在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更合適。無論集羣中的數據量如何，獲取記錄的成本都是相同的。