快捷導(dǎo)航

淺談Mysql使用B+樹(shù)來(lái)實(shí)現(xiàn)索引的原因

更新時(shí)間：2023年05月21日 09:39:14 作者：JL8

這篇文章,主要來(lái)探討一下為什么Mysql使用B+樹(shù)來(lái)實(shí)現(xiàn)索引,這里討論的目標(biāo)是Mysql的InnoDB存儲(chǔ)引擎.可以想象一下,如果你是Mysql的開(kāi)發(fā)人員,你會(huì)怎么去選擇合適的數(shù)據(jù)結(jié)構(gòu)呢，感興趣的小伙伴跟著小編一起來(lái)探討吧

從實(shí)際場(chǎng)景出發(fā)

任何數(shù)據(jù)結(jié)構(gòu)都是為了解決特定問(wèn)題而產(chǎn)生的,那么如果一個(gè)用戶使用Mysql,通常會(huì)有哪些需求呢?我們可以很容易的想到最簡(jiǎn)單的需求:

通過(guò)id或者其他列值進(jìn)行匹配查詢
通過(guò)id進(jìn)行范圍查詢

用戶肯定希望查詢的性能越高越好,對(duì)于一個(gè)表來(lái)說(shuō),如果能直接通過(guò)索引來(lái)查詢到數(shù)據(jù),不必進(jìn)行全表掃描,那就再好不過(guò)了.

選擇合適的數(shù)據(jù)結(jié)構(gòu)

這個(gè)時(shí)候,Mysql的開(kāi)發(fā)人員就會(huì)為了解決用戶的查詢性能問(wèn)題,開(kāi)始選擇合適的數(shù)據(jù)結(jié)構(gòu).能想到的備選方案可能有Hash,B Tree,B+ Tree這三種數(shù)據(jù)結(jié)構(gòu).

如果使用Hash作為索引的數(shù)據(jù)結(jié)構(gòu)

Hash能提供O(1)的查詢復(fù)雜度,對(duì)于類似于select * from t where id = 3這種等值匹配來(lái)說(shuō),性能相當(dāng)?shù)母?可以說(shuō)無(wú)人能及.但是對(duì)于范圍查詢來(lái)說(shuō),Hash就有點(diǎn)捉襟見(jiàn)肘了,Hash沒(méi)辦法做到用O(1)的復(fù)雜度來(lái)進(jìn)行范圍查詢,因?yàn)檫@點(diǎn),Hash是不適合作為底層索引的實(shí)現(xiàn)的.

使用B Tree還是B+ Tree

那么可選的方案現(xiàn)在只剩下B Tree和B+ Tree.因?yàn)檫@兩者的數(shù)據(jù)結(jié)構(gòu)有點(diǎn)相似,所以在這兩個(gè)數(shù)據(jù)結(jié)構(gòu)之間進(jìn)行選擇時(shí),最好是將兩者放在一起對(duì)比,才能更清楚的知道哪種才是更好的數(shù)據(jù)結(jié)構(gòu),.

首先我們應(yīng)該清楚B樹(shù)是如何存儲(chǔ)數(shù)據(jù)的.這里給出一張圖片:

我們現(xiàn)在以聚簇索引來(lái)舉例,圖中的數(shù)字代表主鍵值,后面的*代表該位置是存放實(shí)際的行數(shù)據(jù)的.每個(gè)節(jié)點(diǎn)的左指針指向下一級(jí)的節(jié)點(diǎn),并且左邊指向的節(jié)點(diǎn)的主鍵值大小比上一級(jí)的小,右邊指向的節(jié)點(diǎn)的主鍵值比上一級(jí)的大.B Tree的一個(gè)重要特點(diǎn)是在每一個(gè)節(jié)點(diǎn)都存儲(chǔ)了完整的行數(shù)據(jù).

B+ Tree存儲(chǔ)數(shù)據(jù)的方式是這樣的:

B+ Tree的重要特點(diǎn)是:

只有葉子節(jié)點(diǎn)才會(huì)存放整行數(shù)據(jù),而非葉子節(jié)點(diǎn)只存儲(chǔ)主鍵值,用于向下搜索
葉子節(jié)點(diǎn)冗余了所有的主鍵值,并存儲(chǔ)行數(shù)據(jù),并且每個(gè)節(jié)點(diǎn)之間用雙向鏈表進(jìn)行連接

在圖中的12這個(gè)節(jié)點(diǎn)中,后面是指向24這個(gè)節(jié)點(diǎn)的,在圖中被省略了.

在這里,我們?cè)購(gòu)?qiáng)調(diào)一下B Tree和B+ Tree的重要區(qū)別:

B Tree的每個(gè)節(jié)點(diǎn)都存儲(chǔ)行數(shù)據(jù),而B(niǎo)+ Tree只有葉子節(jié)點(diǎn)存放行數(shù)據(jù).
B Tree因?yàn)槊總€(gè)節(jié)點(diǎn)都存儲(chǔ)行數(shù)據(jù),所以沒(méi)有必要在非葉子節(jié)點(diǎn)再冗余任何數(shù)據(jù).B+ Tree因?yàn)橹挥腥~子節(jié)點(diǎn)存儲(chǔ)行數(shù)據(jù),所以需要在最后一層冗余所有的主鍵值,并存儲(chǔ)行數(shù)據(jù),且節(jié)點(diǎn)之間用鏈表進(jìn)行連接.

理解了這兩者的區(qū)別之后,我們來(lái)考慮一下針對(duì)實(shí)際場(chǎng)景,哪個(gè)數(shù)據(jù)結(jié)構(gòu)才是更好的選擇.首先,我們考慮一下等值查詢,對(duì)于B Tree來(lái)說(shuō),從根節(jié)點(diǎn)的主鍵值開(kāi)始進(jìn)行比較,根據(jù)左小右大的特點(diǎn),可以在某個(gè)層級(jí)定位到整行數(shù)據(jù)并返回.對(duì)于B+ Tree來(lái)說(shuō),也是從根節(jié)點(diǎn)開(kāi)始進(jìn)行比較,不過(guò)最終必須定位到葉子節(jié)點(diǎn)才能獲取到需要的數(shù)據(jù).所以在等值查詢這個(gè)場(chǎng)景下,B Tree看起來(lái)比B+ Tree來(lái)得好.

那么考慮一下范圍查詢,比如B Tree來(lái)說(shuō),查詢數(shù)據(jù)跟等值查詢的模式差不多,只不過(guò)需要掃描到多個(gè)層級(jí)的節(jié)點(diǎn).舉個(gè)例子,如果在上圖中尋找主鍵大于等于10且小于等于24的行數(shù)據(jù).

首先從根節(jié)點(diǎn)12開(kāi)始,12是滿足條件的,所以獲取它的行數(shù)據(jù),12后面的同級(jí)節(jié)點(diǎn)24也符合要求,所以也符合要求.
從12的左指針找到下一個(gè)節(jié)點(diǎn),第一個(gè)節(jié)點(diǎn)是8,不符合要求,之后向后找到它的同級(jí)節(jié)點(diǎn)10,符合要求,后面沒(méi)有其他節(jié)點(diǎn)了,結(jié)束.
節(jié)點(diǎn)12的右指針(節(jié)點(diǎn)24的左指針)沒(méi)有指向任何數(shù)據(jù),所以無(wú)需再找到下一個(gè)節(jié)點(diǎn),所有可能的節(jié)點(diǎn)都查詢過(guò)了,查詢結(jié)束.

我們可以從這個(gè)過(guò)程中看到,范圍查詢需要從根節(jié)點(diǎn)出發(fā),然后可能要找到它的下一級(jí)節(jié)點(diǎn),直到找到所有符合的數(shù)據(jù).

對(duì)于B+ Tree來(lái)說(shuō),尋找主鍵大于等于10且小于等于24的行數(shù)據(jù)的流程是這樣的:

從根節(jié)點(diǎn)12向左找到下一級(jí)的10這個(gè)節(jié)點(diǎn),從10的左指針找到10所在的葉子節(jié)點(diǎn),因?yàn)槿~子節(jié)點(diǎn)是鏈表結(jié)構(gòu),那么可以從這個(gè)葉子節(jié)點(diǎn)的指針一直往后定位到24這個(gè)節(jié)點(diǎn),然后返回這中間的所有數(shù)據(jù).

實(shí)際上數(shù)據(jù)最終都是存儲(chǔ)到磁盤(pán)上的,對(duì)于Mysql來(lái)說(shuō),數(shù)據(jù)是以頁(yè)為單位來(lái)存儲(chǔ)數(shù)據(jù),通常為4KB,在上面的圖中,我們可以理解成每一個(gè)大的長(zhǎng)方形框是一個(gè)頁(yè),而每個(gè)頁(yè)里面存放了很多節(jié)點(diǎn),對(duì)于B Tree來(lái)說(shuō),每個(gè)頁(yè)的節(jié)點(diǎn)都存放整行數(shù)據(jù),對(duì)于B+ Tree來(lái)說(shuō),非葉子頁(yè)的節(jié)點(diǎn)只存放id,也被稱為索引頁(yè)，而葉子節(jié)點(diǎn)存放整行數(shù)據(jù).對(duì)于頁(yè)的讀取,就涉及到IO操作,要知道IO讀取數(shù)據(jù)的速度比從內(nèi)存讀取數(shù)據(jù)要慢得多,通常讀取頁(yè)的時(shí)間在10ms左右.

以范圍查詢?yōu)槔?我們從IO的角度來(lái)概括一下B Tree和B+ Tree的區(qū)別.對(duì)于B Tree而言,讀取根節(jié)點(diǎn)需要一次IO操作,加載出頁(yè)之后,當(dāng)前頁(yè)的數(shù)據(jù)可能只有部分符合要求,然后根據(jù)頁(yè)的指針再進(jìn)行IO操作,找到另外的頁(yè),整個(gè)過(guò)程需要更多的IO操作,并且因?yàn)槊看巫x取的頁(yè)并不是所有數(shù)據(jù)都滿足要求,所以這種方式被稱為隨機(jī)IO.那么對(duì)于B+ Tree而言,也需要從根節(jié)點(diǎn)向下查詢,這其中也涉及到隨機(jī)IO,但定位到需要的葉子節(jié)點(diǎn)后,讀取頁(yè)時(shí)只需要根據(jù)鏈表來(lái)定位到下一個(gè)頁(yè),每次讀取的頁(yè)大概率都是符合要求的數(shù)據(jù),這種方式被稱為順序IO.所以在范圍查詢中,B Tree需要更多的IO操作,這樣就需要耗費(fèi)更多的時(shí)間.如果對(duì)隨機(jī)IO和順序IO不是很理解,文末有個(gè)參考資料可以去看一下.

所以整體上來(lái)看,B+ Tree是更好的選擇.

以上就是淺談Mysql使用B+樹(shù)來(lái)實(shí)現(xiàn)索引的原因的詳細(xì)內(nèi)容，更多關(guān)于MySQL B+樹(shù)索引的資料請(qǐng)關(guān)注腳本之家其它相關(guān)文章！

您可能感興趣的文章: