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

數(shù)據(jù)結(jié)構(gòu)如下所示：

1、B+樹和N叉樹

1.1、B+樹的基本定義

B+樹是一種平衡的多叉搜索樹，廣泛應用于數(shù)據(jù)庫和文件系統(tǒng)的索引結(jié)構(gòu)（如MySQL的InnoDB存儲引擎）。

核心特點

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

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

1、N叉樹

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

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

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

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

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

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

2、葉子節(jié)點：

存儲鍵值和數(shù)據(jù)指針（或?qū)嶋H數(shù)據(jù)）。所有葉子節(jié)點通過指針雙向連接，形成有序鏈表。

1.3、B+樹的N叉特性

1、階數(shù)決定N的值

階數(shù)m是 B+樹的核心參數(shù)，表示：

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

示例：

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

2、B+樹的N叉特性

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

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

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

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

根本原因：

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

示例：階數(shù)m=3 的 B+樹

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

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

4、階數(shù)和性能的影響

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

如下所示：

注意：

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

2、B+樹的查找元素

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

如下圖所示：

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

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

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

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

3、B+樹的插入元素

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

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

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

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

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

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

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

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

舉例：

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

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

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

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

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

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

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

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

4、實際應用

4.1、Innodb引擎

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

mysql使用共享表空間存儲，所有表的數(shù)據(jù)和索引會存儲在一個共享的 ibdata 文件中。表結(jié)構(gòu)以.frm文件的形式存儲在與表對應的文件夾中。

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

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

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

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

階數(shù)計算示例：

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

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

存儲的計算公式：

4.2、文件系統(tǒng)

Linux 的 Ext4 文件系統(tǒng)：

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

總結(jié)

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

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