關(guān)于B+樹的使用及說明
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+樹是一種平衡的多叉搜索樹，廣泛應(yīng)用于數(shù)據(jù)庫和文件系統(tǒng)的索引結(jié)構(gòu)（如MySQL的InnoDB存儲引擎）。
核心特點
- 每個節(jié)點可以包含多個子節(jié)點（即N叉樹）。
- 所有葉子節(jié)點通過指針連接，形成一個有序鏈表。
- 內(nèi)部節(jié)點僅存儲鍵值，數(shù)據(jù)（記錄指針）僅存在于葉子節(jié)點。
1.2、B+樹與N叉樹的關(guā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直接相關(guān)，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)中廣泛應(yīng)用的核心原因。
2、B+樹的查找元素
B+樹中的所有數(shù)據(jù)均保存在葉子結(jié)點，且根結(jié)點和內(nèi)部結(jié)點均只是充當(dāng)控制查找記錄的媒介，并不代表數(shù)據(jù)本身，所有的內(nèi)部結(jié)點元素都同時存在于子結(jié)點中，是子節(jié)點元素中是最大（或最?。┰亍?/strong>
如下圖所示：
例如B+樹中查找55這個關(guān)鍵字，步驟如下：
1、在根節(jié)點中對比55和根節(jié)點中的元素[60, 85]，發(fā)現(xiàn)55<60，因此應(yīng)該在第一個結(jié)點中繼續(xù)尋找；
2、比較55和第一個節(jié)點中的元素[10, 20, 50, 60]，發(fā)現(xiàn)50<55<60，因此55應(yīng)該存在于第四個結(jié)點當(dāng)中；
3、繼續(xù)對比55和第四個結(jié)點中的元素[55, 60]，找到55，查找成功。當(dāng)然，也有查找失敗的情況，即要查找的元素并不在B+樹中。
3、B+樹的插入元素
其插入規(guī)則如下：
1、插入的操作全部都在葉子結(jié)點上進行，且不能破壞關(guān)鍵字自小而大的順序；
2、當(dāng)插入關(guān)鍵字后結(jié)點的關(guān)鍵字個數(shù)大于m，需要進行“分裂”。
B+樹的插入有四種情況：
1、若被插入關(guān)鍵字所在的結(jié)點，其含有關(guān)鍵字?jǐn)?shù)目小于m，則直接插入；
2、若被插入關(guān)鍵字所在的結(jié)點，其含有關(guān)鍵字?jǐn)?shù)目等于m，則需要將這個結(jié)點分為左右兩部分，中間的結(jié)點放到父節(jié)點中。假設(shè)其雙親結(jié)點中包含的關(guān)鍵字個數(shù)小于 m，則插入操作完成。
3、在第 2 種情況中，如果上移操作導(dǎo)致其雙親結(jié)點中關(guān)鍵字個數(shù)大于 M，則應(yīng)繼續(xù)分裂其雙親結(jié)點。
4、若插入的關(guān)鍵字比當(dāng)前結(jié)點中的最大值還大，破壞了B+樹中從根結(jié)點到當(dāng)前結(jié)點的所有索引值，此時需要及時根節(jié)點、字節(jié)點，再做葉子節(jié)點插入操作。
舉例：
1、插入關(guān)鍵字12，此時第一個葉子節(jié)點部分[10, 15]關(guān)鍵字的個數(shù)<m，可以直接插入：（紫色代表插入的元素）
2、插入95，需要插入到最后一個葉子節(jié)點部分[85, 91, 97]：
此時該節(jié)點的關(guān)鍵字個數(shù)大于m，需要進行分裂操作，并且父節(jié)點需要插入一個新的關(guān)鍵字：
3、插入40，需要插入到第二個葉子節(jié)點部分[21, 37, 44]：
此時該節(jié)點的關(guān)鍵字個數(shù)大于m，需要進行分裂操作，并且父節(jié)點需要插入一個新的關(guān)鍵字：
父節(jié)點插入新的關(guān)鍵字之后，根結(jié)點關(guān)鍵字的個數(shù)大于m，也需要進行分裂：
4、插入100，由于其值比最大值 97 還大，插入之后，從根結(jié)點到該結(jié)點經(jīng)過的所有結(jié)點中的所有值都要由 97 改為 100。（橙色為修改之后的）
修改完最大值之后，在最后一個節(jié)點處插入100：
4、實際應(yīng)用
4.1、Innodb引擎
MySQL數(shù)據(jù)表以文件方式存放在磁盤中，默認(rèn)使用共享表空間（0）存儲。
mysql使用共享表空間存儲，所有表的數(shù)據(jù)和索引會存儲在一個共享的 ibdata 文件中。表結(jié)構(gòu)以.frm文件的形式存儲在與表對應(yīng)的文件夾中。
如果使用了獨立表空間，InnoDB 會將每個表的結(jié)構(gòu)和數(shù)據(jù)存儲在獨立的 .ibd 文件中。每當(dāng)表的數(shù)據(jù)或索引被更新時，文件也會隨之變化。表的結(jié)構(gòu)仍然以.frm文件存儲。
更多知識詳細(xì)可參考：談?wù)刴ysql的日志的用途
每個頁節(jié)點段、非頁節(jié)點段可參考如下：
注意：階數(shù)由頁大?。≒age Size）決定（通常為 16KB）。
階數(shù)計算示例：
每個關(guān)鍵字（如主鍵）為 8 字節(jié)，指針為 6 字節(jié)。當(dāng)磁盤塊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)驗，希望能給大家一個參考，也希望大家多多支持腳本之家。
相關(guān)文章
mysql unix準(zhǔn)換時間格式查找指定日期數(shù)據(jù)代碼
這篇文章主要介紹了mysql unix準(zhǔn)換時間格式查找指定日期數(shù)據(jù),需要的朋友可以參考下2014-03-03
Mysql導(dǎo)入導(dǎo)出工具Mysqldump和Source命令用法詳解
Mysql本身提供了命令行導(dǎo)出工具Mysqldump和Mysql Source導(dǎo)入命令進行SQL數(shù)據(jù)導(dǎo)入導(dǎo)出工作，通過Mysql命令行導(dǎo)出工具Mysqldump命令能夠?qū)ysql數(shù)據(jù)導(dǎo)出為文本格式(txt)的SQL文件，通過Mysql Source命令能夠?qū)QL文件導(dǎo)入Mysql數(shù)據(jù)庫中，下面通過Mysql導(dǎo)入導(dǎo)出SQL實例詳解Mysqldump和Source命令的用法2012-09-09
mysql中show指令使用過程中會經(jīng)常遇到，在本文將為大家詳細(xì)介紹下其具體的使用，需要的朋友不要錯過2014-11-11
這篇文章主要介紹了MySql多表鏈接查詢詳細(xì)教程的相關(guān)資料,需要的朋友可以參考下2022-10-10
MySQL數(shù)據(jù)庫INNODB表損壞修復(fù)處理過程分享
突然收到MySQL報警，從庫的數(shù)據(jù)庫掛了，一直在不停的重啟，打開錯誤日志，發(fā)現(xiàn)有張表壞了。innodb表損壞不能通過repair table 等修復(fù)myisam的命令操作?，F(xiàn)在記錄下解決過程2013-08-08
這篇文章主要介紹了深入理解MySQL中MVCC與BufferPool緩存機制，MySQL默認(rèn)RR隔離級別就是通過該機制來保證的MVCC，更多主題相關(guān)內(nèi)容，需要的可以參考下面文章內(nèi)容介紹2022-05-05
MySQL數(shù)據(jù)庫8——數(shù)據(jù)庫中函數(shù)的應(yīng)用詳解
這篇文章主要介紹了MySQL數(shù)據(jù)庫8——數(shù)據(jù)庫中函數(shù)的應(yīng)用，文中通過示例代碼介紹的非常詳細(xì)，對大家的學(xué)習(xí)或者工作具有一定的參考學(xué)習(xí)價值，需要的朋友們下面隨著小編來一起學(xué)習(xí)學(xué)習(xí)吧2019-03-03
要讓本機（主機）連接到虛擬機上的 MySQL 數(shù)據(jù)庫,你需要確保虛擬機和主機之間的網(wǎng)絡(luò)連接正常,并且 MySQL 配置允許外部連接,本文給大家介紹了本機連接虛擬機MYSQL的操作指南,需要的朋友可以參考下2024-12-12
數(shù)據(jù)庫索引的知識點整理小結(jié),你所需要了解的都在這兒了
這篇文章主要介紹了數(shù)據(jù)庫索引的知識點整理小結(jié),你所需要了解的都在這兒了,本文給大家介紹的非常詳細(xì)，對大家的學(xué)習(xí)或工作具有一定的參考借鑒價值，需要的朋友可以參考下2020-07-07
本篇文章是對mysql與Oracle update的區(qū)別進行了詳細(xì)的分析介紹，需要的朋友參考下2013-07-07