[[394629]]

索引，可能讓好很多人望而生畏，畢竟每次面試時(shí)候 MySQL 的索引一定是必問(wèn)內(nèi)容，哪怕先撇開(kāi)面試，就在平常的開(kāi)發(fā)中，對(duì)于 SQL 的優(yōu)化也而是重中之重。

可以毫不夸張的說(shuō)，系統(tǒng)中 SQL 的好壞，是能直接決定你系統(tǒng)的快慢的。但是在優(yōu)化之前大家是否想過(guò)一個(gè)問(wèn)題？那就是：我們優(yōu)化的原則是什么？?jī)?yōu)化SQL的理論基礎(chǔ)是什么？

雖然說(shuō)實(shí)踐出真知，但是我更相信理論是支撐實(shí)踐的基礎(chǔ)，因?yàn)槲覀儾豢赡芎翢o(wú)目的的去盲目的實(shí)踐，因?yàn)檫@樣往往事倍功半。

所以說(shuō)了這么多只想告訴大家，在真正的開(kāi)始索引優(yōu)化之前，我們需要徹底搞明白索引的原理。這樣再談優(yōu)化你將覺(jué)得更絲滑~

1、索引的本質(zhì)

索引的本質(zhì)是一種排好序的數(shù)據(jù)結(jié)構(gòu)。這個(gè)我相信其實(shí)大家并不陌生，因?yàn)檎劦剿饕芏嗳俗匀欢坏木蜁?huì)聯(lián)想到字典中的目錄。

沒(méi)錯(cuò)，這樣的類(lèi)比是很形象的，但是如果再往深處說(shuō)，恐怕很多小伙伴就有點(diǎn)張口結(jié)舌了，那既然你已經(jīng)知道了索引的本質(zhì)，那么您就已經(jīng)有了看這篇文章的基礎(chǔ)，相信讀文本文的你，一定會(huì)對(duì)索引的原理有一個(gè)全新的了解。

2、索引的分類(lèi)

在數(shù)據(jù)庫(kù)中，索引是分很多種類(lèi)的（千萬(wàn)不要狹隘的認(rèn)為索引只有 B+ 樹(shù)，那是因?yàn)槲覀兤綍r(shí)使用的基本都是 MySQL）。而不同的種類(lèi)很顯然是為了應(yīng)付不同的場(chǎng)合，那索引到底有那些種類(lèi)呢？下面就讓我們來(lái)大致的了解下。

2.1、Hash 索引

Hash 索引是比較常見(jiàn)的一種索引，他的單條記錄查詢(xún)的效率很高，時(shí)間復(fù)雜度為1。但是，Hash索引并不是最常用的數(shù)據(jù)庫(kù)索引類(lèi)型，尤其是我們常用的Mysql Innodb引擎就是不支持hash索引的。主要有以下原因：

•  Hash索引適合精確查找，但是范圍查找不適合
  •   因?yàn)榇鎯?chǔ)引擎都會(huì)為每一行計(jì)算一個(gè)hash碼，hash碼都是比較小的，并且不同鍵值行的hash碼通常是不一樣的，hash索引中存儲(chǔ)的就是Hash碼，hash 碼彼此之間是沒(méi)有規(guī)律的，且 Hash 操作并不能保證順序性，所以值相近的兩個(gè)數(shù)據(jù)，Hash值相差很遠(yuǎn)，被分到不同的桶中。這就是為什么hash索引只能進(jìn)行全職匹配的查詢(xún)，因?yàn)橹挥羞@樣，hash碼才能夠匹配到數(shù)據(jù)。

對(duì)于 hash 索引，小伙伴們只需要了解到這里就可以了。

2.2、二叉樹(shù)

另外，常見(jiàn)的索引使用的數(shù)據(jù)結(jié)構(gòu)是樹(shù)結(jié)構(gòu)，首先我們來(lái)介紹下最經(jīng)典的二叉樹(shù)。

先來(lái)介紹下二叉樹(shù)的特點(diǎn)：

•   二叉樹(shù)的時(shí)間復(fù)雜度為 O(n)
•   一個(gè)節(jié)點(diǎn)只能有兩個(gè)子節(jié)點(diǎn)。即度不超過(guò)2
•   左子節(jié)點(diǎn) 小于 本節(jié)點(diǎn)，右子節(jié)點(diǎn) 大于 本節(jié)點(diǎn)

首先來(lái)看一下二叉樹(shù)的樣子

但是在極端情況下會(huì)出現(xiàn)鏈化的情況，即節(jié)點(diǎn)一直在某一邊增加。如下圖

二叉樹(shù)中，有一種特殊的結(jié)構(gòu)——平衡二叉樹(shù)，平衡二叉樹(shù)的特點(diǎn)：

•    根節(jié)點(diǎn)會(huì)隨著數(shù)據(jù)的改變而變更
•    數(shù)據(jù)量越多，遍歷次數(shù)越多，IO次數(shù)就越多，就越慢（磁盤(pán)的IO由樹(shù)高決定）

2.4、B樹(shù)（二三樹(shù)）

了解了二叉樹(shù)之后，可以進(jìn)一步談一下什么是B樹(shù)了。B 樹(shù)大概是這樣子的：

從B樹(shù)的結(jié)構(gòu)圖中可以看到每個(gè)節(jié)點(diǎn)中不僅包含數(shù)據(jù)的 key 值，還有 data 值。

而每頁(yè)的存儲(chǔ)空間是有限的，如果 data 比較大，會(huì)導(dǎo)致每個(gè)節(jié)點(diǎn)的 key 存儲(chǔ)的較少，當(dāng)數(shù)據(jù)量較大的時(shí)候，同樣會(huì)導(dǎo)致B樹(shù)很深，從而增加了磁盤(pán) IO 的次數(shù)，進(jìn)而影響查詢(xún)效率。

好了，說(shuō)到這里，常見(jiàn)的索引的種類(lèi)也說(shuō)完了，上面的內(nèi)容僅僅是作為一個(gè)鋪墊，下面我們正式開(kāi)始 MySQL 的 B+ 樹(shù)。

2.5、B+樹(shù)

MySQL 中最常用的索引的數(shù)據(jù)結(jié)構(gòu)是 B+ 樹(shù)，他有以下特點(diǎn)：

1.  在 B+ 樹(shù)中，所有數(shù)據(jù)記錄節(jié)點(diǎn)都是按照鍵值的大小存放在同一層的葉子節(jié)點(diǎn)上，而非葉子結(jié)點(diǎn)只存儲(chǔ)key的信息，這樣可以大大減少每個(gè)節(jié)點(diǎn)的存儲(chǔ)的key的數(shù)量，降低B+ 樹(shù)的高度
2.  B+ 樹(shù)葉子節(jié)點(diǎn)的關(guān)鍵字從小到大有序排列，左邊結(jié)尾數(shù)據(jù)都會(huì)保存右邊節(jié)點(diǎn)開(kāi)始數(shù)據(jù)的指針。
3.  B+ 樹(shù)的層級(jí)更少：相較于 B 樹(shù) B+ 每個(gè)非葉子節(jié)點(diǎn)存儲(chǔ)的關(guān)鍵字?jǐn)?shù)更多，樹(shù)的層級(jí)更少所以查詢(xún)數(shù)據(jù)更快
4.  B+ 樹(shù)查詢(xún)速度更穩(wěn)定：B+ 所有關(guān)鍵字?jǐn)?shù)據(jù)地址都存在葉子節(jié)點(diǎn)上，所以每次查找的次數(shù)都相同所以查詢(xún)速度要比B樹(shù)更穩(wěn)定;
5.  B+ 樹(shù)天然具備排序功能：B+ 樹(shù)所有的葉子節(jié)點(diǎn)數(shù)據(jù)構(gòu)成了一個(gè)有序鏈表，在查詢(xún)大小區(qū)間的數(shù)據(jù)時(shí)候更方便，數(shù)據(jù)緊密性很高，緩存的命中率也會(huì)比B樹(shù)高。
6.  B+ 樹(shù)全節(jié)點(diǎn)遍歷更快：B+ 樹(shù)遍歷整棵樹(shù)只需要遍歷所有的葉子節(jié)點(diǎn)即可，，而不需要像 B 樹(shù)一樣需要對(duì)每一層進(jìn)行遍歷，這有利于數(shù)據(jù)庫(kù)做全表掃描。

好了說(shuō)了這么多的 B+ 樹(shù)的特點(diǎn)，我們來(lái)張圖看看 B+ 樹(shù)到底長(zhǎng)什么樣子（如果看不懂，也沒(méi)有關(guān)系，下文會(huì)一步一步解釋說(shuō)明的）

上面的數(shù)據(jù)頁(yè)就是實(shí)際存放數(shù)據(jù)頁(yè)的地方，且數(shù)據(jù)頁(yè)之間是通過(guò)雙向鏈表進(jìn)行連接的，好了到這里我們就將各個(gè)索引的類(lèi)型快速了解了下，下面我們就開(kāi)始正式B+樹(shù)的分析。

3、主鍵目錄

我們將上圖中的數(shù)據(jù)頁(yè)拿出來(lái)再細(xì)化下，就成了下面的這張圖

我們都知道 MySQL 在存儲(chǔ)數(shù)據(jù)的時(shí)候是以數(shù)據(jù)頁(yè)為最小單位的，且數(shù)據(jù)在數(shù)據(jù)頁(yè)中的存儲(chǔ)是連續(xù)的，數(shù)據(jù)頁(yè)中的數(shù)據(jù)是按照主鍵排序的（沒(méi)有主鍵是由 MySQL自己維護(hù)的 ROW_ID 來(lái)排序的），數(shù)據(jù)頁(yè)和數(shù)據(jù)頁(yè)之間是通過(guò)雙向鏈表來(lái)關(guān)聯(lián)的，數(shù)據(jù)與數(shù)據(jù)時(shí)間是通過(guò)單向鏈表來(lái)關(guān)聯(lián)的。

也就是說(shuō)有一個(gè)在每個(gè)數(shù)據(jù)頁(yè)中，他必然就有一個(gè)最小的主鍵，然后每個(gè)數(shù)據(jù)頁(yè)的頁(yè)號(hào)和最小的主鍵會(huì)組成一個(gè)主鍵目錄（就像上圖中的左邊部分），假設(shè)現(xiàn)在要查找主鍵為 2 的數(shù)據(jù)，通過(guò)二分查找法最后確定下主鍵為 2 的記錄在數(shù)據(jù)頁(yè) 1 中，此時(shí)就會(huì)定位到數(shù)據(jù)頁(yè) 1 接著再去定位主鍵為 2 的記錄，我們先知道大致的流程，細(xì)節(jié)先不要深究，先從宏觀看結(jié)構(gòu)原理，再到微觀看實(shí)現(xiàn)原理。

剛剛上面是說(shuō)的其實(shí)可以理解為是主鍵索引，主鍵索引也是最簡(jiǎn)單的最基礎(chǔ)的索引。這個(gè)時(shí)候大家應(yīng)該知道為什么你建立了主鍵查詢(xún)就能變快了吧？

4、索引頁(yè)

但是現(xiàn)在假設(shè)有很多很多的是數(shù)據(jù)頁(yè)，那是不是對(duì)應(yīng)的主鍵目錄會(huì)很大很大呢？

那假設(shè)有1000萬(wàn)條記錄、5000萬(wàn)條記錄呢？是不是就算是二分法查找，其效率也依舊是很低的，所以為了解決這種問(wèn)題 MySQL 又設(shè)計(jì)出了一種新的存儲(chǔ)結(jié)構(gòu)—索引頁(yè)。例如有下面這樣情況，

假設(shè)上面的主鍵目錄中的記錄是非常非常多的，此時(shí)上面的結(jié)構(gòu)是演變成這樣子的，MySQL 會(huì)將里面的記錄拆分到不同的索引頁(yè)中，也就是下面這樣子的

索引頁(yè)中記錄的是每頁(yè)數(shù)據(jù)頁(yè)的頁(yè)號(hào)和該數(shù)據(jù)頁(yè)中最小的主鍵的記錄，也就是說(shuō)最小主鍵和數(shù)據(jù)頁(yè)號(hào)不是單純的維護(hù)在主鍵目錄中了，而是演變成了索引頁(yè)，索引頁(yè)和數(shù)據(jù)頁(yè)類(lèi)似，一張不夠存就分裂到下一張。

假如現(xiàn)在要查找 id=20 的這條記錄，咦？那我應(yīng)該到哪個(gè)索引頁(yè)中查找該條記錄呢？所以這個(gè)時(shí)候肯定是需要去維護(hù)索引頁(yè)的。

沒(méi)錯(cuò)，MySQL 也是這么設(shè)計(jì)的，也就是說(shuō) MySQL 同時(shí)也設(shè)計(jì)出了用于維護(hù)索引頁(yè)的數(shù)據(jù)結(jié)構(gòu)，其實(shí)也還叫索引頁(yè)，只不過(guò)他們是在不同的層級(jí)，類(lèi)似下面這樣子的：

也就是說(shuō)維護(hù)索引頁(yè)的索引頁(yè)是在真正存儲(chǔ)記錄和數(shù)據(jù)頁(yè)的索引頁(yè)的上一層，現(xiàn)在如果你想查找 id=20 的這條記錄，那就是從最上層的索引頁(yè)開(kāi)始查找，通過(guò)二分法查找，很快就能夠定位到 id=20 s這條記錄是在索引頁(yè) 2 上，然后到就索引頁(yè) 2 上面查找，接著就是和之前一樣了（注意，索引頁(yè)中的記錄也是通過(guò)單向鏈表連接的），根據(jù)各個(gè)最小的主鍵能夠定位到 id=20 是在數(shù)據(jù)頁(yè)5上，假設(shè)數(shù)據(jù)頁(yè)5是這樣子的

那這個(gè)時(shí)候你是不是能夠想明白數(shù)據(jù)是怎么定位的了呢？

5、索引頁(yè)的分層

好，既然你已經(jīng)知道到索引頁(yè)太多會(huì)往上一層擴(kuò)散，那現(xiàn)在假設(shè)上一層的索引頁(yè)記錄也太多了，那該怎么辦？很簡(jiǎn)單，繼續(xù)分裂，再往上一層繼續(xù)，不廢話(huà)，我來(lái)畫(huà)圖幫助大家理解

我看明白了，你看明白了嗎？我們來(lái)模擬一個(gè)查找的過(guò)程，假設(shè)你要查找 37 這條記錄，說(shuō)實(shí)話(huà)我根本不知道這條記錄在哪里。好，現(xiàn)在我們就來(lái)模擬 MySQL 的查找過(guò)程，首先從最頂層的索引頁(yè)開(kāi)始查找，因?yàn)?id=37，因此定位到了索引頁(yè)16，然后到索引頁(yè) 16 中繼續(xù)查找，此時(shí)同樣能夠定位到 id=37 在索引頁(yè) 3 中，然后繼續(xù)查找，最終能夠定位到數(shù)據(jù)實(shí)在數(shù)據(jù)頁(yè) 8 中，假設(shè)數(shù)據(jù)頁(yè) 8 是這樣子的

是不是很完美？如果非要我把上面的圖畫(huà)完整，那....小弟義不容辭（圖太大了，索引頁(yè)中數(shù)據(jù)的鏈表結(jié)構(gòu)就不畫(huà)出來(lái)了）

這個(gè)時(shí)候機(jī)智的你是不是已經(jīng)發(fā)現(xiàn)了什么小秘密？他是不是很像一顆二叉樹(shù)？實(shí)際上這就是一顆 B+ 樹(shù)的結(jié)構(gòu)，這也是數(shù)據(jù)在磁盤(pán)中真正存儲(chǔ)的物理結(jié)構(gòu)。B+樹(shù)的特性是什么呢？B+樹(shù)，也是二叉搜索樹(shù)的一種，但是他的數(shù)據(jù)僅僅存儲(chǔ)在葉子節(jié)點(diǎn)（在這里就是數(shù)據(jù)頁(yè)），像這種索引頁(yè)+數(shù)據(jù)頁(yè)組成的組成的B+樹(shù)就是聚簇索引(這句話(huà)很重要)。

聚簇索引是 MySQL 基于主鍵索引結(jié)構(gòu)創(chuàng)建的

6、非主鍵索引

但是現(xiàn)在問(wèn)題又來(lái)了，既然這里強(qiáng)調(diào)的是主鍵索引，那我們平時(shí)開(kāi)發(fā)中除了主鍵索引其他的索引也用的不少，這時(shí)候該怎么辦？假設(shè)你現(xiàn)在對(duì)name、age建立索引。現(xiàn)在回顧下主鍵索引，是不是在插入數(shù)據(jù)的時(shí)候基于主鍵的順序去維護(hù)一個(gè) B+ 樹(shù)的？

而實(shí)際上非主鍵索引其原理是一樣的，MySQL 都是去維護(hù)一顆 B+ 樹(shù)，說(shuō)白了，你建立多少個(gè)索引，MySQL 就會(huì)幫你維護(hù)多少的B+樹(shù)（這下是不是也突然想明白了為什么索引不能建立太多了？以前就知道不能建立太多索引，因?yàn)樗饕矔?huì)占用空間，實(shí)際上這就是根本原因）

假如現(xiàn)在真的對(duì)name+age建立索引，那此時(shí)是存放的呢？此時(shí) MySQL 根據(jù)會(huì) name+age 維護(hù)一個(gè)單獨(dú)的 B+ 樹(shù)結(jié)構(gòu)，數(shù)據(jù)依舊是存放在數(shù)據(jù)頁(yè)中的，只不過(guò)是原來(lái)數(shù)據(jù)中的每條記錄寫(xiě)的是 id=xx，現(xiàn)在寫(xiě)的是name=xx，age=xx，id=xx，不管怎么樣，主鍵肯定會(huì)存放的，先來(lái)張圖壓壓驚

在插入數(shù)據(jù)的時(shí)候，MySQL 首先會(huì)根據(jù) name 進(jìn)行排序，如果 name 一樣，就根據(jù)聯(lián)合索引中的 age 去排序，如果還一樣，那么就會(huì)根據(jù) 主鍵 字段去排序。插入的原理就是這樣子的。

此時(shí)每個(gè)數(shù)據(jù)頁(yè)中的記錄存放的實(shí)際是索引字段和主鍵字段，而其他字段是不存的（為什么不存放？一樣的數(shù)據(jù)到處存放很浪費(fèi)空間的，也沒(méi)必要，所以才會(huì)有下面的索引優(yōu)化），至于查找，原理和過(guò)程跟聚簇索引一樣，這里就不再贅述，但是，下面說(shuō)的內(nèi)容卻是至關(guān)重要的：假設(shè)現(xiàn)在執(zhí)行這樣的SQL： 

SELECT name FROM student WHERE name='wx' 

那么此時(shí)的查詢(xún)是完美的，使用到了索引且不需要回表

7.回表

是這樣子的，現(xiàn)在要根據(jù) name 查找到該條記錄，且查詢(xún)的字段（即 select 后面的查詢(xún)字段）也僅僅有 name（只要是在 name,age,id 這三個(gè)字段中都可以）這個(gè)時(shí)候是能夠直接獲取到最終的記錄的

換句話(huà)說(shuō)，因?yàn)槁?lián)合索引中的記錄也僅僅有 name，age，id，所以在查詢(xún)的如果也僅僅查詢(xún)這三個(gè)字段，那么在該B+樹(shù)中就能夠查詢(xún)到想要的結(jié)果了。

那現(xiàn)在假設(shè)查詢(xún)的 SQL 是這樣子的（我們假設(shè) student 中還有除了name，age，id 其他的字段 ） 

SELECT * FROM student WHERE name='wx' 

那這下子就完蛋了，因?yàn)槟悻F(xiàn)在雖然根據(jù) name 很快的定位到了該條記錄，但是因?yàn)?name+age 不是聚簇索引，此時(shí)的 B+ 樹(shù)的數(shù)據(jù)頁(yè)中存放的僅僅是自己關(guān)聯(lián)的索引和主鍵索引字段，并不會(huì)存其他的字段，所以這個(gè)時(shí)候其他的屬性值是獲取不到的，這時(shí)候該怎么辦？

這種情況下，MySQL 就需要進(jìn)行回表查詢(xún)了。此時(shí) MySQL 就會(huì)根據(jù)定位到的某條記錄中的 id 再次進(jìn)行聚簇索引查找，也就是說(shuō)會(huì)根據(jù) id 去維護(hù) id 的那么 B+ 樹(shù)中查找。因?yàn)榫鄞厮饕袛?shù)據(jù)頁(yè)記錄的是一條記錄的完整的記錄，這個(gè)過(guò)程就叫回表。

再?gòu)?qiáng)調(diào)下回表的含義：根據(jù)非主鍵索引查詢(xún)到的結(jié)果并沒(méi)有查找的字段值，此時(shí)就需要再次根據(jù)主鍵從聚簇索引的根節(jié)點(diǎn)開(kāi)始查找，這樣再次查找到的記錄才是完成的。

最后，讓我一起看下 MySQL 對(duì)于非主鍵索引的維護(hù)過(guò)程：

對(duì)于非主鍵索引（一般都是聯(lián)合索引），在維護(hù) B+ 樹(shù)的時(shí)候，會(huì)根據(jù)聯(lián)合索引的字段依次去判斷，假設(shè)聯(lián)合索引為：name + address + age，那么 MySQL 在維護(hù)該索引的 B+ 樹(shù)的時(shí)候，首先會(huì)根據(jù) name 進(jìn)行排序，name 相同的話(huà)會(huì)根據(jù)第二個(gè) address 排序，如果 address 也一樣，那么就會(huì)根據(jù) age 去排序，如果 age 也一樣，那么就會(huì)根據(jù)主鍵字段值去排序，且對(duì)于非主鍵索引，MySQL 在維護(hù) B+ 樹(shù)的時(shí)候，僅僅是維護(hù)索引字段和主鍵字段。