我已經構建了一個我自己的b +樹索引，包含對索引進行插入/刪除/搜索的所有操作。爲了加速插入一個巨大的數據集，我想實現批量加載以及能夠實驗大數據集。將數據批量加載到b +樹中
我一直在試圖做的是對數據進行排序並開始填充葉級別的頁面。一旦必要，密鑰被複制或推送到上層。我始終跟蹤不同高度的指數前沿。例如，如果我的索引高度爲3（根，包含內部節點和葉子級別的一個級別），我只在內存中保留3頁，一旦它們滿了或者沒有更多數據，我將它們寫入磁盤。
問題是要向每個頁面寫入多少數據才能維護所有單個節點的頁面限制。這些限制可以在 here找到。我無法找到任何有用的資源，詳細說明批量加載的實施情況，或者確定使用哪種填充比率以確保節點限制的好策略。
任何想法？
從問題的評論我可以告訴你的關注是最後一頁（或最後一頁，如果考慮在樹上更高）可能無法達到最小填充計數。
由於這些頁面的數量以log2（n）（樹的高度）爲界，我懷疑理論性能保證不受影響。
無論如何，您鏈接到的保證不是正確性所必需的。它們足以保證運行時間的界限。他們不是必要雖然保證運行時間（例如：一行添加一行到b-tree的末尾 - 你仍然得到相同的保證運行時間）。
如果你想知道真實的B樹是如何操作的，你可能想看看你最喜歡的RDBMS（作爲一個SQL Server用戶，我知道SQL Server高興地低於50％的頁面填充保證沒有實際影響）。我認爲你會發現理論上的擔憂被認爲不是很有意義。
沒錯！如果您可以設法保持樹木平衡，那麼％50填充率不會是一個非常大的問題。特別是，如果你有一個很大的分支因子。但問題最初是如何建立一個平衡的B +樹，首先使用批量加載。那麼，我已經從頭開始編寫了一個B +樹，並且已經用一種方法解決了這個問題，計算了每個級別的桶的數量並將這些密鑰均勻分佈在桶中，但仍然對標準做法感到好奇。 – Pirooz
爲什麼你不填滿所有的網頁，直到他們滿了？只要樹不退化成病理性病例，理論上的限制在實踐中並不重要。 – usr
如果我在很多情況下將每個頁面填充到最大容量，我最終會得到一個不平衡的B +樹。密鑰需要在水平和垂直方向上大致均勻地分佈在索引上，這就是爲什麼存在理論極限。 – Pirooz
您提供的鏈接表示任何節點的最大容量爲b，這意味着它最大滿。我不能拿出一個數據集來填充樹葉，直到它們滿了會導致樹不平衡。你能給個例子嗎？ – usr