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樹的插入過程，接著，再講解一下刪除關鍵字的過程。
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創建聯合索引的規則是首先會對聯合索引的最左邊第一個字段排序，在第一個字段的排序基礎上，然後在對第二個字段進行排序。
以上就是MySQL使用B+Tree當索引有哪些優勢的詳細內容，更多關於MySQL使用B+Tree當索引的優勢的資料請關註WalkonNet其它相關文章！