MySQL中的索引原理與索引分類

一、MySQL索引起步

1. 索引的概述

MySQL官方對索引的定義為：索引（index）是幫助MySQL高效獲取數據的數據結構（有序）。在數據之外，資料庫系統還維護著滿足特定查找算法的數據結構，這些數據結構以某種方式引用（指向）數據，這樣就可以在這些數據結構上實現高級查找算法，這種數據結構就是索引。如下圖所示：

左邊是數據表，一共有兩列七行記錄，最左邊的0x07格式的數據是物理地址（注意邏輯上相鄰的記錄在磁碟上也並不是一定物理相鄰的）。為了加快 Col 2 的查找，可以維護一個右邊所示的二叉查找樹，每個節點分別包含索引鍵值和一個指向對應數據的物理地址的指針，這樣就可以運用二叉查找快速獲取到對應的數據了。

一般來說索引本身也很大，不可能全部存儲在內存中，因此索引往往以索引文件的形式存儲在磁碟上。建立索引是資料庫中用來提高性能的最常用的方式。

2. 建立索引的優劣

優勢

類似於書籍的目錄索引，提高數據檢索的效率，降低資料庫的IO成本；通過索引對數據進行排序，降低數據排序的成本，降低CPU的消耗；

劣勢：

實際上索引也是一張表，該表中保存了主鍵與索引欄位，並指向實體類的記錄，所以索引列也是要佔用空間的；雖然索引提高了查詢效率，同時也降低了表更新的速度，如對表進行INSERT、UPDATE、DELETE。因為更新表時，MySQL不僅要保存數據，還要保存一下索引列的欄位，都會調整因為更新所帶來的鍵值變化後的索引信息。3. 什麼時候建立索引

索引是應用程式設計和開發的一個重要方面。若索引太多，應用程式的性能可能會受到影響。而索引太少，對查詢性能又會產生影響，要找到一個平衡點，這對應用程式的性能至關重要。一些開發人員總是在事後才想起添加索引----我一直認為，這源於一種錯誤的開發模式。如果知道數據的使用，那麼從一開始就應該在需要處添加索引。開發人員往往對資料庫的使用停留在應用的層面，比如編寫SQL語句、存儲過程之類，甚至可能不知道索引的存在，或認為事後讓相關DBA加上即可。DBA往往不夠了解業務的數據流，而添加索引需要通過監控大量的SQL語句進而從中找到問題，這個步驟所需的時間肯定是遠大於初始添加索引所需的時間，並且可能會遺漏一部分的索引。當然索引也並不是越多越好，我曾經遇到過這樣一個問題：某臺MySQL伺服器 iostat 顯示磁碟使用率一直處於100%，經過分析後發現是由於開發人員添加了太多的索引，在刪除一些不必要的索引之後，磁碟使用率馬上下降為20%。可見索引的添加也是非常有技術含量的。

二、索引的數據結構1. 索引分類與引擎對索引的支持

索引是在MySQL的存儲引擎層中實現的，而不是在伺服器層實現的。所以每種存儲引擎的索引都不一定完全相同，也不是所有的存儲引擎都支持所有的索引類型。MySQL目前提供了以下4中索引：

B TREE索引：最常見的索引類型，大部分索引都支持B樹索引。HASH索引：只有Memory引擎支持，使用場景簡單。R-tree索引（空間索引）：空間索引是MyISAM引擎的一個特殊索引類型，主要用於地理空間數據類型，通常使用較少；Full-text（全文索引）：全文索引也是MyISAM的一個特殊索引類型，主要用於全文索引，InnoDB從MySQL 5.6版本開始支持全文索引；

MyISAM、InnoDB、Memory三種存儲引擎對各種索引類型的支持：

索引InnoDB引擎MyISAM引擎Memory引擎B TREE索引支持支持支持HASH索引不支持不支持支持R-tree索引不支持支持不支持Full-text5.6版本後支持支持不支持

我們常說的索引，如果沒有特別的索引，都是指B+樹（多路搜索樹，並不一定是二叉的）結構組織的索引。其中聚集索引、符合索引、前綴索引、唯一索引默認都是使用 B+ tree，統稱為索引。

2. B Tree結構

B樹又叫多路平衡搜索樹，一顆m叉的B Tree特性如下：

除根節點與葉子節點外，每個節點至少有[ceil (m / 2) ]個孩子節點；每個非葉子結點由n個key與n+1個指針組成，其中 [ceil ( m / 2 ) -1] <= n <= m-1；

接下來以5叉B TREE為例，key的數量：公式推導 [ ceil ( m / 2 ) -1 ] <= n <= m-1。所以 2 <= n <= 4。當 n > 4時，中間節點分裂到父節點，兩邊節點分裂。

以插入 C N G A H E K Q M 數據為例，演變過程如一下步驟：

（1）插入前四個字母 C N G A，此時根節點剛好滿足 n < m-1；

（2）繼續插入H，n > 4，中間元素G字母向上分裂到新的節點；

（3）繼續插入E K Q，此時並不需要分裂；

（4）插入M，中間元素M字母向上分裂到父節點中，排在G後面；

到此就構建了一顆簡單的B樹，B樹與二叉搜索樹相比，查詢效率更高，因為對於相同的數據量來說，B樹的層次結構比二叉樹小，因此搜索速度快，當然這與磁碟IO有很大聯繫，等會介紹。

3. B+ Tree結構

B+樹 是 B樹的變種，B+樹 與 B樹 的區別為：

如上圖，就是一顆典型的B+ Tree，一個節點擁有n個子節點，那麼就擁有n個key。同時非葉子節點僅具有充當索引的作用，不存放跟記錄有關的信息。樹的所有葉子節點構成一個有序鍊表，可以按照key排序依次遍歷全部記錄，接下來介紹下MySQL中的B+樹。

三、為什麼MySQL使用B+樹？

1. 磁碟IO與預讀

前面提到了磁碟訪問，這裡簡單介紹一下磁碟IO和預讀，磁碟讀取數據靠的是機械運動，每次讀取數據花費的時間可以分為尋道時間、旋轉延遲、傳輸時間三個部分：

在公眾號頂級架構師後臺回復「架構整潔」，獲取一份驚喜禮包。

尋道時間指的是磁臂移動到指定磁軌所需要的時間，主流磁碟一般在5 ms以下；旋轉延遲就是我們經常說的磁碟轉速磁碟轉速，比如一個磁碟7200轉/min，表示每分鐘能轉7200次，也就是說一秒能轉120次，旋轉延遲就是1/120/2 = 4.17 ms，也就是半圈的時間（這裡有兩個時間：平均尋道時間，受限於目前的物理水平，大概是5 ms的時間，找到磁軌了，還需要找到你數據存在的那個點，尋點時間，這尋點時間的一個平均值就是半圈的時間，這個半圈時間叫做平均延遲時間，那麼平均延遲時間加上平均尋道時間就是你找到一個數據所消耗的平均時間，大概 9 ms，其實機械硬碟慢主要是慢在這兩個時間上了，當找到數據然後把數據拷貝到內存的時間是非常短暫的，和光速差不多了）；傳輸時間指的是從磁碟讀出或將數據寫入磁碟的時間，一般在零點幾毫秒，相對於前兩個時間可以忽略不計。

那麼訪問一次磁碟的時間，即一次磁碟IO的時間約等於5+4.17 = 9 ms左右，聽起來還挺不錯的，但要知道一臺500 -MIPS（Million Instructions Per Second）的機器每秒可以執行5億條指令，因為指令依靠的是電的性質，換句話說執行一次IO的消耗的時間段下cpu可以執行約450萬條指令，資料庫動輒十萬百萬乃至千萬級數據，每次9毫秒的時間，顯然是個災難，所以我們要想辦法降低IO次數。下圖是計算機硬體延遲的對比圖，供大家參考：

考慮到磁碟IO是非常高昂的操作，計算機作業系統做了一些優化，當一次IO時，不光把當前磁碟地址的數據，而是把相鄰的數據也都讀取到內存緩衝區內，因為局部預讀性原理告訴我們，當計算機訪問一個地址的數據的時候，與其相鄰的數據也會很快被訪問到。每一次IO讀取的數據我們稱之為一頁(page)。具體一頁有多大數據跟作業系統有關，一般為 4k 或 8k，也就是我們讀取一頁內的數據時候，實際上才發生了一次IO，這個理論對於索引的數據結構設計非常有幫助。

2. MySQL中的B+ 樹

一般來說，索引本身也很大，所以不會存儲在內存中，往往是以索引文件的形式存儲在磁碟上的，因此索引在查找的過程中也是需要到IO消耗的。

好了，那麼我們為了減少磁碟IO的次數，是不是一次讀取的內容越多，就越能減少IO的消耗呢？假如我們現在按上圖的索引圖要查找3這個元素，需要到幾次磁碟IO呢？首先將磁碟塊1加載到內存中，判斷出3小於28，那麼就會去鎖定p1指針（這個比較過程以及指針的切換是非常快的，這個過程是發生在內存中，相較於IO操作可以忽略不計），將磁碟塊2加載到內存中，繼續判斷，從而將磁碟塊4也加載到內存中，此時為葉節點，葉節點存儲數據，那麼就只需要在當前的塊中將3查找出來即可，整個過程只發生了3次磁碟IO，大大地提高了效率。

2.1 為什麼是B+樹而不是B樹？

上面我們提到的B+樹所完成的工作，B樹也能完成？為什麼MySQL中的索引大多使用B+樹而不是B樹呢？有以下幾個原因：

首先B+樹的空間利用率更高（非葉節點沒有data域），可減少IO次數，磁碟讀寫所耗費的代價更低；

B+樹的查詢效率更加地穩定，B樹搜索在非葉子節點還是葉子節點結束都有可能，約靠近根節點，查找效率越快；而B+樹無論查找的是什麼數據，最終都需要從根節點一直走向葉節點，所有查找所經過的次數都是一樣的；

B+樹能同時支持隨機檢索和順序檢索，而B樹只適合隨機檢索，順序檢索的效率比B+樹低；

增刪文件時，B+樹的效率更高，因為所有的data都在葉子節點中，而B樹刪減節點時還需要分裂，中間節點向上等操作；

2.2 那Hash索引呢？

Hash索引更容易理解，底層就是Hash表，調用一次hash函數就可以直接確定相應鍵值，之後進行回表查詢實際數據，按理說Hash索引比B+樹還高效？為什麼不使用Hash索引呢？原因有以下幾點：

Hash索引不支持區間查找，類似select * form table where age > 10這種查找，對於Hash來說，XX；

Hash索引不支持模糊查詢，像JoJoX和JoJoA之間沒有關聯性，原因在於Hash函數的不可預測；

Hash索引在等值查詢上很快，但是卻不穩定，hash索引還有一個重要的問題，hash碰撞，當發生hash碰撞時，某個鍵值大量重複時，效率變得極差；

四、索引分類

按表列屬性分類，有以下幾種索引類型：

1. 單值索引（單列索引）

單值索引即一個索引只包含單個列，一個表中可以有多個單列索引；語法如下：

CREATE TABLE customer (    id INT(10) UNSIGNED  AUTO_INCREMENT,    customer_no VARCHAR(200),    customer_name VARCHAR(200),    PRIMARY KEY(id),    KEY (customer_name)  );

CREATE INDEX idx_customer_name ON customer(customer_name); 
DROP INDEX idx_customer_name ;

2. 主鍵索引
CREATE TABLE customer (    id INT(10) UNSIGNED  AUTO_INCREMENT,    customer_no VARCHAR(200),    customer_name VARCHAR(200),    PRIMARY KEY(id) );
CREATE TABLE customer2 (    id INT(10) UNSIGNED,    customer_no VARCHAR(200),    customer_name VARCHAR(200),    PRIMARY KEY(id) );

ALTER TABLE customer add PRIMARY KEY customer(customer_no);  ALTER TABLE customer drop PRIMARY KEY ;

3. 唯一索引
索引列的值必須唯一，但允許有空值，語法如下：
在公眾號編程技術圈後臺回復「Java」，獲取Java面試題和答案驚喜禮包。
CREATE TABLE customer (    id INT(10) UNSIGNED  AUTO_INCREMENT,    customer_no VARCHAR(200),    customer_name VARCHAR(200),    PRIMARY KEY(id),    KEY (customer_name),    UNIQUE (customer_no));

CREATE UNIQUE INDEX idx_customer_no ON customer(customer_no);DROP INDEX idx_customer_no on customer ;

4. 複合索引（聯合索引）
複合索引即一個索引中包含多個列，在資料庫操作期間，複合索引所需要的開銷更小（相對於相同的多個列建立單值索引）；
CREATE TABLE customer (    id INT(10) UNSIGNED  AUTO_INCREMENT,    customer_no VARCHAR(200),    customer_name VARCHAR(200),    PRIMARY KEY(id),    KEY (customer_name),    UNIQUE (customer_name),    KEY (customer_no,customer_name));

CREATE INDEX idx_no_name ON customer(customer_no,customer_name); DROP INDEX idx_no_name on customer ;

接下來介紹以下最左前綴匹配域覆蓋索引：
5. 最左前綴匹配
認識了單值索引和複合索引，接下來了解最左前綴匹配（leftmost prefix）就容易得多了。什麼是最左前綴匹配呢？
假設現在有三個欄位建立了複合索引CREATE INDEX idx_a_b_c ON demo_table(a, b, c);那麼但你的where條件是a、a、b或者啊a、b、c時，都可以命中索引，除此之外都不能命中索引，例如：a、c或者b、c等；
當然有一個例外，當你 select 的欄位裡有複合索引裡的欄位，那麼where語句不需要滿足最左前綴匹配，MySQL 也會走索引。
比如：select a from demo_table where b = "xxx";
不過這時走索引不是為了加速查詢（這時候索引對查詢效率提升效果幾乎沒有），而是為了利用下面要講的，覆蓋索引，來減少對數據的檢索。
6. 覆蓋索引
覆蓋索引（covering index）的原理很簡單，就像你拿到了一本書的目錄，裡頭有標題和對應的頁碼，當你想知道第267頁的標題是什麼的時候，完全沒有必要翻到267頁去看，而是直接看目錄。
同理，當你要select的欄位，已經在索引樹裡面存儲，那就不需要再去檢索資料庫，直接拿來用就行了。
還是上面的例子，你給a、b、c三個欄位建了複合索引，那麼對於下面這條sql，就可以走覆蓋索引:
select b, c from demo_table where a = "xxx";
explain一下，你就會發現extra欄位是「Using index」，或者使用explain FORMAT=JSON … ，輸出一個json結果的結果，看「using_index」屬性，你會發現是「true」，這都意味著使用到了覆蓋索引。
Using index (JSON property: using_index)：The column information is retrieved from the table using only information in the index tree without having to do an additional seek to read the actual row.

按存儲結構分類，有以及幾種索引：
7. 聚簇索引（聚集索引）
聚簇索引就是將數據存儲與索引放到了一塊，找到索引也就找到了數據。
InnoDB的聚簇索引實際上是在同一個BTree結構中同時存儲了索引和整行數據，通過該索引查詢可以直接獲取查詢數據行。
聚簇索引不是一種單獨的索引類型，而是一種數據的存儲方式，聚簇索引的順序，就是數據在硬碟上的物理順序。
在 MySQL 通常聚簇索引是主鍵的同義詞，每張表只包含一個聚簇索引(其他資料庫不一定)。
8. 輔助索引（二級索引）
非聚簇索引就是將數據存儲於索引分開結構，索引結構的葉子節點指向了數據的對應行，MyISAM通過key_buffer把索引先緩存到內存中，當需要訪問數據時（通過索引訪問數據），在內存中直接搜索索引，然後通過索引找到磁碟相應數據（這一步稱為回表查詢），這也就是為什麼索引不在key buffer命中時，速度慢的原因。
五、索引設計原則
索引的設計可以遵循一些已有的原則，創建索引的時候儘量考慮是否符合這些原則，便於提升索引的使用效率，更高效地使用索引：
對查詢次數頻次較高，且數據量較大的表建立索引；
索引欄位的選擇，最佳候選列應當從where子句的條件中提取，如果where子句中的組合比較多，那麼應當挑選最常用、過濾效果最好的列的組合；
使用唯一索引，區分度高、使用效率越高；
索引可以有效的提升查詢數據的效率 , 但索引數量並不是多多益善 , 索引越多 , 維護索引的代價自然也就水漲船高 . 對於插入, 更新, 刪除 等 DML 操作比較繁瑣的表來說 , 索引過多 , 會引入相當高的維護代價 , 降低 DML 操作的效率 , 增加相應操作的時間消耗 , 另外索引過多的話 , MySQL也會犯 選擇困難症 , 雖然最終仍然會找到一個可用的索引 , 但無疑提高了索引的代價 .
使用段索引 , 索引創建之後也是使用硬碟來存儲的 , 因此提高索引訪問的 I/O 效率 , 也可以跳高總體的訪問效率 . 假如構成索引的欄位 總長度比較短 , 那麼在給定大小的存儲塊內 , 可以存儲更多的索引值 , 相應的可以有效地提升MySQL訪問索引的 I/O 效率.
利用最左前綴的原則 , N個列組合而成的組合索引 , 那麼相當於是創建了N 個索引 。如果查詢時where 子句使用了組成該索引的前幾個欄位 , 那麼這條查詢SQL可以利用組合索引來提升查詢效率
參考文章：
MySQL索引原理：https://www.cnblogs.com/exceptioneye/p/5452068.html
MySQL索引分類：https://blog.csdn.net/qq_17707713/article/details/90059408
MySQL優化之索引篇：https://www.cnblogs.com/cryin107/p/13166865.html
PS：歡迎在留言區留下你的觀點，一起討論提高。如果今天的文章讓你有新的啟發，歡迎轉發分享給更多人。
版權申明：內容來源網絡，版權歸原創者所有。除非無法確認，我們都會標明作者及出處，如有侵權煩請告知，我們會立即刪除並表示歉意。謝謝!