我有一个问题 - 在索引中查找键值对 - 比如说在 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
并且获取多个键的值只是线性 O(m)，其中 m 是检索到的键的数量 http://redis.io/commands/hmget
这怎么可能？
Redis 是一个内存存储。因此，它可以使用适用于内存存储的数据结构（允许快速随机访问）。
为了实现字典（用于主字典，也用于散列和集合对象，并与 zset 对象的跳过列表结合使用），Redis 使用单独的链式散列表，其访问复杂度为 O(1+n/k) 其中n 是项目数，k 是桶数。
Redis 确保桶的数量随着项目的数量而增长，因此在实践中 n/k 保持在较低水平。这种重新散列活动在后台逐步完成。当项目数量很大时，复杂性接近 O(1)（摊销）。
其他存储（例如 Cassandra）旨在将数据存储在磁盘上，同时出于性能原因最小化随机 I/O 的数量。哈希表不是一个好的数据结构，因为它不强制数据的局部性（它不能很好地从缓冲区缓存中受益）。因此，基于磁盘的存储通常使用 B 树变体（大多数 RDBMS）或日志结构合并（LSM）树变体（Cassandra），它们具有 O(log n) 复杂度。
所以是的，Redis 为许多操作提供了 O(1)，但有一个限制：所有数据都应该适合内存。这里没有魔法。