在 aerospike 中使用 btree 作为主索引有什么好处？
what is the advantage of using btree in aerospike for primary index?
我正在浏览 Aerospike 的文档。并发现为了存储主键，Aerospike 使用散列和散列指向 BTree，而 bTree 包含指向实际记录的指针。
据我所知，Redis 只使用散列（为了解决冲突，他们维护一个散列列表）。散列指向实际记录。
aerospike使用Btree有什么优势？这是否意味着通过其主键 aerospike 访问记录需要 O(logn) ？而 redis 只需要 O(1).
我可能是错的，但这就是我从 documentation 中了解到的全部内容。有人可以更详细地说明这个话题吗？
我不确定问题的重点，但这里是：
实际上是 Aerospike 的 primary index is a distributed hash of red-black trees, between 1 and 4096 sprigs per partition (see the partition-tree-sprigs 配置参数）。
有 4096 个逻辑分区，evenly distributed across the nodes of the cluster. The key identifying any record 是通过 RIPEMD-160 传递 (namespace, set, PK) 三元组生成的 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)。但是，一旦哈希 table 中的元素多于槽，它就会切换到链表，即 O(n)。对于 rbTree，平均情况和最坏情况的复杂度均为 O(log n)。 Aerospike 旨在处理具有 predictable 低延迟的大型数据集，因此 rbTree 更合适。无论集群中的数据量如何，获取记录的成本都是相同的。
补充： 从 Aerospike DB 4.2 版开始，sprigs 在内存方面变得更加便宜，并且每个分区 4096 个 sprigs 的限制已被删除。您可以通过分配足够的枝条有效地将枝条变成深度为 1 的红黑树，因此可以使 O(log n) 实际上与 O(1) 相同。例如，如果您希望小枝的平均树深度为 1，并且您的数据库中有十亿个对象，则可以将 partition-tree-sprigs 设置为 262144（必须是 2 的幂），这将花费848MB 均匀分布到节点（3 节点集群中为 283MB）。
我正在浏览 Aerospike 的文档。并发现为了存储主键，Aerospike 使用散列和散列指向 BTree，而 bTree 包含指向实际记录的指针。 据我所知，Redis 只使用散列（为了解决冲突，他们维护一个散列列表）。散列指向实际记录。
aerospike使用Btree有什么优势？这是否意味着通过其主键 aerospike 访问记录需要 O(logn) ？而 redis 只需要 O(1).
我可能是错的，但这就是我从 documentation 中了解到的全部内容。有人可以更详细地说明这个话题吗？
我不确定问题的重点，但这里是：
实际上是 Aerospike 的 primary index is a distributed hash of red-black trees, between 1 and 4096 sprigs per partition (see the partition-tree-sprigs 配置参数）。
有 4096 个逻辑分区，evenly distributed across the nodes of the cluster. The key identifying any record 是通过 RIPEMD-160 传递 (namespace, set, PK) 三元组生成的 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)。但是，一旦哈希 table 中的元素多于槽，它就会切换到链表，即 O(n)。对于 rbTree，平均情况和最坏情况的复杂度均为 O(log n)。 Aerospike 旨在处理具有 predictable 低延迟的大型数据集，因此 rbTree 更合适。无论集群中的数据量如何，获取记录的成本都是相同的。
补充： 从 Aerospike DB 4.2 版开始，sprigs 在内存方面变得更加便宜，并且每个分区 4096 个 sprigs 的限制已被删除。您可以通过分配足够的枝条有效地将枝条变成深度为 1 的红黑树，因此可以使 O(log n) 实际上与 O(1) 相同。例如，如果您希望小枝的平均树深度为 1，并且您的数据库中有十亿个对象，则可以将 partition-tree-sprigs 设置为 262144（必须是 2 的幂），这将花费848MB 均匀分布到节点（3 节点集群中为 283MB）。