在aerospike中使用btree作为主要指标的优势是什么？

Question

我正在阅读Aerospike的文档。并发现为了存储主键，Aerospike使用哈希和散列指向BTree，并且bTree包含指向实际记录的指针。 据我所知，Redis只使用哈希（对于冲突解决方案，他们维护一个哈希列表）。哈希值指向实际记录。

Aerotike使用Btree的优势是什么？这是否意味着通过其主键Aerospike访问记录会花费O（logn）？而redis只需要O（1）。

我可能是错的，但这是我从documentation理解的。有人可以为这个话题提供更多的信息。？

Answer 1

我不知道这个问题的地步，但在这里有云：

其实塞式的primary index是red-black trees分布式哈希，1和4096 sprigs每个分区之间（见partition-tree-sprigs配置PARAM）。

跨群集节点有4096个逻辑分区，它们是evenly distributed。标识任何record的密钥是通过将(namespace, set, PK)三元组通过RIPEMD-160（客户机自动为您执行）生成的20字节摘要。该记录是一致散列到特定分区，因为此摘要中的位用于计算分区ID。

与Redis相比，Redis被设计成单核心，单线程应用程序，运行在单个节点上，Aerospike被构建为分布式数据库。确实，用户可以使用应用程序端解决方案或中间件来实现特定群集Redis。在Aerospike集群中的所有节点的情况下，所有客户端共享一个partition map。

由于客户端知道集群的分区映射，因此它总是与持有主分区的节点（或持有复制分区的节点 - 由replica read policy控制）相隔一跳。所以，它是O（1）到集群中正确的节点。在该节点中，查找分区的rbTree是O（1），然后所有操作都是O（log n）。

当hash table中没有太多数据时（假设你对Redis使用的数据结构是正确的），找到一条记录应该是O（1）。但是，一旦有更多元素比散列表中的插槽切换到链接列表，它是O（n）。对于rbTree，平均值和最坏情况都是O（log n）。 Aerospike旨在处理具有可预测的低延迟的大数据集，因此rbTree更合适。无论集群中的数据量如何，获取记录的成本都是相同的。