從實際場景出發(fā)

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

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

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

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

這個時候,Mysql的開發(fā)人員就會為了解決用戶的查詢性能問題,開始選擇合適的數(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ù)雜度,對于類似于select * from t where id = 3這種等值匹配來說,性能相當(dāng)?shù)母?可以說無人能及.但是對于范圍查詢來說,Hash就有點捉襟見肘了,Hash沒辦法做到用O(1)的復(fù)雜度來進(jìn)行范圍查詢,因為這點,Hash是不適合作為底層索引的實現(xiàn)的.

使用B Tree還是B+ Tree

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

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

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

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

B+ Tree的重要特點是:

• 只有葉子節(jié)點才會存放整行數(shù)據(jù),而非葉子節(jié)點只存儲主鍵值,用于向下搜索

• 葉子節(jié)點冗余了所有的主鍵值,并存儲行數(shù)據(jù),并且每個節(jié)點之間用雙向鏈表進(jìn)行連接

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

在這里,我們再強(qiáng)調(diào)一下B Tree和B+ Tree的重要區(qū)別:

• B Tree的每個節(jié)點都存儲行數(shù)據(jù),而B+ Tree只有葉子節(jié)點存放行數(shù)據(jù).
• B Tree因為每個節(jié)點都存儲行數(shù)據(jù),所以沒有必要在非葉子節(jié)點再冗余任何數(shù)據(jù).B+ Tree因為只有葉子節(jié)點存儲行數(shù)據(jù),所以需要在最后一層冗余所有的主鍵值,并存儲行數(shù)據(jù),且節(jié)點之間用鏈表進(jìn)行連接.

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

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

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

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

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

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

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

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

所以整體上來看,B+ Tree是更好的選擇.

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

最新評論