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

一、MySQL索引起步

1. 索引的概述

MySQL官方對索引的定義為：索引（index）是幫助MySQL高效獲取數(shù)據(jù)的數(shù)據(jù)結(jié)構(gòu)（有序）。在數(shù)據(jù)之外，數(shù)據(jù)庫系統(tǒng)還維護著滿足特定查找算法的數(shù)據(jù)結(jié)構(gòu)，這些數(shù)據(jù)結(jié)構(gòu)以某種方式引用（指向）數(shù)據(jù)，這樣就可以在這些數(shù)據(jù)結(jié)構(gòu)上實現(xiàn)高級查找算法，這種數(shù)據(jù)結(jié)構(gòu)就是索引。如下圖所示：

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

一般來說索引本身也很大，不可能全部存儲在內(nèi)存中，因此索引往往以索引文件的形式存儲在磁盤上。建立索引是數(shù)據(jù)庫中用來提高性能的最常用的方式。

2. 建立索引的優(yōu)劣

優(yōu)勢

劣勢：

3. 什么時候建立索引

索引是應(yīng)用程序設(shè)計和開發(fā)的一個重要方面。若索引太多，應(yīng)用程序的性能可能會受到影響。而索引太少，對查詢性能又會產(chǎn)生影響，要找到一個平衡點，這對應(yīng)用程序的性能至關(guān)重要。一些開發(fā)人員總是在事后才想起添加索引----我一直認為，這源于一種錯誤的開發(fā)模式。如果知道數(shù)據(jù)的使用，那么從一開始就應(yīng)該在需要處添加索引。開發(fā)人員往往對數(shù)據(jù)庫的使用停留在應(yīng)用的層面，比如編寫SQL語句、存儲過程之類，甚至可能不知道索引的存在，或認為事后讓相關(guān)DBA加上即可。DBA往往不夠了解業(yè)務(wù)的數(shù)據(jù)流，而添加索引需要通過監(jiān)控大量的SQL語句進而從中找到問題，這個步驟所需的時間肯定是遠大于初始添加索引所需的時間，并且可能會遺漏一部分的索引。當然索引也并不是越多越好，我曾經(jīng)遇到過這樣一個問題：某臺MySQL服務(wù)器 iostat 顯示磁盤使用率一直處于100%，經(jīng)過分析后發(fā)現(xiàn)是由于開發(fā)人員添加了太多的索引，在刪除一些不必要的索引之后，磁盤使用率馬上下降為20%?？梢娝饕奶砑右彩欠浅Ｓ屑夹g(shù)含量的。

二、索引的數(shù)據(jù)結(jié)構(gòu)

1. 索引分類與引擎對索引的支持

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

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

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

索引	InnoDB引擎	MyISAM引擎	Memory引擎
B TREE索引	支持	支持	支持
HASH索引	不支持	不支持	支持
R-tree索引	不支持	支持	不支持
Full-text	5.6版本后支持	支持	不支持

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

2. B Tree結(jié)構(gòu)

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

• 樹中每個節(jié)點最多包含m個孩子節(jié)點；
• 除根節(jié)點與葉子節(jié)點外，每個節(jié)點至少有[ceil (m / 2) ]個孩子節(jié)點；
• 若根節(jié)點不是葉子節(jié)點，則至少有兩個孩子；
• 所有的葉子結(jié)點都在同一層；
• 每個非葉子結(jié)點由n個key與n+1個指針組成，其中 [ceil ( m / 2 ) -1] <= n <= m-1；

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

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

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

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

（3）繼續(xù)插入E K Q，此時并不需要分裂；

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

到此就構(gòu)建了一顆簡單的B樹，B樹與二叉搜索樹相比，查詢效率更高，因為對于相同的數(shù)據(jù)量來說，B樹的層次結(jié)構(gòu)比二叉樹小，因此搜索速度快，當然這與磁盤IO有很大聯(lián)系，等會介紹。

3. B+ Tree結(jié)構(gòu)

B+樹 是 B樹的變種，B+樹 與 B樹 的區(qū)別為：

• n叉B+樹最多含有n個key，而 B樹最多只能含有n - 1個key；

• B+樹的葉子結(jié)點保存所有的key信息，依照key的大小順序排列；

• 所有的非葉子節(jié)點都可以看作key的索引部分。

  

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

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

1. 磁盤IO與預(yù)讀

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

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

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

考慮到磁盤IO是非常高昂的操作，計算機操作系統(tǒng)做了一些優(yōu)化，當一次IO時，不光把當前磁盤地址的數(shù)據(jù)，而是把相鄰的數(shù)據(jù)也都讀取到內(nèi)存緩沖區(qū)內(nèi)，因為局部預(yù)讀性原理告訴我們，當計算機訪問一個地址的數(shù)據(jù)的時候，與其相鄰的數(shù)據(jù)也會很快被訪問到。每一次IO讀取的數(shù)據(jù)我們稱之為一頁(page)。具體一頁有多大數(shù)據(jù)跟操作系統(tǒng)有關(guān)，一般為 4k 或 8k，也就是我們讀取一頁內(nèi)的數(shù)據(jù)時候，實際上才發(fā)生了一次IO，這個理論對于索引的數(shù)據(jù)結(jié)構(gòu)設(shè)計非常有幫助。

2. MySQL中的B+ 樹

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

好了，那么我們?yōu)榱藴p少磁盤IO的次數(shù)，是不是一次讀取的內(nèi)容越多，就越能減少IO的消耗呢？假如我們現(xiàn)在按上圖的索引圖要查找3這個元素，需要到幾次磁盤IO呢？首先將磁盤塊1加載到內(nèi)存中，判斷出3小于28，那么就會去鎖定p1指針（這個比較過程以及指針的切換是非?？斓?，這個過程是發(fā)生在內(nèi)存中，相較于IO操作可以忽略不計），將磁盤塊2加載到內(nèi)存中，繼續(xù)判斷，從而將磁盤塊4也加載到內(nèi)存中，此時為葉節(jié)點，葉節(jié)點存儲數(shù)據(jù)，那么就只需要在當前的塊中將3查找出來即可，整個過程只發(fā)生了3次磁盤IO，大大地提高了效率。

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

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

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

• B+樹的查詢效率更加地穩(wěn)定，B樹搜索在非葉子節(jié)點還是葉子節(jié)點結(jié)束都有可能，約靠近根節(jié)點，查找效率越快；而B+樹無論查找的是什么數(shù)據(jù)，最終都需要從根節(jié)點一直走向葉節(jié)點，所有查找所經(jīng)過的次數(shù)都是一樣的；

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

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

2.2 那Hash索引呢？

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

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

• Hash索引不支持模糊查詢，像JoJoX和JoJoA之間沒有關(guān)聯(lián)性，原因在于Hash函數(shù)的不可預(yù)測；

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

四、索引分類

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

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. 唯一索引

索引列的值必須唯一，但允許有空值，語法如下：

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. 復(fù)合索引（聯(lián)合索引）

復(fù)合索引即一個索引中包含多個列，在數(shù)據(jù)庫操作期間，復(fù)合索引所需要的開銷更?。ㄏ鄬τ谙嗤亩鄠€列建立單值索引）；

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. 最左前綴匹配

認識了單值索引和復(fù)合索引，接下來了解最左前綴匹配（leftmost prefix）就容易得多了。什么是最左前綴匹配呢？

假設(shè)現(xiàn)在有三個字段建立了復(fù)合索引CREATE INDEX idx_a_b_c ON demo_table(a, b, c);那么但你的where條件是a、a、b或者啊a、b、c時，都可以命中索引，除此之外都不能命中索引，例如：a、c或者b、c等；

當然有一個例外，當你 select 的字段里有復(fù)合索引里的字段，那么where語句不需要滿足最左前綴匹配，MySQL 也會走索引。
比如：select a from demo_table where b = "xxx";
不過這時走索引不是為了加速查詢（這時候索引對查詢效率提升效果幾乎沒有），而是為了利用下面要講的，覆蓋索引，來減少對數(shù)據(jù)的檢索。

6. 覆蓋索引

覆蓋索引（covering index）的原理很簡單，就像你拿到了一本書的目錄，里頭有標題和對應(yīng)的頁碼，當你想知道第267頁的標題是什么的時候，完全沒有必要翻到267頁去看，而是直接看目錄。
同理，當你要select的字段，已經(jīng)在索引樹里面存儲，那就不需要再去檢索數(shù)據(jù)庫，直接拿來用就行了。

還是上面的例子，你給a、b、c三個字段建了復(fù)合索引，那么對于下面這條sql，就可以走覆蓋索引:

select b, c from demo_table where a = "xxx";

explain一下，你就會發(fā)現(xiàn)extra字段是“Using index”，或者使用explain FORMAT=JSON … ，輸出一個json結(jié)果的結(jié)果，看“using_index”屬性，你會發(fā)現(xiàn)是“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.

按存儲結(jié)構(gòu)分類，有以及幾種索引：

7. 聚簇索引（聚集索引）

聚簇索引就是將數(shù)據(jù)存儲與索引放到了一塊，找到索引也就找到了數(shù)據(jù)。

InnoDB的聚簇索引實際上是在同一個BTree結(jié)構(gòu)中同時存儲了索引和整行數(shù)據(jù)，通過該索引查詢可以直接獲取查詢數(shù)據(jù)行。

聚簇索引不是一種單獨的索引類型，而是一種數(shù)據(jù)的存儲方式，聚簇索引的順序，就是數(shù)據(jù)在硬盤上的物理順序。

在 MySQL 通常聚簇索引是主鍵的同義詞，每張表只包含一個聚簇索引(其他數(shù)據(jù)庫不一定)。

8. 輔助索引（二級索引）

非聚簇索引就是將數(shù)據(jù)存儲于索引分開結(jié)構(gòu)，索引結(jié)構(gòu)的葉子節(jié)點指向了數(shù)據(jù)的對應(yīng)行，MyISAM通過key_buffer把索引先緩存到內(nèi)存中，當需要訪問數(shù)據(jù)時（通過索引訪問數(shù)據(jù)），在內(nèi)存中直接搜索索引，然后通過索引找到磁盤相應(yīng)數(shù)據(jù)（這一步稱為回表查詢），這也就是為什么索引不在key buffer命中時，速度慢的原因。

五、索引設(shè)計原則

索引的設(shè)計可以遵循一些已有的原則，創(chuàng)建索引的時候盡量考慮是否符合這些原則，便于提升索引的使用效率，更高效地使用索引：

• 對查詢次數(shù)頻次較高，且數(shù)據(jù)量較大的表建立索引；

• 索引字段的選擇，最佳候選列應(yīng)當從where子句的條件中提取，如果where子句中的組合比較多，那么應(yīng)當挑選最常用、過濾效果最好的列的組合；

• 使用唯一索引，區(qū)分度高、使用效率越高；

• 索引可以有效的提升查詢數(shù)據(jù)的效率 , 但索引數(shù)量并不是多多益善 , 索引越多 , 維護索引的代價自然也就水漲船高 . 對于插入, 更新, 刪除 等 DML 操作比較繁瑣的表來說 , 索引過多 , 會引入相當高的維護代價 , 降低 DML 操作的效率 , 增加相應(yīng)操作的時間消耗 , 另外索引過多的話 , MySQL也會犯 選擇困難癥 , 雖然最終仍然會找到一個可用的索引 , 但無疑提高了索引的代價 .

• 使用段索引 , 索引創(chuàng)建之后也是使用硬盤來存儲的 , 因此提高索引訪問的 I/O 效率 , 也可以跳高總體的訪問效率 . 假如構(gòu)成索引的字段 總長度比較短 , 那么在給定大小的存儲塊內(nèi) , 可以存儲更多的索引值 , 相應(yīng)的可以有效地提升MySQL訪問索引的 I/O 效率.

• 利用最左前綴的原則 , N個列組合而成的組合索引 , 那么相當于是創(chuàng)建了N 個索引 。如果查詢時where 子句使用了組成該索引的前幾個字段 , 那么這條查詢SQL可以利用組合索引來提升查詢效率

參考文章：

• MySQL索引原理：https://www.cnblogs.com/exceptioneye/p/5452068.html

• MySQL索引分類：https://blog.csdn.net/qq_17707713/article/details/90059408

• MySQL優(yōu)化之索引篇：https://www.cnblogs.com/cryin107/p/13166865.html

免責聲明：本文內(nèi)容由21ic獲得授權(quán)后發(fā)布，版權(quán)歸原作者所有，本平臺僅提供信息存儲服務(wù)。文章僅代表作者個人觀點，不代表本平臺立場，如有問題，請聯(lián)系我們，謝謝！