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

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

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

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

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

這個(gè)時(shí)候,Mysql的開發(fā)人員就會(huì)為了解決用戶的查詢性能問題,開始選擇合適的數(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這種等值匹配來說,性能相當(dāng)?shù)母?可以說無人能及.但是對(duì)于范圍查詢來說,Hash就有點(diǎn)捉襟見肘了,Hash沒辦法做到用O(1)的復(fù)雜度來進(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樹是如何存儲(chǔ)數(shù)據(jù)的.這里給出一張圖片:

我們現(xiàn)在以聚簇索引來舉例,圖中的數(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è)購?qiáng)調(diào)一下B Tree和B+ Tree的重要區(qū)別:

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

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

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

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

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

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

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

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

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

最新評(píng)論