索引介紹

索引是口氣什么

• 官方介紹索引是幫助MySQL高效獲取數據的數據結構。更通俗的搞懂說，數據庫索引好比是索識點一本書前面的目錄，能加快數據庫的引所有知查詢速度。

  

• 一般來說索引本身也很大，口氣不可能全部存儲在內存中，搞懂因此索引往往是索識點存儲在磁盤上的文件中的（可能存儲在單獨的索引文件中，也可能和數據一起存儲在數據文件中）。引所有知

• 我們通常所說的口氣索引，包括聚集索引、搞懂覆蓋索引、索識點組合索引、前綴索引、唯一索引等，沒有特別說明，默認都是使用B+樹結構組織（多路搜索樹，并不一定是二叉的）的索引。

索引的優勢和劣勢

優勢：

• 可以提高數據檢索的效率，降低數據庫的IO成本，類似于書的目錄。

• 通過索引列對數據進行排序，降低數據排序的成本，降低了CPU的消耗。

• 被索引的列會自動進行排序，包括【單列索引】和【組合索引】，只是組合索引的排序要復雜一些。
• 如果按照索引列的順序進行排序，對應order by語句來說，效率就會提高很多。

劣勢：

• 索引會占據磁盤空間

• 索引雖然會提高查詢效率，但是會降低更新表的效率。比如每次對表進行增刪改操作，MySQL不僅要保存數據，還有保存或者更新對應的索引文件。

索引類型

主鍵索引

索引列中的值必須是唯一的，不允許有空值。

普通索引

MySQL中基本索引類型，沒有什么限制，允許在定義索引的列中插入重復值和空值。

唯一索引

索引列中的值必須是唯一的，但是允許為空值。

全文索引

只能在文本類型CHAR,VARCHAR,TEXT類型字段上創建全文索引。字段長度比較大時，如果創建普通索引，在進行like模糊查詢時效率比較低，這時可以創建全文索引。MyISAM和InnoDB中都可以使用全文索引。

空間索引

MySQL在5.7之后的版本支持了空間索引，而且支持OpenGIS幾何數據模型。MySQL在空間索引這方面遵循OpenGIS幾何數據模型規則。

前綴索引

在文本類型如CHAR,VARCHAR,TEXT類列上創建索引時，可以指定索引列的長度，但是數值類型不能指定。

其他（按照索引列數量分類）

1. 單列索引

2. 組合索引

   組合索引的使用，需要遵循最左前綴匹配原則（最左匹配原則）。一般情況下在條件允許的情況下使用組合索引替代多個單列索引使用。

索引的數據結構

Hash表

Hash表，在Java中的HashMap，TreeMap就是Hash表結構，以鍵值對的方式存儲數據。我們使用Hash表存儲表數據Key可以存儲索引列，Value可以存儲行記錄或者行磁盤地址。Hash表在等值查詢時效率很高，時間復雜度為O(1)；但是不支持范圍快速查找，范圍查找時還是只能通過掃描全表方式。

顯然這種并不適合作為經常需要查找和范圍查找的數據庫索引使用。

二叉查找樹

二叉樹，我想大家都會在心里有個圖。

二叉樹特點：每個節點最多有2個分叉，左子樹和右子樹數據順序左小右大。

這個特點就是為了保證每次查找都可以這折半而減少IO次數，但是二叉樹就很考驗第一個根節點的取值，因為很容易在這個特點下出現我們并發想發生的情況“樹不分叉了”，這就很難受很不穩定。

顯然這種情況不穩定的我們再選擇設計上必然會避免這種情況的

平衡二叉樹

平衡二叉樹是采用二分法思維，平衡二叉查找樹除了具備二叉樹的特點，最主要的特征是樹的左右兩個子樹的層級最多相差1。在插入刪除數據時通過左旋/右旋操作保持二叉樹的平衡，不會出現左子樹很高、右子樹很矮的情況。

使用平衡二叉查找樹查詢的性能接近于二分查找法，時間復雜度是 O(log2n)。查詢id=6，只需要兩次IO。

就這個特點來看，可能各位會覺得這就很好，可以達到二叉樹的理想的情況了。然而依然存在一些問題：

1. 時間復雜度和樹高相關。樹有多高就需要檢索多少次，每個節點的讀取，都對應一次磁盤 IO 操作。樹的高度就等于每次查詢數據時磁盤 IO 操作的次數。磁盤每次尋道時間為10ms，在表數據量大時，查詢性能就會很差。（1百萬的數據量，log2n約等于20次磁盤IO，時間20*10=0.2s）

2. 平衡二叉樹不支持范圍查詢快速查找，范圍查詢時需要從根節點多次遍歷，查詢效率不高。

B樹：改造二叉樹

MySQL的數據是存儲在磁盤文件中的，查詢處理數據時，需要先把磁盤中的數據加載到內存中，磁盤IO 操作非常耗時，所以我們優化的重點就是盡量減少磁盤 IO 操作。訪問二叉樹的每個節點就會發生一次IO，如果想要減少磁盤IO操作，就需要盡量降低樹的高度。那如何降低樹的高度呢？

假如key為bigint=8字節，每個節點有兩個指針，每個指針為4個字節，一個節點占用的空間16個字節（8+4*2=16）。

因為在MySQL的InnoDB存儲引擎一次IO會讀取的一頁（默認一頁16K）的數據量，而二叉樹一次IO有效數據量只有16字節，空間利用率極低。為了最大化利用一次IO空間，一個簡單的想法是在每個節點存儲多個元素，在每個節點盡可能多的存儲數據。每個節點可以存儲1000個索引（16k/16=1000），這樣就將二叉樹改造成了多叉樹，通過增加樹的叉樹，將樹從高瘦變為矮胖。構建1百萬條數據，樹的高度只需要2層就可以（1000*1000=1百萬），也就是說只需要2次磁盤IO就可以查詢到數據。磁盤IO次數變少了，查詢數據的效率也就提高了。

這種數據結構我們稱為B樹，B樹是一種多叉平衡查找樹，如下圖主要特點：

1. B樹的節點中存儲著多個元素，每個內節點有多個分叉。

2. 節點中的元素包含鍵值和數據，節點中的鍵值從大到小排列。也就是說，在所有的節點都儲存數據。

3. 父節點當中的元素不會出現在子節點中。

4. 所有的葉子結點都位于同一層，葉節點具有相同的深度，葉節點之間沒有指針連接。

舉個例子，在b樹中查詢數據的情況：

假如我們查詢值等于10的數據。查詢路徑磁盤塊1->磁盤塊2->磁盤塊5。

第一次磁盤IO：將磁盤塊1加載到內存中，在內存中從頭遍歷比較，10<15，走左路，到磁盤尋址磁盤塊2。

第二次磁盤IO：將磁盤塊2加載到內存中，在內存中從頭遍歷比較，7<10，到磁盤中尋址定位到磁盤塊5。

第三次磁盤IO：將磁盤塊5加載到內存中，在內存中從頭遍歷比較，10=10，找到10，取出data，如果data存儲的行記錄，取出data，查詢結束。如果存儲的是磁盤地址，還需要根據磁盤地址到磁盤中取出數據，查詢終止。

相比二叉平衡查找樹，在整個查找過程中，雖然數據的比較次數并沒有明顯減少，但是磁盤IO次數會大大減少。同時，由于我們的比較是在內存中進行的，比較的耗時可以忽略不計。B樹的高度一般2至3層就能滿足大部分的應用場景，所以使用B樹構建索引可以很好的提升查詢的效率。

過程如圖：

看到這里一定覺得B樹就很理想了，但是前輩們會告訴你依然存在可以優化的地方：

1. B樹不支持范圍查詢的快速查找，你想想這么一個情況如果我們想要查找10和35之間的數據，查找到15之后，需要回到根節點重新遍歷查找，需要從根節點進行多次遍歷，查詢效率有待提高。

2. 如果data存儲的是行記錄，行的大小隨著列數的增多，所占空間會變大。這時，一個頁中可存儲的數據量就會變少，樹相應就會變高，磁盤IO次數就會變大。

B+樹：改造B樹

B+樹，作為B樹的升級版，在B樹基礎上，MySQL在B樹的基礎上繼續改造，使用B+樹構建索引。B+樹和B樹最主要的區別在于非葉子節點是否存儲數據的問題

• B樹：非葉子節點和葉子節點都會存儲數據。
• B+樹：只有葉子節點才會存儲數據，非葉子節點至存儲鍵值。葉子節點之間使用雙向指針連接，最底層的葉子節點形成了一個雙向有序鏈表。

B+樹的最底層葉子節點包含了所有的索引項。從圖上可以看到，B+樹在查找數據的時候，由于數據都存放在最底層的葉子節點上，所以每次查找都需要檢索到葉子節點才能查詢到數據。

所以在需要查詢數據的情況下每次的磁盤的IO跟樹高有直接的關系，但是從另一方面來說，由于數據都被放到了葉子節點，放索引的磁盤塊鎖存放的索引數量是會跟這增加的，相對于B樹來說，B+樹的樹高理論上情況下是比B樹要矮的。

也存在索引覆蓋查詢的情況，在索引中數據滿足了當前查詢語句所需要的全部數據，此時只需要找到索引即可立刻返回，不需要檢索到最底層的葉子節點。

舉個例子：等值查詢

假如我們查詢值等于9的數據。查詢路徑磁盤塊1->磁盤塊2->磁盤塊6。

第一次磁盤IO：將磁盤塊1加載到內存中，在內存中從頭遍歷比較，9<15，走左路，到磁盤尋址磁盤塊2。

第二次磁盤IO：將磁盤塊2加載到內存中，在內存中從頭遍歷比較，7<9<12，到磁盤中尋址定位到磁盤塊6。

第三次磁盤IO：將磁盤塊6加載到內存中，在內存中從頭遍歷比較，在第三個索引中找到9，取出data，如果data存儲的行記錄，取出data，查詢結束。如果存儲的是磁盤地址，還需要根據磁盤地址到磁盤中取出數據，查詢終止。（這里需要區分的是在InnoDB中Data存儲的為行數據，而MyIsam中存儲的是磁盤地址。）

過程如圖：

范圍查詢：

假如我們想要查找9和26之間的數據。查找路徑是磁盤塊1->磁盤塊2->磁盤塊6->磁盤塊7。

首先查找值等于9的數據，將值等于9的數據緩存到結果集。這一步和前面等值查詢流程一樣，發生了三次磁盤IO。

查找到15之后，底層的葉子節點是一個有序列表，我們從磁盤塊6，鍵值9開始向后遍歷篩選所有符合篩選條件的數據。

第四次磁盤IO：根據磁盤6后繼指針到磁盤中尋址定位到磁盤塊7，將磁盤7加載到內存中，在內存中從頭遍歷比較，9<25<26，9<26<=26，將data緩存到結果集。

主鍵具備唯一性（后面不會有<=26的數據），不需再向后查找，查詢終止。將結果集返回給用戶。

可以看到B+樹可以保證等值和范圍查詢的快速查找，MySQL的索引就采用了B+樹的數據結構。

Mysql的索引實現

介紹完了索引數據結構，那肯定是要帶入到Mysql里面看看真實的使用場景的，所以這里分析Mysql的兩種存儲引擎的索引實現：MyISAM索引和InnoDB索引

MyIsam索引

以一個簡單的user表為例。user表存在兩個索引，id列為主鍵索引，age列為普通索引

CREATE?TABLE?`user`
(
??`id`???????int(11)?NOT?NULL?AUTO_INCREMENT,
??`username`?varchar(20)?DEFAULT?NULL,
??`age`??????int(11)?????DEFAULT?NULL,
??PRIMARY?KEY?(`id`)?USING?BTREE,
??KEY?`idx_age`?(`age`)?USING?BTREE
)?ENGINE?=?MyISAM
??AUTO_INCREMENT?=?1
??DEFAULT?CHARSET?=?utf8;

MyISAM的數據文件和索引文件是分開存儲的。MyISAM使用B+樹構建索引樹時，葉子節點中存儲的鍵值為索引列的值，數據為索引所在行的磁盤地址。

主鍵索引

表user的索引存儲在索引文件user.MYI中，數據文件存儲在數據文件 user.MYD中。

簡單分析下查詢時的磁盤IO情況：

根據主鍵等值查詢數據：

select * from user where id = 28;

1. 先在主鍵樹中從根節點開始檢索，將根節點加載到內存，比較28<75，走左路。（1次磁盤IO）
2. 將左子樹節點加載到內存中，比較16<28<47，向下檢索。（1次磁盤IO）
3. 檢索到葉節點，將節點加載到內存中遍歷，比較16<28，18<28，28=28。查找到值等于30的索引項。（1次磁盤IO）
4. 從索引項中獲取磁盤地址，然后到數據文件user.MYD中獲取對應整行記錄。（1次磁盤IO）
5. 將記錄返給客戶端。

磁盤IO次數：3次索引檢索+記錄數據檢索。

根據主鍵范圍查詢數據：

select?*?from?user?where?id?between?28?and?47;

1. 先在主鍵樹中從根節點開始檢索，將根節點加載到內存，比較28<75，走左路。（1次磁盤IO）

2. 將左子樹節點加載到內存中，比較16<28<47，向下檢索。（1次磁盤IO）

3. 檢索到葉節點，將節點加載到內存中遍歷比較16<28，18<28，28=28<47。查找到值等于28的索引項。

   根據磁盤地址從數據文件中獲取行記錄緩存到結果集中。（1次磁盤IO）

   我們的查詢語句時范圍查找，需要向后遍歷底層葉子鏈表，直至到達最后一個不滿足篩選條件。

4. 向后遍歷底層葉子鏈表，將下一個節點加載到內存中，遍歷比較，28<47=47，根據磁盤地址從數據文件中獲取行記錄緩存到結果集中。（1次磁盤IO）

5. 最后得到兩條符合篩選條件，將查詢結果集返給客戶端。

磁盤IO次數：4次索引檢索+記錄數據檢索。

備注：以上分析僅供參考，MyISAM在查詢時，會將索引節點緩存在MySQL緩存中，而數據緩存依賴于操作系統自身的緩存，所以并不是每次都是走的磁盤，這里只是為了分析索引的使用過程。

輔助索引

在 MyISAM 中,輔助索引和主鍵索引的結構是一樣的，沒有任何區別，葉子節點的數據存儲的都是行記錄的磁盤地址。只是主鍵索引的鍵值是唯一的，而輔助索引的鍵值可以重復。

查詢數據時，由于輔助索引的鍵值不唯一，可能存在多個擁有相同的記錄，所以即使是等值查詢，也需要按照范圍查詢的方式在輔助索引樹中檢索數據。

InnoDB索引

主鍵索引（聚簇索引）

每個InnoDB表都有一個聚簇索引 ，聚簇索引使用B+樹構建，葉子節點存儲的數據是整行記錄。一般情況下，聚簇索引等同于主鍵索引，當一個表沒有創建主鍵索引時，InnoDB會自動創建一個ROWID字段來構建聚簇索引。InnoDB創建索引的具體規則如下：

1. 在表上定義主鍵PRIMARY KEY，InnoDB將主鍵索引用作聚簇索引。
2. 如果表沒有定義主鍵，InnoDB會選擇第一個不為NULL的唯一索引列用作聚簇索引。
3. 如果以上兩個都沒有，InnoDB 會使用一個6 字節長整型的隱式字段 ROWID字段構建聚簇索引。該ROWID字段會在插入新行時自動遞增。

除聚簇索引之外的所有索引都稱為輔助索引。在中InnoDB，輔助索引中的葉子節點存儲的數據是該行的主鍵值都。在檢索時，InnoDB使用此主鍵值在聚簇索引中搜索行記錄。

這里以user_innodb為例，user_innodb的id列為主鍵，age列為普通索引。

CREATE?TABLE?`user_innodb`
(
??`id`???????int(11)?NOT?NULL?AUTO_INCREMENT,
??`username`?varchar(20)?DEFAULT?NULL,
??`age`??????int(11)?????DEFAULT?NULL,
??PRIMARY?KEY?(`id`)?USING?BTREE,
??KEY?`idx_age`?(`age`)?USING?BTREE
)?ENGINE?=?InnoDB;

InnoDB的數據和索引存儲在一個文件t_user_innodb.ibd中。InnoDB的數據組織方式，是聚簇索引。

主鍵索引的葉子節點會存儲數據行，輔助索引只會存儲主鍵值。

等值查詢數據：

select?*?from?user_innodb?where?id?=?28;

1. 先在主鍵樹中從根節點開始檢索，將根節點加載到內存，比較28<75，走左路。（1次磁盤IO）

   將左子樹節點加載到內存中，比較16<28<47，向下檢索。（1次磁盤IO）

   檢索到葉節點，將節點加載到內存中遍歷，比較16<28，18<28，28=28。查找到值等于28的索引項，直接可以獲取整行數據。將改記錄返回給客戶端。（1次磁盤IO）

   磁盤IO數量：3次。

輔助索引

除聚簇索引之外的所有索引都稱為輔助索引，InnoDB的輔助索引只會存儲主鍵值而非磁盤地址。

以表user_innodb的age列為例，age索引的索引結果如下圖。

底層葉子節點的按照（age，id）的順序排序，先按照age列從小到大排序，age列相同時按照id列從小到大排序。

使用輔助索引需要檢索兩遍索引：首先檢索輔助索引獲得主鍵，然后使用主鍵到主索引中檢索獲得記錄。

畫圖分析等值查詢的情況：

select?*?from?t_user_innodb?where?age=19;

根據在輔助索引樹中獲取的主鍵id，到主鍵索引樹檢索數據的過程稱為回表查詢。

磁盤IO數：輔助索引3次+獲取記錄回表3次

組合索引

還是以自己創建的一個表為例：表 abc_innodb，id為主鍵索引，創建了一個聯合索引idx_abc(a,b,c)。

CREATE?TABLE?`abc_innodb`
(
??`id`?int(11)?NOT?NULL?AUTO_INCREMENT,
??`a`??int(11)?????DEFAULT?NULL,
??`b`??int(11)?????DEFAULT?NULL,
??`c`??varchar(10)?DEFAULT?NULL,
??`d`??varchar(10)?DEFAULT?NULL,
??PRIMARY?KEY?(`id`)?USING?BTREE,
??KEY?`idx_abc`?(`a`,?`b`,?`c`)
)?ENGINE?=?InnoDB;

select * from abc_innodb order by a, b, c, id;

組合索引的數據結構：

組合索引的查詢過程：

select?*?from?abc_innodb?where?a?=?13?and?b?=?16?and?c?=?4;

最左匹配原則：

最左前綴匹配原則和聯合索引的索引存儲結構和檢索方式是有關系的。

在組合索引樹中，最底層的葉子節點按照第一列a列從左到右遞增排列，但是b列和c列是無序的，b列只有在a列值相等的情況下小范圍內遞增有序，而c列只能在a，b兩列相等的情況下小范圍內遞增有序。

就像上面的查詢，B+樹會先比較a列來確定下一步應該搜索的方向，往左還是往右。如果a列相同再比較b列。但是如果查詢條件沒有a列，B+樹就不知道第一步應該從哪個節點查起。

可以說創建的idx_abc(a,b,c)索引，相當于創建了(a)、（a,b）（a,b,c）三個索引。、

組合索引的最左前綴匹配原則：使用組合索引查詢時，mysql會一直向右匹配直至遇到范圍查詢(>、<、between、like)就停止匹配。

覆蓋索引

覆蓋索引并不是說是索引結構，覆蓋索引是一種很常用的優化手段。因為在使用輔助索引的時候，我們只可以拿到主鍵值，相當于獲取數據還需要再根據主鍵查詢主鍵索引再獲取到數據。但是試想下這么一種情況，在上面abc_innodb表中的組合索引查詢時，如果我只需要abc字段的，那是不是意味著我們查詢到組合索引的葉子節點就可以直接返回了，而不需要回表。這種情況就是覆蓋索引。

可以看一下執行計劃：

覆蓋索引的情況：

未使用到覆蓋索引：

總結

看到這里，你是不是對于自己的sql語句里面的索引的有了更多優化想法呢。

比如：

避免回表

在InnoDB的存儲引擎中，使用輔助索引查詢的時候，因為輔助索引葉子節點保存的數據不是當前記錄的數據而是當前記錄的主鍵索引，索引如果需要獲取當前記錄完整數據就必然需要根據主鍵值從主鍵索引繼續查詢。這個過程我們成位回表。想想回表必然是會消耗性能影響性能。那如何避免呢？

使用索引覆蓋，舉個例子：現有User表（id(PK),name(key),sex,address,hobby...）

如果在一個場景下，select id,name,sex from user where name ='zhangsan';這個語句在業務上頻繁使用到，而user表的其他字段使用頻率遠低于它，在這種情況下，如果我們在建立 name 字段的索引的時候，不是使用單一索引，而是使用聯合索引（name，sex）這樣的話再執行這個查詢語句是不是根據輔助索引查詢到的結果就可以獲取當前語句的完整數據。

這樣就可以有效地避免了回表再獲取sex的數據。

這里就是一個典型的使用覆蓋索引的優化策略減少回表的情況。

聯合索引的使用

聯合索引，在建立索引的時候，盡量在多個單列索引上判斷下是否可以使用聯合索引。聯合索引的使用不僅可以節省空間，還可以更容易的使用到索引覆蓋。

試想一下，索引的字段越多，是不是更容易滿足查詢需要返回的數據呢。比如聯合索引（a_b_c），是不是等于有了索引：a，a_b，a_b_c三個索引，這樣是不是節省了空間，當然節省的空間并不是三倍于（a，a_b，a_b_c）三個索引，因為索引樹的數據沒變，但是索引data字段的數據確實真實的節省了。

聯合索引的創建原則，在創建聯合索引的時候因該把頻繁使用的列、區分度高的列放在前面，頻繁使用代表索引利用率高，區分度高代表篩選粒度大，這些都是在索引創建的需要考慮到的優化場景，也可以在常需要作為查詢返回的字段上增加到聯合索引中，如果在聯合索引上增加一個字段而使用到了覆蓋索引，那我建議這種情況下使用聯合索引。

聯合索引的使用

1. 考慮當前是否已經存在多個可以合并的單列索引，如果有，那么將當前多個單列索引創建為一個聯合索引。
2. 當前索引存在頻繁使用作為返回字段的列，這個時候就可以考慮當前列是否可以加入到當前已經存在索引上，使其查詢語句可以使用到覆蓋索引。

好啦以上就是我自己對索引的一些小總結，有點小長有點枯燥，適合收藏后慢慢看。

哈嘍，我是小林，時而圖解技術，時而說些雜事，時而拍拍貓片。

推薦閱讀

索引為什么能提高查詢性能....

一口氣搞懂「文件系統」，就靠這 25 張圖了