Làm thế nào để redis yêu cầu O (1) thời gian để tra cứu chính?

Question

Tôi có một câu hỏi - tra cứu một cặp khóa giá trị trong chỉ mục - giả sử trên cassandra hoặc postgres - thường ở khoảng O (logn)

source: https://github.com/tinkerpop/blueprints/wiki/Graph-Indices.

Trong tài liệu redis, nó cho biết độ phức tạp thời gian chạy là O (1).

Nguồn: http://redis.io/commands/get http://redis.io/commands/hget

Và nhận được giá trị của nhiều phím chỉ O tuyến tính (n) http://redis.io/commands/hmget

Làm thế nào là nó có thể?

Answer 1

Redis là một cửa hàng trong bộ nhớ. Do đó, nó có thể sử dụng các cấu trúc dữ liệu thích nghi với bộ nhớ lưu trữ (cho phép truy cập ngẫu nhiên nhanh).

Để thực hiện từ điển (được sử dụng cho từ điển chính, nhưng cũng cho đối tượng băm và đặt và kết hợp với danh sách bỏ qua đối tượng zset), Redis sử dụng separate chaining hash tables, có độ phức tạp truy cập là O (1 + n/k) trong đó n là số vật phẩm và số lượng xô.

Redis đảm bảo số lượng nhóm phát triển với số lượng mục để trong thực tế n/k được giữ ở mức thấp. Hoạt động phục hồi này được thực hiện từng bước trong nền. Khi số lượng các mục là đáng kể, độ phức tạp là gần với O (1) (khấu hao).

Các cửa hàng khác (ví dụ Cassandra) được thiết kế để lưu trữ dữ liệu trên đĩa trong khi giảm thiểu số lượng I/O ngẫu nhiên vì lý do hiệu suất. Một bảng băm không phải là một cấu trúc dữ liệu tốt cho điều này, bởi vì nó không thực thi địa phương của dữ liệu (nó không được hưởng lợi từ bộ đệm đệm rất tốt). Vì vậy, các cửa hàng dựa trên đĩa thường sử dụng các biến thể B-tree (hầu hết RDBMS) hoặc các biến thể cây có cấu trúc nhật ký (LSM) (Cassandra), có độ phức tạp O (log n).

Vì vậy, có, Redis cung cấp O (1) cho nhiều thao tác, nhưng có một ràng buộc: tất cả dữ liệu phải phù hợp với bộ nhớ. Không có ma thuật ở đây.