在數據庫中，如果索引太多，應用程序的性能可能會受到影響，如果索引太少，又會對查詢性能產生影響。所以，我們要追求兩者的一個平衡點，足夠多的索引帶來查詢性能提高，又不因為索引過多導致修改數據等操作時負載過高。 文章會從，B+樹索引，索引的分類，哈希索引，全文索引，這個幾個方面講解

B+樹索引

• 索引的查找
• 索引的插入
• 索引的刪除

索引的分類

• 聚集索引
• 輔助索引
• 聯合索引
• 覆蓋索引

哈希索引

• 哈希算法
• 自適應哈希索引

全文索引

• 倒排索引
• 全文檢索索引緩存
• 全文索引的一些限制

InnoDB支持3種常見索引，我們接下來要詳細講解的就是 B+ 樹索引，哈希索引，全文索引。

B+樹索引

1、B+樹中的B不是代表的二叉（Binary） ，而是代表平衡（Balance），因為B+樹是從最早的平衡二叉樹演化而來，但是B+樹不是一個二叉樹。

2、B+樹是為磁盤或其他直接存取輔助設備設計的一種平衡查找樹，在B+樹中，所有的記錄節點都是按照鍵值大小順序存在同一層的葉子節點，由葉子節點指針進行相連。

3、B+樹在數據庫中的特點就是高扇出，因此在數據庫中B+樹的高度一般都在2~4層，這也就是說查找一個鍵值記錄時，最多只需要2到4次IO,當前的機械硬盤每秒至少可以有100次IO，2~4次IO意味著查詢時間只需要0.02~0.04秒。

4、B+樹索引并不能找到一個給定鍵值的具體行，B+樹索引能找到的只是被查找的鍵值所在行的頁，然后數據庫把頁讀到內存，再內存中進行查找，最后找到要查找的數據。

5、數據庫中B+樹索引可以分為，聚集索引和非聚集索引，但是不管是聚集索引還是非聚集索引，其內部都是B+樹實現的，即高度是平衡的，葉子節點存放著所有的數據，聚集索引和非聚集索引不同的是，葉子節點是否存儲的是一整行信息。每張表只能有一個聚集索引。

6、B+樹的每個數據頁（葉子節點）是通過一個雙向鏈表進行鏈接，數據頁上的數據的順序是按照主鍵順序存儲的。

先來看一個B+樹，其高度為2，每頁可以放4條記錄，扇出為5。

圖：一顆高度為2的B+樹

索引的查找

B+樹索引使用二分法查找，也稱折半查找法，基本思想就是：將記錄有序化（遞增或遞減）排列，在超找過程中采用跳躍式方式查找，既先以有序數列的中心點位置比較對象，如果要查找的元素小于該元素的中心點元素，則將待查找的元素縮小為左半部分，否則為右半部分，通過一次比較，將查找區間縮小一半。

如圖所示，從有序列表中查找 48，只需要3步：

圖：二分法查找

索引的插入

B+樹的查找速度很快，但是維護一顆平衡的B+樹代價就是非常大的，通常來說，需要1次或者多次左旋右旋來保證插入后樹的平衡性。

B+樹的插入為了保持樹的平衡，需要做大量的頁（葉子節點）的拆分，頁的存儲基本都在磁盤，頁的拆分意味著磁盤的操作，所以應該盡量減少頁的拆分，在采用自增長ID，作為主鍵，會大量的減少頁的拆分，提升的性能。

B+樹 插入的三種情況

Leaf Page滿Index Page滿操作

No	No	直接將記錄插入葉子節點
Yes	No	1、拆分Leaf Page 2、將中間的節點放入到Index Page中 3、小于中間節點的記錄放左邊 4、大于或等于中間節點的記錄放右邊
Yes	Yes	1、拆分Leaf Page 2、小于中間節點的記錄放左邊 3、大于或等于中間節點的記錄放右邊 4、拆分Index Page 5、小于中間節點的記錄放左邊 6、大于中間節點的記錄放右邊 7、中間節點放入上一層 Index Page

圖：一顆高度為2的B+樹

我們用實例來分析B+樹的插入。

（1）我們插入28這個鍵值，發現當前Leaf Page和Index Page都沒有滿，我們直接插入就可以了。

（2）這次我們再插入一條70這個鍵值，這時原先的Leaf Page已經滿了，但是Index Page還沒有滿，符合表（B+樹 插入的三種情況）的第二種情況，這時插入Leaf Page后的情況為50、55、60、65、70。我們根據中間的值60拆分葉節點。將中間節點放入到Index Page中。

（3）因為圖片顯示的關系，這次我沒有能在各葉節點加上雙向鏈表指針。最后我們來插入記錄95，這時符合表（B+樹 插入的三種情況）討論的第三種情況，即Leaf Page和Index Page都滿了，這時需要做兩次拆分。

可以看到，不管怎么變化，B+樹總是會保持平衡。但是為了保持平衡，對于新插入的鍵值可能需要做大量的拆分頁（split）操作，而B+樹主要用于磁盤，因此頁的拆分意味著磁盤的操作，應該在可能的情況下盡量減少頁的拆分。因此，B+樹提供了旋轉（rotation）的功能。

索引的刪除

B+樹使用填充因子（fill factor） 來控制樹的刪除變化，50%是填充因子可設的最小值，B+樹的刪除也同樣必須保證刪除后樹的平衡性，刪除的過程中會涉及，合并葉子節或兄弟節點，但是都是為了保持樹的平衡。

索引的分類

在了解B+樹索引的本質和實現后，我們看看索引分為幾類，聚集索引，輔助索引，聯合索引，覆蓋索引

聚集索引

就是按照每張表的主鍵構造一顆B+樹，同時葉子節點存儲整張表的行記錄數，也將聚集索引的葉子節點成為“數據頁”，聚集索引的特性決定了表中的行記錄數據也是索引的一部分。同B+樹數據結構一樣，每個數據頁都通過一個雙向鏈表進行鏈接。

數據頁只能按照一顆B+樹進行排序，因此每張表只能有一個聚集索引，由于數據頁定義了邏輯順序，聚集索引能夠很快的在數據頁訪問指針進行范圍的查找數據。

聚集索引在物理上不是連續的，在邏輯上是連續的，前面已經說過是通過雙向鏈表進行維護，物理存儲可以不按照主鍵順序存儲。

輔助索引

輔助索引（也稱非聚集索引），葉子節點并不包含行記錄的全部數據。葉子節點除了包含鍵值外，每個葉子節點還包含了一個書簽，該書簽告訴InnoDB 存儲引擎可以從哪里找到輔助索引相對應行的記錄。因此InnoDB 存儲引擎的輔助索引的書簽就是相應整行數據的聚集索引鍵。

一個表中可以有多個輔助索引。例如，一個輔助索引樹需要遍歷3次才能找到主鍵索引，如果聚集索引樹的高為同樣為3，那么它還需要對聚集索引樹進行三次查找，最終才能找到一個完整的數據頁，因此一共需要6次IO訪問才能得到最終的數據頁。

聯合索引

聯合索引是指對表上多個列進行建立索引，聯合索引本質還是一顆B+樹，不同的是索引的鍵值數量不是1個，而是大于等于2。聯合索引的鍵值在B+樹中也是有序的，通過葉子節點可以在邏輯的順序上讀出所有數據。

覆蓋索引

InnoDB存儲引擎支持覆蓋索引（或稱索引覆蓋），就是從輔助索引中就可以直接得到查詢的記錄，而不需要再次查詢聚集索引中的記錄。使用覆蓋索引的好處就是，輔助索引不包括整行記錄的所有信息，所以覆蓋索引的大小要小于聚集索引，因此可以減少IO操作。

通俗的解釋：

覆蓋索引是非聚集組合索引的一種形式，它包括在查詢里的Select、Join和Where子句用到的所有列（即建立索引的字段正好是覆蓋查詢語句[select子句]與查詢條件[Where子句]中所涉及的字段，也就是索引包含了查詢正在查找的所有數據）

哈希索引

學習哈希索引之前，我們先了解一些基礎的知識：哈希算法。哈希算法是一種常用的算法，時間復雜度為O(1)。它不僅應用在索引上，各個數據庫應用中也都會使用。

哈希算法

InnoDB存儲引擎使用哈希算法來對字典進行查找，哈希碰撞采用轉鏈表解決，哈希函數采用除法散列方式。

例如：當前參數InnoDB_buffer_pool_size大小為10M，則共有640個16k的頁，對于緩沖頁內存的哈希表來說，需要分配640×2=1280個槽，但是由于1280不是質數，所以需要取比1280更大的一點的質數，應該是1399，所以啟動的時候，會分配1399個槽的哈希表，用來哈希查詢所在的緩沖池中的頁。

InnoDB存儲引擎是通過除法散列到1399個其中的一個槽中。

自適應哈希索引

自適應哈希索引采用之前說的哈希表方式，不同的是哈希索引對字典類型的等值查找非常快，對范圍查詢就無能為力了。

所以說哈希索引只能用于搜索等值查詢，范圍查詢是不能使用哈希索引。

全文索引

之前已經說過，B+樹索引的特點，對于使用如下sql，是支持B+樹索引的，只要content 加了B+樹索引，就能利用索引進項快速查詢。

我們通過 B+ 樹索引可以進行前綴查找，如：

select * from blog where content like 'xxx%'; 復制代碼

只要為content列添加了B+樹索引（聚集索引或輔助索引），就可快速查詢。但在更多情況下，我們在博客或搜索引擎中需要查詢的是某個單詞，而不是某個單詞開頭，如：

select * from blog where content like '%xxx%'; 復制代碼

此時如果使用B+樹索引依然是全表掃描，而全文檢索（Full-Text Search）就是將整本書或文章內任意內容檢索出來的技術。

根據B+樹索引的特點是不支持的，InnoDB存儲引擎從1.2.x開始支持全文索引技術，其特性支MyISAM的全部功能。

具體實現原理接下來會介紹

倒排索引

全文檢索使用倒排索引來實現，倒排索引同B+樹索引一樣，也是一種數據結構，它在輔助表中存儲了單詞與單詞自身在一個或多個文檔中所在位置的映射，這通常利用關聯數組實現。

倒排索引它需要將分詞（word）存儲在一個輔助表（Auxiliary Table）中，為了提高全文檢索的并行性能，共有6張輔助表。輔助表中存儲了單詞和單詞在各行記錄中位置的映射關系。它分為兩種：倒排文件索引，詳細倒排索引

1、inverted file index（倒排文件索引），表現為{單詞，單詞所在文檔ID} 2、full inverted index（詳細倒排索引），表現為{單詞，(單詞所在文檔ID, 文檔中的位置)}

全文檢索表

DocumentIDText 文檔內容

1	Souyunku Technical team (搜云庫技術團隊)
2	Go Technical stack (Go技術棧)

inverted file index（倒排文件索引）-輔助表存儲為

倒排文件索引類型的輔助表存儲為：

NumberText 分詞Documents (單詞所在文檔ID)

1	Souyunku	1
2	Technical	1，2
3	team	1
4	Go	2
5	stack	2

full inverted index（ 詳細倒排索引）-輔助表存儲為

詳細倒排索引類型的輔助表存儲為，占用更多空間，也更好的定位數據，比提供更多的搜索特性：

NumberText 分詞Documents (單詞所在文檔ID:文檔中的位置)

1	Souyunku	1:1
2	Technical	1:2 ，2:2
3	team	1:3
4	Go	2:1
5	stack	2:3

全文檢索索引緩存

輔助表是存在與磁盤上的持久化的表，由于磁盤I/O比較慢，因此提供FTS Index Cache（全文檢索索引緩存）來提高性能。FTS Index Cache是一個紅黑樹結構，根據（word, list）排序，在有數據插入時，索引先更新到緩存中，而后InnoDB存儲引擎會批量進行更新到輔助表中。

當數據庫宕機時，尚未落盤的索引緩存數據會自動讀取并存儲，配置參數innodb_ft_cache_size控制緩存的大小，默認為32M，提高該值，可以提高全文檢索的性能，但在故障時，需要更久的時間恢復。

在刪除數據時，InnoDB不會刪除索引數據，而是保存在DELETED輔助表中，因此一段時間后，索引會變得非常大，可以通過optimize table命令手動刪除無效索引記錄。如果需要刪除的內容非常多，會影響應用程序的可用性，參數innodb_ft_num_word_optimize控制每次刪除的分詞數量，默認為2000，用戶可以調整該參數來控制刪除幅度。

全文索引的一些限制

1、現在只支持myisam和innodb 2、不支持分區表 3、多列組合的全文檢索索引必須使用相同的字符集和字符序 4、象形文字不支持。需要ngram來分詞 5、建立全文索引的各個字段必須統一 6、match（）里的查找列，必須是在fulltext索引里定義過的 7、against（）必須為字符串且為常量 8、索引提示會更差 9、在innodb中，所有涉及到全文索引列的DML操作（update，insert，delete），只會在事務提交的時候，執行。中間可能要分詞，標記等 10、不能用 % 通配符 11、不支持沒有單詞界定符（delimiter）的語言，如中文、日語、韓語等

參考資料：MySQL技術內幕 InnoDB存儲引擎 第2版

關注我們

作者：鵬磊
出處：微信公眾號「搜云庫技術團隊」，微信ID：souyunku
版權歸作者所有，任何形式轉載請聯系作者。

轉載于:https://juejin.im/post/5cf620d3e51d4510aa0114bb

總結

以上是生活随笔為你收集整理的面试官：聊一下你对MySQL索引实现原理？的全部內容，希望文章能夠幫你解決所遇到的問題。

如果覺得生活随笔網站內容還不錯，歡迎將生活随笔推薦給好友。