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

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

我們都是知道數(shù)據(jù)庫的數(shù)據(jù)都是存儲在磁盤上的，當我們程序啟動起來的時候，就相當于一個進程運行在了機器的內(nèi)存當中。所以當我們程序要查詢數(shù)據(jù)時，必須要從內(nèi)存出來到磁盤里面去查找數(shù)據(jù)，然后將數(shù)據(jù)寫回到內(nèi)存當中。但是磁盤的io效率是遠不如內(nèi)存的，所有查找數(shù)據(jù)的快慢直接影響程序運行的效率。
而數(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到某個槽位上，直接一次查找就可以準確的找到數(shù)據(jù)的位置，這多快呀。但是我們在做業(yè)務(wù)時，往往只需要一條的數(shù)據(jù)需求很少，大部分的需求都是根據(jù)一定的條件查詢一部分的數(shù)據(jù)，這個時候hash顯示不是很合適。

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

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

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

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

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

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

B樹插入

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

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

插入18，70，50,40

插入22

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

接著插入23，25，39

分裂，得到下面的。

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

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

如圖：

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

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

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

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

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

一些花里胡哨的概念

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

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

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

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