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

获取多个键的值只是线性O(m),其中m是检索到的键数 http://redis.io/commands/hmget

这怎么可能？

Answer 1

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),但存在一个约束:所有数据都应该适合内存.这里没有魔力.