在Aerospike中使用btree作为主要索引有什么优势？

Question

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

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

我可能是错的，但是我从文档中了解到了全部。有人可以在这个话题上发表更多意见吗？

Answer 1

我不确定问题的重点，但是这里是：

实际上塞式的主索引是分布式哈希红黑树，1个4096之间小枝每个分区（参见partition-tree-sprigs配置PARAM）。

共有4096个逻辑分区，它们均匀分布在群集的各个节点上。标识任何记录的密钥是20字节摘要，该摘要是通过将(namespace, set, PK)三元组传递到RIPEMD-160（客户端自动为您完成的操作）而产生的。由于该摘要中的位用于计算分区ID，因此该记录将始终哈希到特定分区。

与Redis设计为在单个节点上运行的单核，单线程应用程序相反，Aerospike被构建为分布式数据库。的确，用户可以使用应用程序端解决方案或中间件临时群集Redis。对于Aerospike，群集中的所有节点以及所有客户端共享一个分区图。

由于客户端知道群集的分区图，因此它总是与保存主分区的节点（或保存副本分区的节点-由副本读取策略控制）相距一跳。因此，它是群集中正确节点的O（1）。在该节点内，找到分区的rbTree为O（1），然后所有操作均为O（log n）。

如果哈希表中没有很多数据（假设您对Redis使用的数据结构是正确的），则查找记录应为O（1）。但是，一旦哈希表中的元素多于插槽，它就会切换到链表O（n）。对于rbTree，平均情况和最坏情况均为O（log n）。Aerospike旨在处理可预测的低延迟的大型数据集，因此rbTree更合适。无论集群中的数据量如何，获取记录的成本都是相同的。

补充：从Aerospike DB 4.2版开始，小树枝在内存方面变得便宜得多，并且每个分区4096个小树枝的限制已删除。通过分配足够的小枝，可以有效地将小枝变成深度为1的红黑树，因此O（log n）实际上可以与O（1）相同。例如，如果您希望这些小树枝的平均树深为1，并且数据库中有十亿个对象，partition-tree-sprigs则应将其设置为262144（必须是2的幂），这将花费848MB均匀分配给节点（3节点群集中的283MB）。