用於快速查找和插入遞增整數鍵的內存樹/索引結構

Question

背景：我將插入大約10億個鍵值對。我需要一個內存中索引，我可以同時對（唯一的，64位整數）鍵的（32位整數）值進行查找。沒有更新，沒有刪除，也沒有遍歷。隨着時間的推移，鑰匙通常會逐漸增加。

什麼樣的索引結構最適合處理這個問題？

我能想到的要求是：

• 它需要有高效的重新平衡，由於日益增加的鍵
• 它需要有效地使用存儲器，以適應在RAM中，優選< 28GB
• 它需要非常有效的查找

Answer 1

對於這個問題，可能沒有比簡單的排序向量更高效的數據結構。 （實際上，考慮到對齊問題以及取決於訪問特性，您可能希望將鍵和值放在不同的向量中）。但是存在一些實際問題，特別是如果您不知道數據量有多大。如果你知道這一點，或者如果你準備預先分配太多的空間，然後死亡，如果你得到更多的數據比適合這個空間，那麼這很好，但你仍然需要擔心保持向量排序。

一個可能更好的方法是保留索引範圍的二叉搜索樹，其中BST的葉指向數據「叢」（即向量）。 （這實質上是一個B+ tree。）叢可能相當大;我會說一些事情，比如你希望在幾分鐘內收到的數據量，或者幾千條。他們不必都是相同的大小。 （B +樹通常比這個扇出小，但是因爲你的數據是「大多數排序的」，所以你應該可以使用更大的數據。不要讓它太大，唯一的一點是減少開銷和緩存）

由於您的數據是「大多數排序」，因此您可以將數據累積一段時間，將其保存在普通的有序地圖中（假設您有這樣的事情），甚至可以在使用插入排序的向量中。當這個緩衝區變得足夠大時，你可以把它作爲一個單獨的塊附加到你的主數據結構中，重新分配最後的塊來處理重疊。

如果你有理由確定你很少會失序的鍵，將保持第二個常規BST的無序數據元素。任何無法通過重新分區新簇和前一簇的元素都可以添加到該BST中。要進行查找，可以在主結構和無序結構之間進行並行查找。

如果您偏​​執或對數據量無法確定，只需使用標準的B +樹插入算法，該算法包括創建具有一點保留但未使用的空間的簇以允許插入（a幾個百分點;你想避免空間開銷），並在必要時拆分叢。