圖解:什么是 B+樹(shù) ? (查找篇)

來(lái)源：景禹

作者：景禹

前面談了 B+樹(shù)的基本概念，今日主要說(shuō)一下 B+樹(shù)的查找操作。

下面所有的查找操作都是在上面這顆 B+樹(shù)上進(jìn)行了，為此，我們先仔細(xì)觀察一下這顆B+樹(shù)（毫不隱瞞，這顆 B+樹(shù)出自于嚴(yán)蔚敏老師的數(shù)據(jù)結(jié)構(gòu)教材）。

第一點(diǎn)：B+樹(shù)中的所有數(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+ 樹(shù)中的結(jié)點(diǎn) 59 （結(jié)點(diǎn) 15、44、97、72 類似），是其子結(jié)點(diǎn) [15、44、59] 中的最大元素，也是葉子結(jié)點(diǎn) [51、59] 中的最大元素。所有的數(shù)據(jù) [10、15、21、37、44、51、59、63、72、85、91、97] 均保存在葉子結(jié)點(diǎn)之中，而根結(jié)點(diǎn) [59、97] 及內(nèi)部結(jié)點(diǎn) [15、44、59] 與 [72、97] 均不是數(shù)據(jù)本身，只是充當(dāng)控制查找記錄的媒介。

需要注意的是，根結(jié)點(diǎn)的最大元素 97 是整顆 B+樹(shù)當(dāng)中最大的元素，無(wú)論之后在葉子結(jié)點(diǎn)中插入或刪除多少元素，始終要保證最大元素在根結(jié)點(diǎn)當(dāng)中，這個(gè)講插入和刪除時(shí)還會(huì)看到。

第二點(diǎn)：每一個(gè)葉子結(jié)點(diǎn)都有指向下一個(gè)葉子結(jié)點(diǎn)的 指針，便捷之處就在于之后我們將看到的區(qū)間查找。

查詢單個(gè)元素

我們以查詢 59 為例進(jìn)行說(shuō)明。

第一次磁盤(pán) I/O ：訪問(wèn)根結(jié)點(diǎn) [59、97] ，發(fā)現(xiàn) 59 小于等于 ?[59、97] 中的 59 ，則訪問(wèn)根結(jié)點(diǎn)的第一個(gè)孩子結(jié)點(diǎn)。

第二次磁盤(pán) I/O : 訪問(wèn)結(jié)點(diǎn) [15、44、59] ，發(fā)現(xiàn) 59 大于 44 且小于等于 59 ，則訪問(wèn)當(dāng)前結(jié)點(diǎn)的第三個(gè)孩子結(jié)點(diǎn) [51、59] .

第三次磁盤(pán) I/O ：訪問(wèn)葉子結(jié)點(diǎn) [51、59] ，順序遍歷結(jié)點(diǎn)內(nèi)部，找到要查找的元素 59 .

我想你已經(jīng)注意到了和 B-樹(shù)的區(qū)別，對(duì)于 B+樹(shù)中單個(gè)元素的查找而言，每一個(gè)元素都有相同的磁盤(pán) I/O操作次數(shù)，即使查詢的元素出現(xiàn)在根結(jié)點(diǎn)中，但那只是一個(gè)充當(dāng)控制查找記錄的媒介，并不是數(shù)據(jù)本身，數(shù)據(jù)真正存在于葉子結(jié)點(diǎn)當(dāng)中，所以 B+樹(shù)中查找任何一個(gè)元素都要從根結(jié)點(diǎn)一直走到葉子結(jié)點(diǎn)才可以。

B+樹(shù)的非葉子結(jié)點(diǎn)均不存儲(chǔ) Data (即 ，官方將其稱為衛(wèi)星數(shù)據(jù)) ，所以與 B-樹(shù)相比，同樣大小的磁盤(pán)頁(yè)，B+樹(shù)的非葉子結(jié)點(diǎn)可以存儲(chǔ)更多的索引（關(guān)鍵字），這也就意味著在數(shù)據(jù)量相同的情況下，B+樹(shù)的結(jié)構(gòu)比 B-樹(shù)更加 “矮胖”，查詢時(shí)磁盤(pán) I/O 次數(shù)會(huì)更少。

注意： B-樹(shù)的查詢性能并不穩(wěn)定，對(duì)于根結(jié)點(diǎn)中關(guān)鍵字可能只有一次磁盤(pán) I/O，而對(duì)于葉子結(jié)點(diǎn)中的關(guān)鍵字需要樹(shù)的高度次磁盤(pán) I/O 操作。

比如查找上圖 B-樹(shù)中的關(guān)鍵字 59 僅需要一次磁盤(pán) I/O 操作，關(guān)鍵字 21 需要 3 次磁盤(pán) I/O，關(guān)鍵字 72 需要 2 次磁盤(pán) I/O.

B+樹(shù)所有查詢所有關(guān)鍵字的磁盤(pán) I/O 的次數(shù)都是樹(shù)的高度。

區(qū)間查詢

為了更清楚地看到 B+樹(shù)進(jìn)行區(qū)間查詢的優(yōu)勢(shì)，我們以查詢下面的 B-樹(shù)中大于等于21 ，小于等于63的關(guān)鍵字為例進(jìn)行說(shuō)明。

第一步：訪問(wèn) B-樹(shù)的根結(jié)點(diǎn) [59] ，發(fā)現(xiàn) 21 比 59 小，則訪問(wèn)根結(jié)點(diǎn)的第一個(gè)孩子 [15、44] .

第二步：訪問(wèn)結(jié)點(diǎn) ?[15、44] ，發(fā)現(xiàn) 21 大于 15 且小于 44 ，則訪問(wèn)當(dāng)前結(jié)點(diǎn)的第二個(gè)孩子結(jié)點(diǎn) [21、37] 。

第三步：訪問(wèn)結(jié)點(diǎn) [21、37] , 找到區(qū)間的左端點(diǎn) 21 ，然后從該關(guān)鍵字 21 開(kāi)始，進(jìn)行中序遍歷，依次為關(guān)鍵字 37 、44、51、59，直到遍歷到區(qū)間的右端點(diǎn) 63 為止， 不考慮中序遍歷過(guò)程的壓棧和入棧操作，磁盤(pán) I/O 次數(shù)多了 2次，即訪問(wèn)結(jié)點(diǎn) 72 和結(jié)點(diǎn) 63?并加載進(jìn)內(nèi)存。

而 B+樹(shù)進(jìn)行區(qū)間查找，簡(jiǎn)直要舒服的不要不要的。同樣是查找區(qū)間 [21,63] 之間的關(guān)鍵字。

第一步：訪問(wèn)根結(jié)點(diǎn) [59、97] , 發(fā)現(xiàn)區(qū)間的左端點(diǎn) 21 小于 59， 則訪問(wèn)第一個(gè)孩子結(jié)點(diǎn)?[15、44、59] .

第二步：訪問(wèn)結(jié)點(diǎn) [15、44、59] ?，發(fā)現(xiàn) 21 大于 15 且小于 44 ，則訪問(wèn)第二個(gè)孩子結(jié)點(diǎn) [21、37，44] .

第三步：訪問(wèn)結(jié)點(diǎn) [21、37，44] ?，找到了左端點(diǎn) 21 ，此時(shí) B+樹(shù)的優(yōu)越性就出來(lái)了，不再需要中序遍歷，而是相當(dāng)于單鏈表的遍歷，直接從左端點(diǎn) 21 開(kāi)始一直遍歷到左端點(diǎn) 63 即可，沒(méi)有任何額外的磁盤(pán) I/O 操作。

綜合來(lái)看 B+樹(shù)的優(yōu)勢(shì)就是：

1. 查找時(shí)磁盤(pán) I/O 次數(shù)更少，因?yàn)?B+樹(shù)的非葉子結(jié)點(diǎn)可以存儲(chǔ)更多的關(guān)鍵字，數(shù)據(jù)量相同的情況下，B+樹(shù)更加 “矮胖” ，效率更高。
2. B+樹(shù)查詢所有關(guān)鍵字的磁盤(pán) I/O 次數(shù)都一樣，查詢效率穩(wěn)定。
3. B+樹(shù)進(jìn)行區(qū)間查找時(shí)更加簡(jiǎn)便實(shí)用。

此外給大家推薦一篇博文 MySQL索引背后的數(shù)據(jù)結(jié)構(gòu)及算法原理（http://blog.codinglabs.org/articles/theory-of-mysql-index.html） ，其中對(duì)于MySQL 索引為什么采用 B+樹(shù)，以及InnoDB表為什么必須有主鍵，并且為什么推薦使用自增主鍵都有解釋，需要的朋友可以自提，我就不再造輪子了。