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

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

1、B+樹和N叉樹

1.1、B+樹的基本定義

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

核心特點(diǎn)

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

1.2、B+樹與N叉樹的關(guān)系

1、N叉樹

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

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

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

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

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

存儲(chǔ)鍵值（Key）和子節(jié)點(diǎn)指針。每個(gè)節(jié)點(diǎn)最多有mm個(gè)子節(jié)點(diǎn)（N=m）。

2、葉子節(jié)點(diǎn)：

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

1.3、B+樹的N叉特性

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

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

• 每個(gè)節(jié)點(diǎn)最多有m個(gè)子節(jié)點(diǎn)。
• 每個(gè)節(jié)點(diǎn)最多存儲(chǔ)m−1個(gè)鍵值。

示例：

對(duì)于階數(shù)m=5的 B+樹：每個(gè)節(jié)點(diǎn)最多有 5 個(gè)子節(jié)點(diǎn)（N=5）。每個(gè)節(jié)點(diǎn)最多存儲(chǔ) 4 個(gè)鍵值。

2、B+樹的N叉特性

每個(gè)節(jié)點(diǎn)的子節(jié)點(diǎn)數(shù)量可變：

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

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

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

根本原因：

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

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

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

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

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

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

如下所示：

注意：

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

2、B+樹的查找元素

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

如下圖所示：

例如B+樹中查找55這個(gè)關(guān)鍵字，步驟如下：

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

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

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

3、B+樹的插入元素

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

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

2、當(dāng)插入關(guān)鍵字后結(jié)點(diǎn)的關(guān)鍵字個(gè)數(shù)大于m，需要進(jìn)行“分裂”。

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

1、若被插入關(guān)鍵字所在的結(jié)點(diǎn)，其含有關(guān)鍵字?jǐn)?shù)目小于m，則直接插入；

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

3、在第 2 種情況中，如果上移操作導(dǎo)致其雙親結(jié)點(diǎn)中關(guān)鍵字個(gè)數(shù)大于 M，則應(yīng)繼續(xù)分裂其雙親結(jié)點(diǎn)。

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

舉例：

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

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

此時(shí)該節(jié)點(diǎn)的關(guān)鍵字個(gè)數(shù)大于m，需要進(jìn)行分裂操作，并且父節(jié)點(diǎn)需要插入一個(gè)新的關(guān)鍵字：

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

此時(shí)該節(jié)點(diǎn)的關(guān)鍵字個(gè)數(shù)大于m，需要進(jìn)行分裂操作，并且父節(jié)點(diǎn)需要插入一個(gè)新的關(guān)鍵字：

父節(jié)點(diǎn)插入新的關(guān)鍵字之后，根結(jié)點(diǎn)關(guān)鍵字的個(gè)數(shù)大于m，也需要進(jìn)行分裂：

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

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

4、實(shí)際應(yīng)用

4.1、Innodb引擎

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

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

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

更多知識(shí)詳細(xì)可參考：談?wù)刴ysql的日志的用途

每個(gè)頁節(jié)點(diǎn)段、非頁節(jié)點(diǎn)段可參考如下：

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

階數(shù)計(jì)算示例：

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

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

存儲(chǔ)的計(jì)算公式：

4.2、文件系統(tǒng)

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

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

總結(jié)

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

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

最新評(píng)論