一、MySQL索引起步

1. 索引的概述

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

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

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

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

優(yōu)勢(shì)

劣勢(shì)：

3. 什么時(shí)候建立索引

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

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

1. 索引分類與引擎對(duì)索引的支持

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

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

MyISAM、InnoDB、Memory三種存儲(chǔ)引擎對(duì)各種索引類型的支持：

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

  

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

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

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

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

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

那么訪問一次磁盤的時(shí)間，即一次磁盤IO的時(shí)間約等于5+4.17 = 9 ms左右，聽起來(lái)還挺不錯(cuò)的，但要知道一臺(tái)500 -MIPS（Million Instructions Per Second）的機(jī)器每秒可以執(zhí)行5億條指令，因?yàn)橹噶钜揽康氖请姷男再|(zhì)，換句話說(shuō)執(zhí)行一次IO的消耗的時(shí)間段下cpu可以執(zhí)行約450萬(wàn)條指令，數(shù)據(jù)庫(kù)動(dòng)輒十萬(wàn)百萬(wàn)乃至千萬(wàn)級(jí)數(shù)據(jù)，每次9毫秒的時(shí)間，顯然是個(gè)災(zāi)難，所以我們要想辦法降低IO次數(shù)。下圖是計(jì)算機(jī)硬件延遲的對(duì)比圖，供大家參考：

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

2. MySQL中的B+ 樹

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

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

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

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

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

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

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

• 增刪文件時(shí)，B+樹的效率更高，因?yàn)樗械膁ata都在葉子節(jié)點(diǎn)中，而B樹刪減節(jié)點(diǎn)時(shí)還需要分裂，中間節(jié)點(diǎn)向上等操作；

2.2 那Hash索引呢？

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

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

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

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

四、索引分類

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

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

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

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

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

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ù)合索引即一個(gè)索引中包含多個(gè)列，在數(shù)據(jù)庫(kù)操作期間，復(fù)合索引所需要的開銷更?。ㄏ鄬?duì)于相同的多個(gè)列建立單值索引）；

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 ;

---

接下來(lái)介紹以下最左前綴匹配域覆蓋索引：

5. 最左前綴匹配

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

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

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

6. 覆蓋索引

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

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

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

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

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

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

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

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

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

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

8. 輔助索引（二級(jí)索引）

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

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

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

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

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

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

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

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

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

參考文章：

• 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

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