Mysql索性為什麼要用B+Tree當索引

資料庫為什麼需要索引呢？

我們都是知道資料庫的資料都是儲存在磁碟上的，當我們程式啟動起來的時候，就相當於一個程序執行在了機器的記憶體當中。所以當我們程式要查詢資料時，必須要從記憶體出來到磁盤裡面去查詢資料，然後將資料寫回到記憶體當中。但是磁碟的io效率是遠不如記憶體的，所有查詢資料的快慢直接影響程式執行的效率。

而資料庫加索引的主要目的就是為了使用一種合適的資料結構，可以使得查詢資料的效率變高，減少磁碟io的次數，提升資料查詢的速率，而不再是愣頭青式的全域性遍歷。

那索引為啥要用B+Tree的資料結構呢？

如果我們簡單的想的話，想要快速的查詢到資料，感覺hash表是最快的，根據key，hash到某個槽位上，直接一次查詢就可以準確的找到資料的位置，這多快呀。但是我們在做業務時，往往只需要一條的資料需求很少，大部分的需求都是根據一定的條件查詢一部分的資料，這個時候hash顯示不是很合適。

我們再考慮樹，比如二叉樹，平衡二叉樹，紅黑樹，B樹等，他們都是二分查詢，找數也快，但是不管是平衡二叉樹還是最佳化後的紅黑樹，說到底他們都是二叉樹，當節點多了的時候，它們的高度就會高呀，我找一個數據。根節點不是，那就找下一層，下一層還沒有我就再去找下一層，這樣造成的後果就是我找一個數據可能要找好幾次，而每一次都是執行了一次磁碟的io，而我們的索引的目的就是要減少磁碟io呀，這樣設計可不行。那我們是不是把高度變矮就可以了呢？

所以我們再考慮下B樹。首先簡單介紹下B樹的資料結構：

首先看看B樹的定義。

每個節點最多有m-1個關鍵字（可以存有的鍵值對）。

根節點最少可以只有1個關鍵字。

非根節點至少有m/2關鍵字。

每個節點中的關鍵字都按照從小到大的順序排列，每個關鍵字的左子樹中的所有關鍵字都小於它，而右子樹中的所有關鍵字都大於它。

所有葉子節點都位於同一層，或者說根節點到每個葉子節點的長度都相同。

每個節點都存有索引和資料，也就是對應的key和value。

所以，根節點的

關鍵字

數量範圍： 1 <= k <= m-1 ，非根節點的

關鍵字

數量範圍： m/2 <= k <= m-1 。

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

我們再舉個例子來說明一下上面的概念，比如這裡有一個5階的B樹，根節點數量範圍：1 <= k <= 4，非根節點數量範圍：2 <= k <= 4。

下面，我們透過一個插入的例子，講解一下B樹的插入過程，接著，再講解一下刪除關鍵字的過程。

1。2 B樹插入

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

例子：在5階B樹中，結點最多有4個key，最少有2個key（注意：下面的節點統一

用一個節點表示key和value

）。

插入18，70，50，40

插入22

插入22時，發現這個節點的關鍵字已經大於4了，所以需要進行分裂，分裂的規則在上面已經講了，分裂之後，如下。

接著插入23，25，39

分裂，得到下面的。

所以B樹每一層的節點數會變多，相同的資料量的話，B樹會比二叉樹高度更低，需要的io次數就會變少，所以符合我們的索引需求。那MySQL最後為什麼選擇了B+樹呢，比B樹更優的地方在哪裡呢？

我們先看看B+樹與B樹不同的地方：

B+樹葉子節點包含了這棵樹的所有鍵值

，非葉子節點不儲存資料，只儲存索引，資料都儲存在葉子節點。而B樹是每個節點都存有索引和資料。

B+樹每個葉子結點都存有相鄰葉子結點的指標，葉子結點本身依關鍵字的大小自小而大順序連結。

如圖：

第一點：當非葉子節點只存索引key而不存data時，就可以使得非葉子節點的佔用空間變少，相同容量的節點可以儲存更多的索引，那同樣是三層的B+樹，階數就會變多，就會比B樹存更多的資料。

第二點：B+樹葉子節點存有相鄰葉子節點的指標，想要理解這個指標的好處，我們的先知道磁碟讀取資料時往往不是嚴格按需讀取，而是每次都會

預讀

，即使只需要一個位元組，磁碟也會從這個位置開始，順序向後讀取一定長度的資料放入記憶體。這樣做的理論依據是計算機科學中著名的區域性性原理：

當一個數據被用到時，其附近的資料也通常會馬上被使用。

程式執行期間所需要的資料通常比較集中。

預讀的長度一般為頁（page）的整倍數。頁是計算機管理儲存器的邏輯塊，硬體及作業系統往往將主存和磁碟儲存區分割為連續的大小相等的塊，每個儲存塊稱為一頁（在許多作業系統中，頁得大小通常為4k），主存和磁碟以頁為單位交換資料。當程式要讀取的資料不在主存中時，會觸發一個缺頁異常，此時系統會向磁碟發出讀盤訊號，磁碟會找到資料的起始位置並

向後連續讀取

一頁或幾頁載入記憶體中，然後異常返回，程式繼續執行。

現在再看B+樹葉子節點的指標，我們就明白了它的用處，預讀的時候可以保證連續讀取的資料有序。

可能還有的同學提過B*樹，它是在B+樹基礎上，為非葉子結點也增加連結串列指標。個人覺得沒用B星樹可能是覺得沒必要吧，我們在非葉子節點又不存data，data都在葉子節點，非葉子節點了連結串列指標用不上。

一些花裡胡哨的概念

聚簇索引和非聚簇索引：上面我們提到B+樹的葉子節點存了索引key的資料data，但是mysql不同的引擎存data的選擇是不一樣的，MyISAM是將索引檔案和真實的資料檔案分兩個檔案各種存放，索引檔案中存的data是該索引key對應的資料在資料檔案中的地址值，而InnoDB則是將正式的資料存在了葉子節點中。所以聚簇和非聚簇就是區分葉子節點存的data是不是真實的（可以理解為葉子節點擠不擠？）

回表：回表也簡單，但是得先明白主鍵索引和普通索引，上面我們所的葉子節點存真實的資料，那是隻有主鍵索引才是這麼存的，普通索引它存的data是主鍵索引的key。那這樣我們就好理解了。比如我現在給一張表的name欄位建了個普通索引，我想select * from table where name = ‘test’，這個時候我們找到test節點的時候，拿到的key只是這行資料對應的主鍵key，我們要得到整行的資料只能拿著這個key再去主鍵索引樹再找一次。這個操作就叫做回表。

最左匹配原則：當我們新建了一個組合索引時，比如（name+age），查詢時使用 where name = xx and age = xx時會走組合索引，而where age = xx and name =xx則不會走。這是因為MySQL建立聯合索引的規則是首先會對聯合索引的最左邊第一個欄位排序，在第一個欄位的排序基礎上，然後在對第二個欄位進行排序。