如下圖所示：

例如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、文件系統(tǒng)

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

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

總結

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

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