Mysql資料庫索引的那些事

說起mysql的索引的資料結構，大家一定會想起B+樹，但是在談論索引資料結構之前，有個重要前提必須要清楚。就是：索引的資料結構取決于采用何種存儲引擎。

資料庫的存儲引擎有哪些？

MyISAM:索引結構是B+索引但是采用的是稀疏索引

InnoDB：索引結構也是B+索引，但是采用的是密集索引，詳細看

https://blog.csdn.net/zhaojunwei666/article/details/95892585
           

MERGE：

ARCHIVE：

MEMORY：支援hash索引頁支援B+索引

什麼是hash索引

hash索引是基于hash表實作的，隻有精确比對索引所有列的查詢才有效。對于每一行資料，存儲引擎會根據索隐列計算出一個hash值，和指向該資料行的指針。

如圖：

但是hash索引有着自身局限性：

• hash索引隻包含hash值和行指針，不存儲字段值，是以不能利用索引的值來避免讀取行
• hash索引順序不是按照索引值順序存儲的，無法進行排序
• hash索引不支援所有的部分索引列查找，因為hash值是根據索引索引列計算出來的
• hash索引隻支援等值比較查詢，如In，=，<>，不支援範圍查詢，如<,>，between
• 通路hash索引速度非常快。當出現hash沖突，存儲引擎必須周遊連結清單中的所有指針，逐行進行比較
• hash沖突很高的話，一些索引維護的代價也很高

B+索引與hash索引的比較：

• B+索引可以根據部分索引進行查找，hash索引必須用全部索引列
• B+索引存儲字段值，不用讀取行，hash索引不行
• B+索引支援範圍查詢，hash索引隻支援等值查詢
• B+索引葉子節點是排序好的連結清單，hash索引無法排序

B樹(balance tree)，B+樹：

*** B樹：**

b樹是m階的多路平衡樹，但是從理論來講，二叉樹的查找次數和速度是最小的，為什麼不用二叉樹？

原因有兩點：

1 考慮磁盤IO的影響，每個節點相當于一個磁盤頁，每次通路需要進行一次IO操作，即樹的深度為n,就需要進行n次磁盤IO，顯然存儲同樣多的資料，二叉樹明顯要比b樹高

2 因為二叉樹不是平衡樹，每次增加節點，因為沒有B樹的左旋，右旋機制，可能最後會形成連結清單，導緻時間複雜度o(n)，導緻效率太低，是以不采用二叉樹作為索引資料結構。

B樹的每個節點最多有m個子節點，m為b樹的階，一個m階的b樹有如下特點：

• 任意非葉子節點最多隻有m個孩子節點，m>2
• 根節點的兒子樹：[2,m]
• 非葉子節點的關鍵字m-1
• 所有葉子節點在同一層，非葉子節點包含資料值
• k個關鍵字把節點分成k+1，分别指向k+1個兒子

有關b樹的一些特性，注意與後面的b+樹區分：

關鍵字集合分布在整顆樹中；

任何一個關鍵字出現且隻出現在一個結點中；

搜尋有可能在非葉子結點結束；

其搜尋性能等價于在關鍵字全集内做一次二分查找；

如圖是一個3階b樹，順便講一下查詢元素5的過程：

1，第一次磁盤IO，把9所在節點讀到記憶體，把目标數5和9比較，小，找小于9對應的節點

2，第二次磁盤IO，還是讀節點到記憶體，在記憶體中把5依次和2、6比較，定位到2、6中間區域對應的節點；

3，第三次磁盤IO就不上圖了，跟第二步一樣，然後就找到了目标5。

b樹的插入删除元素操作：

比如我們要在下圖中插入元素4：

1，首先自頂向下查詢找到4應該在的位置，即3、5之間；

2，但是3階b樹的節點最多隻能有2個元素，是以把3、4、5裡面的中間元素4上移（中間元素上移是插入操作的關鍵）；

3，上一層節點加入4之後也超載了，繼續中間元素上移的操作，現在根節點變成了4、9；

4，還要滿足查找樹的性質，是以對元素進行調整以滿足大小關系，始終維持多路平衡也是b樹的優勢，最後變成這樣：

再比如我們要删除元素11：

1，自頂向下查詢到11，删掉它；

2，然後不滿足b樹的條件了，因為元素12所在的節點隻有一個孩子了，是以我們要“左旋”，元素12下來，元素13上去：

這時如果再删除15呢？很簡單，當元素個數太少以至于不能再旋轉時，12直接上去就行了。

B+樹

B+是B樹的一種變體，查詢性能更好，m階B+樹的特點:

• m階b+樹的非葉子最多有m個孩子，且非葉子節點存儲m個關鍵字，非葉子節點不存儲資料，隻用來做索引，資料都存儲在葉子節點
• 所有的葉子節點存儲了所有的關鍵字資訊，以及指向含關鍵字記錄的指針，所有葉子節點從小到大順序相連
• B+樹有兩個指針，一個指向根節點，一個指向關鍵字最小的葉子節點。
• 同一個數字在不同節點重複出現，根節點的最大關鍵字為b+樹的最大值

B+樹相當于B樹的優勢

• 非葉子節點不存儲資料，可以存儲更多的關鍵字，會使樹更加矮胖，減少磁盤IO次數，提高通路效率
• B+樹必須要查到葉子節點才能找到資料，B樹可能在非葉子節點就可以查到
• 對于查找範圍來說，b+樹隻要周遊葉子節點的連結清單，而b樹需要每次都中序周遊。