B型樹的最大深度

如何計算B型樹的最大深度？B型樹的最大深度

假設你有一個1625的B樹，意思是每個節點有1625個指針和1624個元素。

如果樹包含85,000,000個鍵，樹的最大深度是多少？

除了順序之外，還需要指定適合一個葉節點的[平均值]記錄數（或「元素」）。 – mjv 2010-04-05 22:20:25

如果這是作業，請標記爲這樣。 – danben 2010-04-05 22:35:51

最大深度取決於用於操作樹的算法，以及它們的最壞情況行爲是什麼（我不知道具體情況，對不起）。假設完美平衡，近似深度爲log（N）/ log（1625）。

一棵B +樹可能會稍微深一點，因爲只有樹葉會保存鍵，但差別可能可以忽略不計。如果你認爲每個非葉子節點只需要保持指針，它也可能更淺。

2010-04-05 22:24:04

m階B樹的最差情況高度爲log _m/2 n。

2010-04-05 22:25:40

假設

......這棵樹的最小深度爲3，即它有一個根節點，一層非葉節點和一層葉節點。 ...這棵樹的最大深度也是3。

要計算深度最優化的情況下：

採取記錄，85,000,000，由訂單分總人數，1625
這給葉行數：52308
取這個葉行數，除以訂單
這就給出33;這個數字小於順序，那麼我們可以停止潛水，這是根節點中指針的數量。如果這個數字超過一個節點可以容納的數量，我們會有一個額外的水平，並會繼續分割。

我們做了兩個部門，因此樹的深度爲3

如果所有的節點不得不被分割，因此抱着平均訂單/ 2（不四捨五入）指針會發生更糟的情況。最壞情況下的計算是相似的，我們只是按照2/2的比例進行劃分，即我們的情況是812.5，產生了104,616個葉節點，在樹葉上方的水平上有129個非葉節點，最後是一個根跟蹤這些129個非葉節點。

2010-04-05 22:35:11 mjv

Can BerkGüder已經給出了b樹最大深度的公式。在你的情況下，M = 1625

但有奇數個三分球，甚至數字鍵的可能不是一個好主意，因爲在這種情況下，你將不得不不均勻分裂的節點，當它是滿的。

相反，您應該保持每個節點的奇數個鍵和偶數個指針，以實現節點的統一拆分。

2012-04-26 07:08:28

這是B +，不知道B.

85,000,000記載，在最好的情況下，都記錄在天花板（85米/ 1624）= 52340葉。這是底層，這就是爲什麼我們使用的是元素數量而不是指針數量。

爲了找到有多少層次，我們將繼續將我們發現的葉子數量與訂單分開，一路走高：天花板（52340/1625）= 33。這一次我們使用了指針的數量，因爲我們已經確定了底層，元素被存儲在哪裏，現在正在使用指向元素葉的指針。

由於這個數字並不比訂單本身大，我們在那裏停留，因爲這是根;頂層。 Root有33個指針，最多可以指向33x1625（53625）樹葉，差異不應該讓你感到困惑，因爲不是所有的樹葉都可以填充到最大。 53625葉子最多可以存儲53625x1624（87,087,000）個元素，這足以支撐我們的例子。

回到問題，只有根，和葉元素下方，所以深度爲2

希望這有助於。

2013-06-16 19:35:39 boris

B樹是一個平衡的，最壞的情況下檢索是由其高度限制。Btree容量順序中的每個節點有D。最大深度=最壞的情況下

d =二分之一千六百二十四= 812

身高< =登錄_{d + 1}（第（n + 1）/ 2）+1

答案是登錄_{812 +1}（（85,000,000 + 1）/ 2）+1

2014-12-30 14:02:50

回答