解密 B 樹與 B - 樹：構建穩定可擴展的數據結構

前言：在計算機科學中，B 樹（英語：B-tree）是一種自平衡的樹，能夠保持數據有序。這種數據結構能夠讓查找數據、順序訪問、插入數據及刪除的動作，都在對數時間內完成。B 樹，概括來說是一個一般化的二叉查找樹（binary search tree），可以擁有多於 2 個子節點。與自平衡二叉查找樹不同，B 樹爲系統大塊數據的讀寫操作做了優化。B 樹減少定位記錄時所經歷的中間過程，從而加快存取速度。B 樹這種數據結構可以用來描述外部存儲。這種數據結構常被應用在數據庫和文件系統的實現上。

B + 樹是一種樹數據結構，通常用於數據庫和操作系統的文件系統中。B + 樹的特點是能夠保持數據穩定有序，其插入與修改擁有較穩定的對數時間複雜度。B + 樹元素自底向上插入，這與二叉樹恰好相反。

一、B 樹

1.1B 樹的定義

B 樹是一顆多路平衡查找樹，它可以用於高效地存儲和查找大量的數據。我們描述一顆 B 樹時需要指定它的階數，階數表示了一個結點最多有多少個孩子結點，一般用字母 m 表示階數。當 m 取 2 時，就是我們常見的二叉搜索樹。

一顆 m 階的 B 樹定義如下：

• 每個結點最多有 m-1 個關鍵字。

• 根結點最少可以只有 1 個關鍵字。

• 非根結點至少有 Math.ceil(m/2)-1 個關鍵字。

• 每個結點中的關鍵字都按照從小到大的順序排列，每個關鍵字的左子樹中的所有關鍵字都小於它，而右子樹中的所有關鍵字都大於它。

• 所有葉子結點都位於同一層，或者說根結點到每個葉子結點的長度都相同。

上圖是一顆階數爲 4 的 B 樹。在實際應用中的 B 樹的階數 m 都非常大（通常大於 100），所以即使存儲大量的數據，B 樹的高度仍然比較小。每個結點中存儲了關鍵字（key）和關鍵字對應的數據（data），以及孩子結點的指針。我們將一個 key 和其對應的 data 稱爲一個記錄。但爲了方便描述，除非特別說明，後續文中就用 key 來代替（key, value）鍵值對這個整體。在數據庫中我們將 B 樹（和 B + 樹）作爲索引結構，可以加快查詢速速，此時 B 樹中的 key 就表示鍵，而 data 表示了這個鍵對應的條目在硬盤上的邏輯地址。

根據 B 樹的性質可以得出如下重要結論：

• 1）B 樹是所有節點的平衡因子等於 0 的多路平衡查找樹；

• 2）節點的孩子個數爲結點關鍵字數加一；

• 3）根節點無關鍵字相當於沒有子樹，也即是空樹；若根節點有關鍵字，則子樹必大於兩棵；

• 4）根節點外的分支節點至少有 ⌈m/2⌉-1 個關鍵字，即有⌈m/2⌉ 棵子樹；

• 5）節點中關鍵字自左向右遞增，關鍵字兩側均有指向子樹的指針，左邊指針所指子樹的所有關鍵字均小於該關鍵字，右邊指針所指的子樹的關鍵字均大於該關鍵字。

• 6）所有葉節點在最深一層，代表查找失敗的位置。

1.2 B 樹的插入操作

插入操作是指插入一條記錄，即（key, value）的鍵值對。如果 B 樹中已存在需要插入的鍵值對，則用需要插入的 value 替換舊的 value。若 B 樹不存在這個 key, 則一定是在葉子結點中進行插入操作。

• 根據要插入的 key 的值，找到葉子結點並插入。

• 判斷當前結點 key 的個數是否小於等於 m-1，若滿足則結束，否則進行第 3 步。

• 以結點中間的 key 爲中心分裂成左右兩部分，然後將這個中間的 key 插入到父結點中，這個 key 的左子樹指向分裂後的左半部分，這個 key 的右子樹指向分裂後的右半部分，然後將當前結點指向父結點，繼續進行第 3 步。

下面以 5 階 B 樹爲例，介紹 B 樹的插入操作，在 5 階 B 樹中，結點最多有 4 個 key，最少有 2 個 key：

1. 在空樹中插入 39

此時根節點只有一個 key，根節點也是葉子結點

2. 繼續插入 22，97 和 41

根節點有 4 個 key

3. 繼續插入 53

插入後超過了最大允許的關鍵字個數 4，所以以 key 值 41 爲中心進行分裂，結果如下圖所示，分裂後當前結點指向父結點，滿足 B 樹條件，插入操作結束。當階樹 m 爲偶數時，需要分裂時就不存在排序恰好在中間的 key，那麼我們選擇中間位置的前一個 key 或者中間位置的後一個 key 爲中心進行分裂均可。

4. 依次插入 13，21，40，同樣會造成分裂，結果如下所示

5. 依次插入 30，27，33，此時分裂一次，再次插入 36，35，34，此時又會分裂一次，最後插入 24，29，結果如下圖所示：

6. 插入 key 值爲 26 的記錄，插入後的結果如下圖所示

此時當前結點需要以 27 爲中心分裂，並向父結點進位 27，然後當前結點指向父結點，結果如下所示：

進位後導致當前結點（即根結點）也需要分裂，分裂的結果如下圖所示：

分裂後當前結點指向新的根，此時無需調整

最後再依次插入 key 爲 17，28，29，31，32 的記錄，結果如下圖所示：

在實現 B 樹的代碼中，爲了使代碼編寫更加容易，我們可以將結點中存儲記錄的數組長度定義爲 m 而非 m-1，這樣方便底層的結點由於分裂向上層插入一個記錄時，上層有多餘的位置存儲這個記錄。同時，每個結點還可以存儲它的父結點的引用，這樣就不必編寫遞歸程序。

一般來說，對於確定的 m 和確定類型的記錄，結點大小是固定的，無論它實際存儲了多少個記錄。但是分配固定結點大小的方法會存在浪費的情況，比如 key 爲 28,29 所在的結點，還有 2 個 key 的位置沒有使用，但是已經不可能繼續在插入任何值了，因爲這個結點的前序 key 是 27, 後繼 key 是 30, 所有整數值都用完了。所以如果記錄先按 key 的大小排好序，再插入到 B 樹中，結點的使用率就會很低，最差情況下使用率僅爲 50%。

1.3B 樹的刪除操作

刪除操作是指，根據 key 刪除記錄，如果 B 樹中的記錄中不存對應 key 的記錄，則刪除失敗。

• 如果當前需要刪除的 key 位於非葉子結點上，則用後繼 key（這裏的後繼 key 均指後繼記錄的意思）覆蓋要刪除的 key，然後在後繼 key 所在的子支中刪除該後繼 key。此時後繼 key 一定位於葉子結點上，這個過程和二叉搜索樹刪除結點的方式類似。刪除這個記錄後執行第 2 步

• 該結點 key 個數大於等於 Math.ceil(m/2)-1，結束刪除操作，否則執行第 3 步。

• 如果兄弟結點 key 個數大於 Math.ceil(m/2)-1，則父結點中的 key 下移到該結點，兄弟結點中的一個 key 上移，刪除操作結束。

• 否則，將父結點中的 key 下移與當前結點及它的兄弟結點中的 key 合併，形成一個新的結點。原父結點中的 key 的兩個孩子指針就變成了一個孩子指針，指向這個新結點。然後當前結點的指針指向父結點，重複上第 2 步。

有些結點它可能即有左兄弟，又有右兄弟，那麼我們任意選擇一個兄弟結點進行操作即可。

下面以 5 階 B 樹爲例，介紹 B 樹的刪除操作，5 階 B 樹中，結點最多有 4 個 key，最少有兩個 key：

1. 原始狀態

2. 在上面的樹種刪除 21，刪除後結點的關鍵字個數仍然大於等於 2，所以刪除結束

3. 在上述情況下接着刪除 27。從上圖可以得知 27 位於非葉子結點種，所以用 27 的後繼替換它。從圖中可以看出，27 的後繼爲 28，我們用 28 替換 27，然後在 28（原 27）的右孩子結點中刪除 28。刪除後的結果如下所示：

刪除後發現，當前葉子結點的記錄的個數小於 2，而它的兄弟結點中有 3 個記錄（當前結點還有一個右兄弟，選擇右兄弟就會出現合併結點的情況，無論選哪一個都行，只是最後 B 樹的形態不一樣而已），我們可以從兄弟結點中接取一個 key。所以父結點中的 28 下移，兄弟結點中的 26 上移，刪除結束。結果如下所示：

4. 在上述情況下繼續刪除 32，結果如下圖：

當刪除後，當前結點中只有一個 key，而兄弟結點中也僅有兩個 key。所以只能讓父結點中的 30 下移和這兩個孩子結點中的 key 合併，成爲一個新的結點，當前結點的指針指向父結點。結果如下圖所示：

當前 key 的個數滿足條件，故刪除結束

5. 上述情況下，我們繼續刪除 key 爲 40 的記錄，刪除後結果如下圖所示：

同理，當前結點的記錄數小於 2，兄弟結點中沒有多餘 key，所以父結點中的 key 下移，和兄弟（這裏我們選擇左兄弟，選擇右兄弟也可以）結點合併，合併後的指向當前結點的指針就指向了父結點。

同理，對於當前結點而言只能繼續合併了，最後結果如下所示。

合併後結點當前結點滿足條件，刪除結束。

二、B + 樹

2.1B + 樹的定義

各種資料上 B + 樹的定義各有不同，一種定義方式是關鍵字個數和孩子結點個數相同。這裏我們採取維基百科上所定義的方式，即關鍵字個數比孩子結點個數小 1，這種方式是和 B 樹基本等價的。

下圖就是一顆階數爲 4 的 B + 樹：

除此之外 B + 樹還有以下的要求：

• B + 樹包含 2 種類型的結點：內部結點（也稱索引結點）和葉子結點。根結點本身即可以是內部結點，也可以是葉子結點。根結點的關鍵字個數最少可以只有 1 個。

• B + 樹與 B 樹最大的不同是內部結點不保存數據，只用於索引，所有數據（或者說記錄）都保存在葉子結點中。

• m 階 B + 樹表示了內部結點最多有 m-1 個關鍵字（或者說內部結點最多有 m 個子樹），階數 m 同時限制了葉子結點最多存儲 m-1 個記錄。

• 內部結點中的 key 都按照從小到大的順序排列，對於內部結點中的一個 key，左樹中的所有 key 都小於它，右子樹中的 key 都大於等於它。葉子結點中的記錄也按照 key 的大小排列。

• 每個葉子結點都存有相鄰葉子結點的指針，葉子結點本身依關鍵字的大小自小而大順序鏈接。

2.2B + 樹插入操作

若爲空樹，創建一個葉子結點，然後將記錄插入其中，此時這個葉子結點也是根結點，插入操作結束。

針對葉子類型結點：根據 key 值找到葉子結點，向這個葉子結點插入記錄。插入後，若當前結點 key 的個數小於等於 m-1，則插入結束。否則將這個葉子結點分裂成左右兩個葉子結點，左葉子結點包含前 m/2 個記錄，右結點包含剩下的記錄，將第 m/2+1 個記錄的 key 進位到父結點中（父結點一定是索引類型結點），進位到父結點的 key 左孩子指針向左結點，右孩子指針向右結點。將當前結點的指針指向父結點，然後執行第 3 步。

針對索引類型結點：若當前結點 key 的個數小於等於 m-1，則插入結束。否則，將這個索引類型結點分裂成兩個索引結點，左索引結點包含前 (m-1)/2 個 key，右結點包含 m-(m-1)/2 個 key，將第 m/2 個 key 進位到父結點中，進位到父結點的 key 左孩子指向左結點, 進位到父結點的 key 右孩子指向右結點。將當前結點的指針指向父結點，然後重複第 3 步。

下面是一顆 5 階 B 樹的插入過程，5 階 B 樹的結點最少 2 個 key，最多 4 個 key：

1. 空樹中插入 5

2. 依次插入 8，10，15

3. 插入 16

插入 16 後超過了關鍵字的個數限制，所以要進行分裂。在葉子結點分裂時，分裂出來的左結點 2 個記錄，右邊 3 個記錄，中間 key 成爲索引結點中的 key，分裂後當前結點指向了父結點（根結點）。結果如下圖所示。

當然我們還有另一種分裂方式，給左結點 3 個記錄，右結點 2 個記錄，此時索引結點中的 key 就變爲 15。

4. 插入 17

5. 插入 18，插入後如下圖所示：

當前結點的關鍵字個數大於 5，進行分裂。分裂成兩個結點，左結點 2 個記錄，右結點 3 個記錄，關鍵字 16 進位到父結點（索引類型）中，將當前結點的指針指向父結點。

當前結點的關鍵字個數滿足條件，插入結束。

6. 插入若干數據後：

7. 繼續在上圖中插入 7，結果如下所示：

8. 當前結點的關鍵字個數超過 4，需要分裂。左結點 2 個記錄，右結點 3 個記錄。分裂後關鍵字 7 進入到父結點中，將當前結點的指針指向父結點，結果如下圖所示。

當前結點的關鍵字個數滿足條件，插入結束。

2.3B + 樹刪除操作

如果葉子結點中沒有相應的 key，則刪除失敗。否則執行下面的步驟：

• 刪除葉子結點中對應的 key。刪除後若結點的 key 的個數大於等於 Math.ceil(m-1)/2 – 1，刪除操作結束, 否則執行第 2 步。

• 若兄弟結點 key 有富餘（大於 Math.ceil(m-1)/2 – 1），向兄弟結點借一個記錄，同時用借到的 key 替換父結（指當前結點和兄弟結點共同的父結點）點中的 key，刪除結束。否則執行第 3 步。

• 若兄弟結點中沒有富餘的 key, 則當前結點和兄弟結點合併成一個新的葉子結點，並刪除父結點中的 key（父結點中的這個 key 兩邊的孩子指針就變成了一個指針，正好指向這個新的葉子結點），將當前結點指向父結點（必爲索引結點），執行第 4 步（第 4 步以後的操作和 B 樹就完全一樣了，主要是爲了更新索引結點）。

• 若索引結點的 key 的個數大於等於 Math.ceil(m-1)/2 – 1，則刪除操作結束。否則執行第 5 步

• 若兄弟結點有富餘，父結點 key 下移，兄弟結點 key 上移，刪除結束。否則執行第 6 步

• 當前結點和兄弟結點及父結點下移 key 合併成一個新的結點。將當前結點指向父結點，重複第 4 步。

注意，通過 B + 樹的刪除操作後，索引結點中存在的 key，不一定在葉子結點中存在對應的記錄。

下面是一顆 5 階 B 樹的刪除過程，5 階 B 數的結點最少 2 個 key，最多 4 個 key。

1. 初始狀態

2. 刪除 22，刪除後結果如下

刪除後葉子結點中 key 的個數大於等於 2，刪除結束

3. 刪除 15，刪除後的結果如下圖所示

刪除後當前結點只有一個 key, 不滿足條件，而兄弟結點有三個 key，可以從兄弟結點借一個關鍵字爲 9 的記錄, 同時更新將父結點中的關鍵字由 10 也變爲 9，刪除結束。

4. 刪除 7，刪除後的結果如下所示

當前結點關鍵字個數小於 2，（左）兄弟結點中的也沒有富餘的關鍵字（當前結點還有個右兄弟，不過選擇任意一個進行分析就可以了，這裏我們選擇了左邊的），所以當前結點和兄弟結點合併，並刪除父結點中的 key，當前結點指向父結點。

此時當前結點的關鍵字個數小於 2，兄弟結點的關鍵字也沒有富餘，所以父結點中的關鍵字下移，和兩個孩子結點合併，結果如下圖所示。

三、B + 樹和 B 樹比較

B 樹可以看作是對 2-3 查找樹的一種擴展，即他允許每個節點有 M-1 個子節點。

• 根節點至少有兩個子節點

• 每個節點有 M-1 個 key，並且以升序排列

• 位於 M-1 和 M key 的子節點的值位於 M-1 和 M key 對應的 Value 之間

• 其它節點至少有 M/2 個子節點

下圖是一個 M=4 階的 B 樹：

可以看到 B 樹是 2-3 樹的一種擴展，他允許一個節點有多於 2 個的元素。

B 樹的插入及平衡化操作和 2-3 樹很相似，這裏就不介紹了。下面是往 B 樹中依次插入：

6 10 4 14 5 11 15 3 2 12 1 7 8 8 6 3 6 21 5 15 15 6 32 23 45 65 7 8 6 5 4

的演示動畫：

B+ 樹是對 B 樹的一種變形樹，它與 B 樹的差異在於：

• 有 k 個子結點的結點必然有 k 個關鍵碼；

• 非葉結點僅具有索引作用，跟記錄有關的信息均存放在葉結點中。

• 樹的所有葉結點構成一個有序鏈表，可以按照關鍵碼排序的次序遍歷全部記錄。

如下圖，是一個 B + 樹:

下圖是 B + 樹的插入動畫：

B 和 B + 樹的區別在於，B + 樹的非葉子結點只包含導航信息，不包含實際的值，所有的葉子結點和相連的節點使用鏈表相連，便於區間查找和遍歷。

B + 樹的優點在於：

• 由於 B + 樹在內部節點上不包含數據信息，因此在內存頁中能夠存放更多的 key。數據存放的更加緊密，具有更好的空間局部性。因此訪問葉子節點上關聯的數據也具有更好的緩存命中率

• B + 樹的葉子節點都是相連的，因此對整棵樹的遍歷只需要一次線性遍歷葉子節點即可。而且由於數據順序排列並且相連，所以便於區間查找和搜索。而 B 樹則需要進行每一層的遞歸遍歷。相鄰的元素可能在內存中不相鄰，所以緩存命中性沒有 B + 樹好。

• B + 樹的數據只存儲在葉子節點中，因此插入和刪除操作只需要修改葉子節點和對應的索引節點，不需要進行節點的分裂和合並，因此 B + 樹的插入和刪除操作更加高效。而 B 樹的每個節點都可以存儲數據，因此在進行插入和刪除操作時需要進行節點分裂和合並。

但是 B 樹也有優點，其優點是：

B 樹的每一個節點都包含 key 和 value，因此經常訪問的元素可能離根節點更近，因此訪問也更迅速。

3.1B 樹的數據如何存儲在磁盤上

B 樹的數據存儲在磁盤上的方式可以分爲兩種：順序存儲和分塊存儲。

順序存儲是指將 B 樹的節點按照層級順序存儲在磁盤上。每個節點被存儲在一個磁盤塊中，而磁盤塊之間通過指針相連。在進行查找、插入和刪除等操作時，需要從根節點開始逐級讀取磁盤塊，直到找到目標節點。由於每次讀取磁盤塊都需要進行 I/O 操作，因此順序存儲方式對磁盤的訪問次數較多，效率相對較低。

分塊存儲是指將 B 樹的節點分爲若干塊，每個塊被存儲在一個磁盤塊中。不同的塊之間通過指針相連。在進行查找、插入和刪除等操作時，只需要讀取與目標節點相鄰的塊，而不需要讀取整個 B 樹。這種方式可以減少磁盤 I/O 的次數，提高操作效率。同時，可以根據磁盤塊的大小和 B 樹的節點大小進行合理的調整，使得存儲空間利用率更高。

總的來說，B 樹的數據存儲方式需要根據具體應用場景和數據規模進行選擇。順序存儲適用於小規模數據和較小的磁盤容量，而分塊存儲適用於大規模數據和較大的磁盤容量。同時，爲了進一步提高 B 樹的訪問效率，可以採用緩存技術，將熱點數據緩存到內存中，以減少磁盤 I/O 的次數。

3.2B + 樹的數據如何存儲在磁盤上

B + 樹的數據存儲在磁盤上的方式與 B 樹有所不同，主要採用分層索引和順序存儲的方式。

具體來說，B + 樹的內部節點僅存儲鍵值和指向下層節點的指針，而不存儲具體的數據。所有的數據都存儲在 B + 樹的葉子節點中，而每個葉子節點之間通過指針相連，形成一個有序鏈表。

在 B + 樹的實現中，通常採用分層索引的方式來降低訪問成本。具體來說，B + 樹的根節點存儲所有數據的索引信息，而每個非葉子節點則存儲一部分索引信息，這些索引信息用於指向下一級節點。在進行數據查找和訪問時，只需要讀取相應的索引信息和葉子節點即可。

爲了提高 B + 樹的訪問效率，一般採用順序存儲的方式來存儲磁盤塊中的數據。每個葉子節點被存儲在一個磁盤塊中，而磁盤塊之間通過指針相連。每個磁盤塊中存儲的數據按照從小到大的順序排列，這樣可以支持範圍查詢等操作。同時，通過使用預讀技術和緩存技術等方法，可以進一步提高 B + 樹的訪問效率。

總的來說，B + 樹的數據存儲方式相對於 B 樹更加緊湊，同時也更加高效。這種數據存儲方式不僅可以降低磁盤 I/O 的次數，而且可以支持更高效的範圍查詢和排序操作。

對 B 樹和 B + 樹的分析和對前面講解的 2-3 樹的分析類似，對於一顆節點爲 N 度爲 M 的子樹，查找和插入需要 logM-1N ~ logM/2N 次比較。這個很好證明，對於度爲 M 的 B 樹，每一個節點的子節點個數爲 M/2 到 M-1 之間，所以樹的高度在 logM-1N 至 logM/2N 之間。

這種效率是很高的，對於 N=62*1000000000 個節點，如果度爲 1024，則 logM/2N <=4，即在 620 億個元素中，如果這棵樹的度爲 1024，則只需要小於 4 次即可定位到該節點，然後再採用二分查找即可找到要找的值。

四、B 樹與 B + 樹應用

B 樹和 B + 廣泛應用於文件存儲系統以及數據庫系統中，在講解應用之前，我們看一下常見的存儲結構：

我們計算機的主存基本都是隨機訪問存儲器 (Random-Access Memory，RAM)，他分爲兩類：靜態隨機訪問存儲器（SRAM）和動態隨機訪問存儲器（DRAM）。SRAM 比 DRAM 快，但是也貴的多，一般作爲 CPU 的高速緩存，DRAM 通常作爲內存。這類存儲器他們的結構和存儲原理比較複雜，基本是使用電信號來保存信息的，不存在機器操作，所以訪問速度非常快，具體的訪問原理可以查看 CSAPP，另外，他們是易失的，即如果斷電，保存 DRAM 和 SRAM 保存的信息就會丟失。

我們使用的更多的是使用磁盤，磁盤能夠保存大量的數據，從 GB 一直到 TB 級，但是 他的讀取速度比較慢，因爲涉及到機器操作，讀取速度爲毫秒級，從 DRAM 讀速度比從磁盤度快 10 萬倍，從 SRAM 讀速度比從磁盤讀快 100 萬倍。下面來看下磁盤的結構：

如上圖，磁盤由盤片構成, 每個盤片有兩面，又稱爲盤面 (Surface)，這些盤面覆蓋有磁性材料。盤片中央有一個可以旋轉的主軸(spindle)，他使得盤片以固定的旋轉速率旋轉，通常是 5400 轉每分鐘(Revolution Per Minute,RPM) 或者是 7200RPM。磁盤包含一個多多個這樣的盤片並封裝在一個密封的容器內。上圖左，展示了一個典型的磁盤表面結構。每個表面是由一組成爲磁道 (track) 的同心圓組成的，每個磁道被劃分爲了一組扇區 (sector). 每個扇區包含相等數量的數據位，通常是（512）子節。扇區之間由一些間隔(gap) 隔開, 不存儲數據。

以上是磁盤的物理結構，現在來看下磁盤的讀寫操作：

如上圖，磁盤用讀 / 寫頭來讀寫存儲在磁性表面的位，而讀寫頭連接到一個傳動臂的一端。通過沿着半徑軸前後移動傳動臂，驅動器可以將讀寫頭定位到任何磁道上，這稱之爲尋道操作。一旦定位到磁道後，盤片轉動，磁道上的每個位經過磁頭時，讀寫磁頭就可以感知到位的值，也可以修改值。對磁盤的訪問時間分爲 尋道時間，旋轉時間，以及傳送時間。

由於存儲介質的特性，磁盤本身存取就比主存慢很多，再加上機械運動耗費，因此爲了提高效率，要儘量減少磁盤 I/O，減少讀寫操作。爲了達到這個目的，磁盤往往不是嚴格按需讀取，而是每次都會預讀，即使只需要一個字節，磁盤也會從這個位置開始，順序向後讀取一定長度的數據放入內存。這樣做的理論依據是計算機科學中著名的局部性原理：

當一個數據被用到時，其附近的數據也通常會馬上被使用。

程序運行期間所需要的數據通常比較集中。

由於磁盤順序讀取的效率很高（不需要尋道時間，只需很少的旋轉時間），因此對於具有局部性的程序來說，預讀可以提高 I/O 效率。

預讀的長度一般爲頁（page）的整倍數。頁是計算機管理存儲器的邏輯塊，硬件及操作系統往往將主存和磁盤存儲區分割爲連續的大小相等的塊，每個存儲塊稱爲一頁（在許多操作系統中，頁得大小通常爲 4k），主存和磁盤以頁爲單位交換數據。當程序要讀取的數據不在主存中時，會觸發一個缺頁異常，此時系統會向磁盤發出讀盤信號，磁盤會找到數據的起始位置並向後連續讀取一頁或幾頁載入內存中，然後異常返回，程序繼續運行。

文件系統及數據庫系統的設計者利用了磁盤預讀原理，將一個節點的大小設爲等於一個頁，這樣每個節點只需要一次 I/O 就可以完全載入。爲了達到這個目的，在實際實現 B-Tree 還需要使用如下技巧：

每次新建一個節點的同時，直接申請一個頁的空間 (512 或者 1024)，這樣就保證一個節點物理上也存儲在一個頁裏，加之計算機存儲分配都是按頁對齊的，就實現了一個 node 只需一次 I/O。如，將 B 樹的度 M 設置爲 1024，這樣在前面的例子中，600 億個元素中只需要小於 4 次查找即可定位到某一存儲位置。

同時在 B + 樹中，內節點只存儲導航用到的 key，並不存儲具體值，這樣內節點個數較少，能夠全部讀取到主存中，外接點存儲 key 及值，並且順序排列，具有良好的空間局部性。所以 B 及 B + 樹比較適合與文件系統的數據結構。下面是一顆 B 樹，用來進行內容存儲。

本文由 Readfog 進行 AMP 轉碼，版權歸原作者所有。
來源：https://mp.weixin.qq.com/s/EItzc0EvUH3lpw-GaKHJIA