深入聊聊mysql索引為什么采用B+樹結構

本篇文章是mysql的進階學習，介紹一下mysql使用b+樹作為索引數據結構的原因，希望對大家有所幫助！

索引提高查詢效率，就像我們看的書，想要直接翻到某一章，是不是不用一頁一頁的翻，只需要看下目錄，根據目錄找到其所在的頁數即可。【相關推薦：mysql】

在計算機中我們需要一種數據結構來存儲這個目錄，常見數據結構有哈希表，二叉查找樹，二叉平衡樹(AVL)，紅黑樹，那為什么Innodb和MyISAM選擇b+樹呢。

1. 哈希表

哈希表就是一個數組+鏈表，用下標0，1，2，3….. 表示其數據所在的位置。如果想要在哈希表中存放數據，首先用對這個數據進行散列算法（基本的就是取模運算），假如數組長度是13 ，進行模13之后是0-12，正好對應的數據的下標，如果計算出的下標一樣的，就會在下標位置跟上鏈表。

缺點：

1. 利用hash存儲需要將所有的數據文件添加到內存，比較消耗內存空間。
2. hash的查找是等值查詢，速度很快，但是各個數據間沒有范圍規律，但在實際工作中更多的是范圍查詢，hash就不太合適了。

不能直接說mysql不使用哈希表，而是要根據存儲引擎來確定的，Memory存儲引擎使用的就是哈希表

2. 二叉查找樹

缺點：

1. 如圖，極端情況可能會出現傾斜的問題，最后變成鏈表結構。
2. 造成樹節點過深，從而增加查找的IO，而現在IO就是查找的瓶頸

3. 二叉平衡樹-AVL

為了保持樹的平衡，避免出現數據傾斜，需要進行旋轉操作，通過左旋或者右旋最終保持最長子樹和最短子樹長度不能超過1，如果超過1就不是嚴格意義上AVL樹了

缺點：

1.當數據量很大的時候，為了保持平衡，需要進行1-n次的旋轉，這個旋轉是比較浪費性能的，插入和刪除效率極低，查詢效率很高。

2. 只有兩個分支，數據量大的時候樹的深度依然很深。

4. 紅黑樹

最長子樹的不能超過最短子樹的2倍，通過變色和旋轉，在插入和查詢上做了平衡

紅黑樹是avl樹的變種，損失了部分查詢性能來提高插入性能。

缺點：

同樣是只有兩個分支，數據量大的時候深度依然會很深

以上三種二叉樹，隨著數據的增多，最終都會出現節點過多的情況，而且他們有且僅有2個分支，那么IO的次數一樣很多.

怎么解決僅有2個分支而且深度過深，這就有了B樹，增加分支

5. B-Tree

1. 首先不讀B減樹，讀B樹
2. 所有鍵值分布在整棵樹中。
3. 搜索有可能在非葉子結點結束，在關鍵字全集內做一次查找，性能逼近二分查找。
4. 每個結點最多擁有m個子樹。
5. 根節點至少有2個子樹。
6. 分支節點至少擁有m/2棵子樹(除根節點和葉子節點外都是分支節點)。
7. 所有葉子節點都在同一層，每個節點最多可以有m-1個key,并且以升序排列

如上圖：（圖中只是畫出來一部分，實際上沒有限制的，不止p1,p2,p3）

每個節點占用一個磁盤塊，一個節點上有兩個升序排列的關鍵字和三個指向子樹根節點的指針，指針存儲的是子節點所在的磁盤塊地址。兩個關鍵詞劃分成的三個范圍域對應三個指針指向的子樹的數據的范圍域。以根節點為例，關鍵字為16和34，p1指針指向的子樹的數據范圍小于16，p2指針指向的子樹的數據范圍為16-34，p3指針指向的子樹的數據范圍大于34。

查找關鍵字28的過程：

1. 根據根節點找到磁盤塊1，讀到內存中。【第一次磁盤I/O操作】
2. 比較關鍵字28在區間(16，34)，找到磁盤塊1的指針p2。
3. 根據p2指針找到磁盤塊3，讀到內存。【第二次磁盤I/O操作】
4. 比較關鍵字28在區間(25，31)，找到磁盤塊3的指針p2。
5. 根據指針p2找到磁盤塊8，讀到內存。【第三次磁盤I/O操作】
6. 在磁盤塊8中的關鍵字列表中找到關鍵字28，結束。

缺點：

1. 每個節點都有key，同時包含data，而每個頁存儲空間是有限的，如果data很大的話會導致每個節點能存儲的key的數量變小。
2. 當存儲的數據量很大的時候會導致深度變大，增加查詢磁盤的io次數，進而影響查詢性能。

6. B+樹

B+樹是在B樹的基礎上做的一種優化，變化如下：

1. B+樹每個節點可以包含更多的節點，這個做的原因有兩個，第一個原因是為了降低樹的高度，第二個原因是將數據范圍變成多個區間，區間越多，數據檢索越快。
2. 非葉子節點只存儲key，葉子節點存儲key和數據。
3. 葉子節點兩兩指針互相連接(符合磁盤預讀的特性)，順序查詢性能更高。

如上圖： 在B+樹上有兩個頭指針，一個指向根節點，另一個指向關鍵字的最小葉子節點，而且所有葉子節點(及數據節點)之間是一種鏈式環結構，因此可以對B+樹進行兩種查找運算：一種是對于主鍵的范圍查找和分頁查找，另一種是從根節點開始的隨機查找。

InnoDB和MyISAM中索引上的差異

1. InnoDB-主鍵索引

葉子節點存儲的是具體的行數據

2. InnoDB-非主鍵索引

非主鍵索引的葉子節點存儲的是主鍵值（所以查詢數據基本要回表）

3. MyISAM

葉子節點存儲的是行數據的地址，額外需要一次尋址，多一次IO

總結：為什么mysql使用的是B+樹

準確的表述：為什么mysql的InnoDB和MyISAM存儲引擎的索引使用的是B+樹

• hash表，等值查詢是很快的，但是不滿足常用的范圍查找且相鄰的兩個值之間沒有關系，而且hash比較消耗內存。

• 二叉樹/平衡二叉樹/紅黑樹等都是有且僅有2個分支，共性就是數據量大的時候樹的深度變深，增加IO的次數。

• B樹會在節點上存儲數據，這樣一頁存放的key的數量就會減少，增加樹的深度。

• B+樹中非葉子節點去除了數據，這樣就會增加一頁中key的數量，而且葉子節點之間是通過鏈表相連，有利于范圍查找和分頁。

原文地址：https://juejin.cn/post/6994810803643744269

作者：紀先生

更多編程相關知識，請訪問：mysql！！

以上就是深入聊聊