我一直在尋找最好的& B +樹最壞的情況下（http://en.wikipedia.org/wiki/B-tree#Best_case_and_worst_case_heights），但我不知道如何使用這個公式與我有的信息。 假設我有一棵有1000條記錄的樹B，B級可以擁有的最大（和最大）數是多少？ 我可以在每個頁面上擁有多少個小鍵。我也可以有很多/少量的頁面。 任何想法？ （如果你想知道，這不是一個家庭作業問題，但它肯定會幫助我理解hw的一些東西。）B +樹上最小/最大記錄數？
它取決於樹的arity。你必須定義這個值。如果說，每個節點都可以有4個孩子，然後你有1000條記錄，則高度
最好的情況log_4（1000）= 5
最壞的情況LOG_ {} 4/2（1000）= 10
矩陣是m，記錄數是n。
我沒有數學得心應手，但...
基本上，樹深度的主要因素是樹中的每個節點的「扇出」。
通常情況下，在簡單的B樹中，扇出爲樹中每個節點的子節點爲2,2個節點。
但是用B +樹，它們通常會有更大的扇形。
進入播放的一個因素是磁盤上節點的大小。例如，如果您有4K頁面大小，並且有4000字節的可用空間（不包括與節點相關的任何其他指針或其他元數據），並且可以說指向任何其他節點的指針在樹中是一個4字節的整數。如果您的B +樹實際上存儲了4個字節的整數，則組合大小（指針信息的4個字節+ 4個字節的關鍵信息）= 8個字節。 4000個空閒字節/ 8個字節== 500個可能的孩子。
這給你一個500人的粉絲爲這個人爲的案件。
因此，只有一頁索引（即根節點）或樹的高度爲1時，可以引用500條記錄。添加另一個級別，並且您的值爲500 * 500，因此對於501個4K頁面，您可以引用250,000行。
很顯然，密鑰的大小越大，或者節點的頁面尺寸越小，該樹能夠勝出的扇形越小。如果您允許每個節點中的可變長度密鑰，那麼扇出可以很容易地改變。
但希望你能看到這一切的工作原理。
有道理！謝謝！ – Eric
最好的和最壞的情況取決於沒有。每個節點可以擁有的孩子。對於最好的情況，我們考慮這樣的情況，即當每個節點具有m-1個密鑰的每個節點時，子節點的最大數量（即m個樹的m）。所以，
第一電平（或根）具有m-1條目 第二級具有m *（M-1）的條目（因爲根具有m兒童每個m-1的鍵） 第三級具有平方公尺*（m-1）條目 ....（H-1）*（m-1）
因此，如果H是樹的高度，則條目的總數等於n = m^H-1 這是相當於H = log_m（n + 1）
因此，在你的情況下，如果你有n = 1000個記錄，每個節點有m個孩子（m應該是奇數），那麼最好的情況高度將等於log_m （1000 + 1）
類似地，對於最壞的情況下：
1級（根）具有至少1個條目（和最小2個孩子） 第二級至少有2 *（d-1）個條目（其中d = ceil（m/2）是每個內部節點（根除外）可以擁有的最小子數） 第3級有2d *（d-1）個條目 ... Hth等級具有2 * d ^（h-2）*（d-1）個條目
因此，如果H是樹的高度，則條目的總數等於n = 2 *如果你有n = 1000條記錄，每個節點有m個孩子（m應該是奇數），則最差情況高度將等於log_d（（1000 + 1）/ 2 + 1）
這很容易！謝謝！ – Eric