redis - Redis如何声明键查找的O(1)时间？

Question

我有一个问题 - 在索引中查找键值对 - 让我们说在 cassandra 或 postgres 上 - 通常在 O(logn) 左右

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

在 redis 文档中，它指出运行时复杂度为 O(1)。

来源:http://redis.io/commands/get http://redis.io/commands/hget

并且获取多个key的值只是线性O(m) 其中m是获取到的key的个数 http://redis.io/commands/hmget

这怎么可能？

Answer 1

Redis 是一种内存存储。因此，它可以使用适合内存存储的数据结构(允许快速随机访问)。

要实现字典(用于主字典，也用于散列和集合对象，并与 zset 对象的跳跃列表结合使用)，Redis 使用 separate chaining hash tables ，其访问复杂度为 O(1+n/k)，其中 n 是项目数，k 是桶数。

Redis 确保桶的数量随着项目的数量而增长，因此在实践中 n/k 保持较低。此重新散列事件在后台逐步完成。当项目数量很大时，复杂度接近于 O(1)(摊销)。

其他存储(例如 Cassandra)旨在将数据存储在磁盘上，同时出于性能原因最小化随机 I/O 的数量。哈希表不是一个好的数据结构，因为它不强制数据的局部性(它不能很好地从缓冲区缓存中获益)。因此，基于磁盘的存储通常使用 B 树变体(大多数 RDBMS)或日志结构合并(LSM)树变体(Cassandra)，它们具有 O(log n) 复杂度。

是的，Redis 为许多操作提供了 O(1)，但有一个约束:所有数据都应该适合内存。这里没有魔法。