MySQL使用B+Tree當(dāng)索引的優(yōu)勢(shì)有哪些

數(shù)據(jù)庫為什么需要索引呢？

我們都是知道數(shù)據(jù)庫的數(shù)據(jù)都是存儲(chǔ)在磁盤上的，當(dāng)我們程序啟動(dòng)起來的時(shí)候，就相當(dāng)于一個(gè)進(jìn)程運(yùn)行在了機(jī)器的內(nèi)存當(dāng)中。所以當(dāng)我們程序要查詢數(shù)據(jù)時(shí)，必須要從內(nèi)存出來到磁盤里面去查找數(shù)據(jù)，然后將數(shù)據(jù)寫回到內(nèi)存當(dāng)中。但是磁盤的io效率是遠(yuǎn)不如內(nèi)存的，所有查找數(shù)據(jù)的快慢直接影響程序運(yùn)行的效率。
而數(shù)據(jù)庫加索引的主要目的就是為了使用一種合適的數(shù)據(jù)結(jié)構(gòu)，可以使得查詢數(shù)據(jù)的效率變高，減少磁盤io的次數(shù)，提升數(shù)據(jù)查找的速率，而不再是愣頭青式的全局遍歷。

那索引為啥要用B+Tree的數(shù)據(jù)結(jié)構(gòu)呢？

如果我們簡單的想的話，想要快速的查找到數(shù)據(jù)，感覺hash表是最快的，根據(jù)key，hash到某個(gè)槽位上，直接一次查找就可以準(zhǔn)確的找到數(shù)據(jù)的位置，這多快呀。但是我們?cè)谧鰳I(yè)務(wù)時(shí)，往往只需要一條的數(shù)據(jù)需求很少，大部分的需求都是根據(jù)一定的條件查詢一部分的數(shù)據(jù)，這個(gè)時(shí)候hash顯示不是很合適。

我們?cè)倏紤]樹，比如二叉樹，平衡二叉樹，紅黑樹，B樹等，他們都是二分查找，找數(shù)也快，但是不管是平衡二叉樹還是優(yōu)化后的紅黑樹，說到底他們都是二叉樹，當(dāng)節(jié)點(diǎn)多了的時(shí)候，它們的高度就會(huì)高呀，我找一個(gè)數(shù)據(jù)。根節(jié)點(diǎn)不是，那就找下一層，下一層還沒有我就再去找下一層，這樣造成的后果就是我找一個(gè)數(shù)據(jù)可能要找好幾次，而每一次都是執(zhí)行了一次磁盤的io，而我們的索引的目的就是要減少磁盤io呀，這樣設(shè)計(jì)可不行。那我們是不是把高度變矮就可以了呢？
所以我們?cè)倏紤]下B樹。首先簡單介紹下B樹的數(shù)據(jù)結(jié)構(gòu)：
首先看看B樹的定義。

1. 每個(gè)節(jié)點(diǎn)最多有m-1個(gè)關(guān)鍵字（可以存有的鍵值對(duì)）。
2. 根節(jié)點(diǎn)最少可以只有1個(gè)關(guān)鍵字。
3. 非根節(jié)點(diǎn)至少有m/2關(guān)鍵字。
4. 每個(gè)節(jié)點(diǎn)中的關(guān)鍵字都按照從小到大的順序排列，每個(gè)關(guān)鍵字的左子樹中的所有關(guān)鍵字都小于它，而右子樹中的所有關(guān)鍵字都大于它。
5. 所有葉子節(jié)點(diǎn)都位于同一層，或者說根節(jié)點(diǎn)到每個(gè)葉子節(jié)點(diǎn)的長度都相同。
6. 每個(gè)節(jié)點(diǎn)都存有索引和數(shù)據(jù)，也就是對(duì)應(yīng)的key和value。
   

所以，根節(jié)點(diǎn)的關(guān)鍵字?jǐn)?shù)量范圍：1 = k = m-1，非根節(jié)點(diǎn)的關(guān)鍵字?jǐn)?shù)量范圍：m/2 = k = m-1。

這里的m表示階數(shù)，階數(shù)表示了一個(gè)節(jié)點(diǎn)最多有多少個(gè)孩子節(jié)點(diǎn)，所以描述一顆B樹時(shí)需要指定它的階數(shù)。

我們?cè)倥e個(gè)例子來說明一下上面的概念，比如這里有一個(gè)5階的B樹，根節(jié)點(diǎn)數(shù)量范圍：1 = k = 4，非根節(jié)點(diǎn)數(shù)量范圍：2 = k = 4。

下面，我們通過一個(gè)插入的例子，講解一下B樹的插入過程，接著，再講解一下刪除關(guān)鍵字的過程。

B樹插入

插入的時(shí)候，我們需要記住一個(gè)規(guī)則：判斷當(dāng)前結(jié)點(diǎn)key的個(gè)數(shù)是否小于等于m-1，如果滿足，直接插入即可，如果不滿足，將節(jié)點(diǎn)的中間的key將這個(gè)節(jié)點(diǎn)分為左右兩部分，中間的節(jié)點(diǎn)放到父節(jié)點(diǎn)中即可。

例子：在5階B樹中，結(jié)點(diǎn)最多有4個(gè)key,最少有2個(gè)key（注意：下面的節(jié)點(diǎn)統(tǒng)一用一個(gè)節(jié)點(diǎn)表示key和value）。

插入18，70，50,40

插入22

插入22時(shí)，發(fā)現(xiàn)這個(gè)節(jié)點(diǎn)的關(guān)鍵字已經(jīng)大于4了，所以需要進(jìn)行分裂，分裂的規(guī)則在上面已經(jīng)講了，分裂之后，如下。

接著插入23，25，39

分裂，得到下面的。

所以B樹每一層的節(jié)點(diǎn)數(shù)會(huì)變多，相同的數(shù)據(jù)量的話，B樹會(huì)比二叉樹高度更低，需要的io次數(shù)就會(huì)變少，所以符合我們的索引需求。那MySQL最后為什么選擇了B+樹呢，比B樹更優(yōu)的地方在哪里呢？
我們先看看B+樹與B樹不同的地方：

• B+樹葉子節(jié)點(diǎn)包含了這棵樹的所有鍵值，非葉子節(jié)點(diǎn)不存儲(chǔ)數(shù)據(jù)，只存儲(chǔ)索引，數(shù)據(jù)都存儲(chǔ)在葉子節(jié)點(diǎn)。而B樹是每個(gè)節(jié)點(diǎn)都存有索引和數(shù)據(jù)。
• B+樹每個(gè)葉子結(jié)點(diǎn)都存有相鄰葉子結(jié)點(diǎn)的指針，葉子結(jié)點(diǎn)本身依關(guān)鍵字的大小自小而大順序鏈接。
  

如圖：

第一點(diǎn)：當(dāng)非葉子節(jié)點(diǎn)只存索引key而不存data時(shí)，就可以使得非葉子節(jié)點(diǎn)的占用空間變少，相同容量的節(jié)點(diǎn)可以存儲(chǔ)更多的索引，那同樣是三層的B+樹，階數(shù)就會(huì)變多，就會(huì)比B樹存更多的數(shù)據(jù)。
第二點(diǎn)：B+樹葉子節(jié)點(diǎn)存有相鄰葉子節(jié)點(diǎn)的指針，想要理解這個(gè)指針的好處，我們的先知道磁盤讀取數(shù)據(jù)時(shí)往往不是嚴(yán)格按需讀取，而是每次都會(huì)預(yù)讀，即使只需要一個(gè)字節(jié)，磁盤也會(huì)從這個(gè)位置開始，順序向后讀取一定長度的數(shù)據(jù)放入內(nèi)存。這樣做的理論依據(jù)是計(jì)算機(jī)科學(xué)中著名的局部性原理：

• 當(dāng)一個(gè)數(shù)據(jù)被用到時(shí)，其附近的數(shù)據(jù)也通常會(huì)馬上被使用。
• 程序運(yùn)行期間所需要的數(shù)據(jù)通常比較集中。
  

預(yù)讀的長度一般為頁（page）的整倍數(shù)。頁是計(jì)算機(jī)管理存儲(chǔ)器的邏輯塊，硬件及操作系統(tǒng)往往將主存和磁盤存儲(chǔ)區(qū)分割為連續(xù)的大小相等的塊，每個(gè)存儲(chǔ)塊稱為一頁（在許多操作系統(tǒng)中，頁得大小通常為4k），主存和磁盤以頁為單位交換數(shù)據(jù)。當(dāng)程序要讀取的數(shù)據(jù)不在主存中時(shí)，會(huì)觸發(fā)一個(gè)缺頁異常，此時(shí)系統(tǒng)會(huì)向磁盤發(fā)出讀盤信號(hào)，磁盤會(huì)找到數(shù)據(jù)的起始位置并向后連續(xù)讀取一頁或幾頁載入內(nèi)存中，然后異常返回，程序繼續(xù)運(yùn)行。

現(xiàn)在再看B+樹葉子節(jié)點(diǎn)的指針，我們就明白了它的用處，預(yù)讀的時(shí)候可以保證連續(xù)讀取的數(shù)據(jù)有序。

可能還有的同學(xué)提過B*樹，它是在B+樹基礎(chǔ)上，為非葉子結(jié)點(diǎn)也增加鏈表指針。個(gè)人覺得沒用B星樹可能是覺得沒必要吧，我們?cè)诜侨~子節(jié)點(diǎn)又不存data，data都在葉子節(jié)點(diǎn)，非葉子節(jié)點(diǎn)了鏈表指針用不上。

一些花里胡哨的概念

聚簇索引和非聚簇索引：上面我們提到B+樹的葉子節(jié)點(diǎn)存了索引key的數(shù)據(jù)data，但是mysql不同的引擎存data的選擇是不一樣的，MyISAM是將索引文件和真實(shí)的數(shù)據(jù)文件分兩個(gè)文件各種存放，索引文件中存的data是該索引key對(duì)應(yīng)的數(shù)據(jù)在數(shù)據(jù)文件中的地址值，而InnoDB則是將正式的數(shù)據(jù)存在了葉子節(jié)點(diǎn)中。所以聚簇和非聚簇就是區(qū)分葉子節(jié)點(diǎn)存的data是不是真實(shí)的（可以理解為葉子節(jié)點(diǎn)擠不擠？）

回表：回表也簡單，但是得先明白主鍵索引和普通索引，上面我們所的葉子節(jié)點(diǎn)存真實(shí)的數(shù)據(jù)，那是只有主鍵索引才是這么存的，普通索引它存的data是主鍵索引的key。那這樣我們就好理解了。比如我現(xiàn)在給一張表的name字段建了個(gè)普通索引，我想select * from table where name = 'test'，這個(gè)時(shí)候我們找到test節(jié)點(diǎn)的時(shí)候，拿到的key只是這行數(shù)據(jù)對(duì)應(yīng)的主鍵key，我們要得到整行的數(shù)據(jù)只能拿著這個(gè)key再去主鍵索引樹再找一次。這個(gè)操作就叫做回表。

最左匹配原則： 當(dāng)我們新建了一個(gè)組合索引時(shí)，比如（name+age），查詢時(shí)使用 where name = xx and age = xx時(shí)會(huì)走組合索引，而where age = xx and name =xx則不會(huì)走。這是因?yàn)镸ySQL創(chuàng)建聯(lián)合索引的規(guī)則是首先會(huì)對(duì)聯(lián)合索引的最左邊第一個(gè)字段排序，在第一個(gè)字段的排序基礎(chǔ)上，然后在對(duì)第二個(gè)字段進(jìn)行排序。

以上就是MySQL使用B+Tree當(dāng)索引有哪些優(yōu)勢(shì)的詳細(xì)內(nèi)容，更多關(guān)于MySQL使用B+Tree當(dāng)索引的優(yōu)勢(shì)的資料請(qǐng)關(guān)注腳本之家其它相關(guān)文章！