B+樹是一種優(yōu)化的B樹結構，適用于數據庫索引。它保證所有數據都在葉子節(jié)點，且葉子節(jié)點間有鏈接，便于數據檢索。

數據結構如下所示：

1、B+樹和N叉樹

1.1、B+樹的基本定義

B+樹是一種平衡的多叉搜索樹，廣泛應用于數據庫和文件系統的索引結構（如MySQL的InnoDB存儲引擎）。

核心特點

• 每個節(jié)點可以包含多個子節(jié)點（即N叉樹）。
• 所有葉子節(jié)點通過指針連接，形成一個有序鏈表。
• 內部節(jié)點僅存儲鍵值，數據（記錄指針）僅存在于葉子節(jié)點。

1.2、B+樹與N叉樹的關系

1、N叉樹

N叉樹是指每個節(jié)點最多有NN個子節(jié)點的樹結構。

• 二叉樹：每個節(jié)點最多有 2 個子節(jié)點（N=2）。
• 三叉樹：每個節(jié)點最多有 3 個子節(jié)點（N=3）。
• B+樹：每個節(jié)點最多有mm個子節(jié)點（N=m，其中mm是 B+樹的階數）。

2、B+樹的節(jié)點結構

B+樹的節(jié)點分為內部節(jié)點和葉子節(jié)點。

1、內部節(jié)點（非葉子節(jié)點）：

存儲鍵值（Key）和子節(jié)點指針。每個節(jié)點最多有mm個子節(jié)點（N=m）。

2、葉子節(jié)點：

存儲鍵值和數據指針（或實際數據）。所有葉子節(jié)點通過指針雙向連接，形成有序鏈表。

1.3、B+樹的N叉特性

1、階數決定N的值

階數m是 B+樹的核心參數，表示：

• 每個節(jié)點最多有m個子節(jié)點。
• 每個節(jié)點最多存儲m−1個鍵值。

示例：

對于階數m=5的 B+樹：每個節(jié)點最多有 5 個子節(jié)點（N=5）。每個節(jié)點最多存儲 4 個鍵值。

2、B+樹的N叉特性

每個節(jié)點的子節(jié)點數量可變：

• 內部節(jié)點的子節(jié)點數在⌈m/2⌉到m之間（保持樹的平衡）。
• 葉子節(jié)點的子節(jié)點數為 0（無子節(jié)點）。

3、B+樹被稱為N叉樹原因

直接原因：B+樹的每個節(jié)點最多有mm個子節(jié)點（N=m），符合N叉樹的定義。

根本原因：

• 多路平衡：B+樹通過多路分支（N叉）減少樹的高度，提高磁盤IO效率。
• 階數mm：B+樹的性能與mm直接相關，mm越大，樹越矮，查找路徑越短。

示例：階數m=3 的 B+樹

        [10, 20]              // 內部節(jié)點（2個鍵值，3個子節(jié)點）
       /     |     \
[5, 8]      [15]      [25, 30] // 葉子節(jié)點（存儲數據）

• 內部節(jié)點：存儲鍵值10、20，指向 3 個子節(jié)點。
• 葉子節(jié)點：存儲數據（如記錄指針），并通過指針連接。

4、階數和性能的影響

1.4、B+樹與B樹的區(qū)別

如下所示：

注意：

• B+樹是N叉樹的一種，其階數mm決定了每個節(jié)點的最大子節(jié)點數（N=m）。
• 這種多叉結構是B+樹在數據庫和文件系統中廣泛應用的核心原因。

2、B+樹的查找元素

B+樹中的所有數據均保存在葉子結點，且根結點和內部結點均只是充當控制查找記錄的媒介，并不代表數據本身，所有的內部結點元素都同時存在于子結點中，是子節(jié)點元素中是最大（或最小）元素。

如下圖所示：

例如B+樹中查找55這個關鍵字，步驟如下：

1、在根節(jié)點中對比55和根節(jié)點中的元素[60, 85]，發(fā)現55<60，因此應該在第一個結點中繼續(xù)尋找；

2、比較55和第一個節(jié)點中的元素[10, 20, 50, 60]，發(fā)現50<55<60，因此55應該存在于第四個結點當中；

3、繼續(xù)對比55和第四個結點中的元素[55, 60]，找到55，查找成功。當然，也有查找失敗的情況，即要查找的元素并不在B+樹中。

3、B+樹的插入元素

其插入規(guī)則如下：

1、插入的操作全部都在葉子結點上進行，且不能破壞關鍵字自小而大的順序；

2、當插入關鍵字后結點的關鍵字個數大于m，需要進行“分裂”。

B+樹的插入有四種情況：

1、若被插入關鍵字所在的結點，其含有關鍵字數目小于m，則直接插入；

2、若被插入關鍵字所在的結點，其含有關鍵字數目等于m，則需要將這個結點分為左右兩部分，中間的結點放到父節(jié)點中。假設其雙親結點中包含的關鍵字個數小于 m，則插入操作完成。

3、在第 2 種情況中，如果上移操作導致其雙親結點中關鍵字個數大于 M，則應繼續(xù)分裂其雙親結點。

4、若插入的關鍵字比當前結點中的最大值還大，破壞了B+樹中從根結點到當前結點的所有索引值，此時需要及時根節(jié)點、字節(jié)點，再做葉子節(jié)點插入操作。

舉例：

1、插入關鍵字12，此時第一個葉子節(jié)點部分[10, 15]關鍵字的個數<m，可以直接插入：（紫色代表插入的元素）

2、插入95，需要插入到最后一個葉子節(jié)點部分[85, 91, 97]：

此時該節(jié)點的關鍵字個數大于m，需要進行分裂操作，并且父節(jié)點需要插入一個新的關鍵字：

3、插入40，需要插入到第二個葉子節(jié)點部分[21, 37, 44]：

此時該節(jié)點的關鍵字個數大于m，需要進行分裂操作，并且父節(jié)點需要插入一個新的關鍵字：

父節(jié)點插入新的關鍵字之后，根結點關鍵字的個數大于m，也需要進行分裂：

4、插入100，由于其值比最大值 97 還大，插入之后，從根結點到該結點經過的所有結點中的所有值都要由 97 改為 100。（橙色為修改之后的）

修改完最大值之后，在最后一個節(jié)點處插入100：

4、實際應用

4.1、Innodb引擎

MySQL數據表以文件方式存放在磁盤中，默認使用共享表空間（0）存儲。

mysql使用共享表空間存儲，所有表的數據和索引會存儲在一個共享的 ibdata 文件中。表結構以.frm文件的形式存儲在與表對應的文件夾中。

如果使用了獨立表空間，InnoDB 會將每個表的結構和數據存儲在獨立的 .ibd 文件中。每當表的數據或索引被更新時，文件也會隨之變化。表的結構仍然以.frm文件存儲。

更多知識詳細可參考：談談mysql的日志的用途

每個頁節(jié)點段、非頁節(jié)點段可參考如下：

注意：階數由頁大?。≒age Size）決定（通常為 16KB）。

階數計算示例：

每個關鍵字（如主鍵）為 8 字節(jié)，指針為 6 字節(jié)。當磁盤塊Page頁大小為 16KB：

實際階數約為 1170，樹高度為 3 時可存儲1170^3≈1.6億條記錄。

存儲的計算公式：

4.2、文件系統

Linux 的 Ext4 文件系統：

• 使用 B+樹管理目錄項。
• 階數由塊大?。?KB）和目錄項大小決定。

總結

在數據庫中通常不只是查詢(select)一條記錄，如果是多條記錄的話，B樹要做中序遍歷，可能要跨層訪問，而B+樹由于所有的數據都在葉子節(jié)點，不用跨層，同時由于有鏈表結構只要找到首尾，就能通過鏈表把數據都讀出來。

以上為個人經驗，希望能給大家一個參考，也希望大家多多支持腳本之家。

最新評論