前言

索引是一個(gè)比較抽象的東西，不同于數(shù)據(jù)庫運(yùn)維人員，開發(fā)人員往往不需要理解的那么深刻，而只需要大概知道它是一個(gè)什么東西，在腦海中有一個(gè)大致的輪廓圖就好了，能夠幫助我們更好的使用索引和明白為什么要這么使用，這就達(dá)到目的了。因此，本文針對(duì)的是開發(fā)人員，講的也比較淺顯，請(qǐng)各位大佬輕噴。

索引概述

索引是儲(chǔ)存在磁盤中的一種特殊文件(也可能有部分在內(nèi)存中)。為什么說它特殊呢，它是將數(shù)據(jù)庫表中的某一列或幾列的值進(jìn)行排序后的具有特殊搜索結(jié)構(gòu)的文件。通過它，我們可以快速從數(shù)據(jù)庫表中讀取所需的信息。

這是一段很抽象的描述，我們很難想象出它到底是怎樣的一種結(jié)構(gòu)。

假設(shè)我們有一張100w數(shù)據(jù)的表，id從1排到了1000000。在沒有索引的情況下，我們要查找id=666666的數(shù)據(jù)，由于是無序的，它也不知道id=666666的數(shù)據(jù)藏在哪里，只能一條條的逐一排查，運(yùn)氣不好的話，可能掃描到最后一行。

我們所說的掃描過程實(shí)際上是將磁盤中的數(shù)據(jù)加載到內(nèi)存中的過程，這就是我們通常所說的磁盤IO操作，磁盤IO是非常高昂的操作，訪問磁盤的成本大概是訪問內(nèi)存的十萬倍左右。因此，我們優(yōu)化的出發(fā)點(diǎn)就有了：要盡可能的減少IO。

我們首先想到的，要是這個(gè)100w數(shù)據(jù)有序就好了，這樣就可以用二分法，先掃描50w-100w的數(shù)據(jù)，再掃描50w-75w的數(shù)據(jù)。。。這樣就可以大幅減少掃描的次數(shù)，也就達(dá)到了減少磁盤IO的目的。

還有沒有更高效的方法呢?

有一種經(jīng)典的數(shù)據(jù)結(jié)構(gòu)，二叉樹，大概長這樣：

這里不講它的原理啊，特點(diǎn)啊，時(shí)間復(fù)雜度計(jì)算啊等等這些，感興趣的可以搜索一下。這里只需要知道一點(diǎn)，它的搜索效率很高，但是有一個(gè)缺點(diǎn)：每個(gè)節(jié)點(diǎn)存儲(chǔ)的數(shù)據(jù)量很少。這就導(dǎo)致了同樣數(shù)量級(jí)的數(shù)據(jù)，在二叉樹中不可避免的會(huì)增加樹的高度，而樹高的增加，就會(huì)導(dǎo)致IO次數(shù)的增多。比如我們要拿到1這個(gè)數(shù)據(jù)，那么讀取的順序?qū)⑹?-5-2-1，先將7的數(shù)據(jù)從磁盤加載到內(nèi)存中，再將5的數(shù)據(jù)從磁盤加載到內(nèi)存中，然后是2,1，最終經(jīng)過4次IO拿到所需數(shù)據(jù)。如果數(shù)據(jù)量再大，樹高再增加，IO次數(shù)也相應(yīng)的會(huì)增多。這里是有一個(gè)公式的，高度是與總節(jié)點(diǎn)數(shù)正相關(guān)。

看到這里我們就明白了，樹越矮，節(jié)點(diǎn)數(shù)就越少，所需磁盤IO次數(shù)越少，效率就越高。

如果讓樹矮一點(diǎn)呢?數(shù)據(jù)量一定的情況下，自然是每個(gè)節(jié)點(diǎn)掛載的數(shù)據(jù)越多，節(jié)點(diǎn)就越少，樹也就越矮!

這就出現(xiàn)了B樹的概念。B樹是一個(gè)多叉樹，每個(gè)節(jié)點(diǎn)可以掛載多個(gè)子節(jié)點(diǎn)，大概是這么個(gè)樣子：

很顯然，樹矮了。

實(shí)際上，mysql的InnoDB 引擎使用的正是B樹的存儲(chǔ)結(jié)構(gòu)，更為準(zhǔn)確一點(diǎn)，是B+樹，它是在B-樹的基礎(chǔ)上改進(jìn)而來，它將表數(shù)據(jù)只存儲(chǔ)在葉子節(jié)點(diǎn)上， 而其他非葉子節(jié)點(diǎn)只存儲(chǔ)索引的key。大概是這么個(gè)樣子：

這樣一個(gè)3層的B+樹就可以表示千萬級(jí)的數(shù)據(jù)。而要訪問到最終的數(shù)據(jù)，只需要3次IO，這在性能上是一個(gè)巨大的提升。其實(shí)，樹的根節(jié)點(diǎn)往往在內(nèi)存中，那么訪問磁盤的次數(shù)就更少了。

接下來，我們通過主鍵索引和非主鍵索引來說明一下整個(gè)的索引流程。首先有一張表，表結(jié)構(gòu)長這樣：

主鍵索引

如上圖所示，葉子節(jié)點(diǎn)中存儲(chǔ)的是表中的整行數(shù)據(jù)，非葉子節(jié)點(diǎn)中存儲(chǔ)的是主鍵的key值，我們通過主鍵ID去查某一條數(shù)據(jù)的時(shí)候，比如說查ID= 8的數(shù)據(jù)。先將非葉子節(jié)點(diǎn)的索引key值加載到內(nèi)存中，產(chǎn)生一次IO，定位到ID=8的數(shù)據(jù)應(yīng)該在P2所指向的磁盤頁中，于是系統(tǒng)再執(zhí)行一次IO操作，將P2指向的磁盤頁中的數(shù)據(jù)加載到內(nèi)存中，在內(nèi)存中經(jīng)過篩選，找到ID=8的數(shù)據(jù)返回給客戶端。這樣就完成了ID=8數(shù)據(jù)的索引查詢。整個(gè)過程執(zhí)行了兩次IO操作。

再來看一下非主鍵索引。

非主鍵索引

非主鍵索引中以name為索引字段。可以看到跟主鍵索引不同的是，非主鍵索引中葉子節(jié)點(diǎn)存儲(chǔ)的不是完整的表數(shù)據(jù)，而是表數(shù)據(jù)的主鍵ID值。索引查詢過程跟主鍵索引一樣，先將非葉子節(jié)點(diǎn)的索引key值加載到內(nèi)存，找到指向的磁盤頁，再將磁盤頁中的數(shù)據(jù)加載到內(nèi)存，在內(nèi)存中篩選出所需的數(shù)據(jù)。這個(gè)過程也是執(zhí)行了兩次IO操作。

這樣就完了嗎?

顯然不是，因?yàn)榉侵麈I索引存儲(chǔ)的，只是一個(gè)主鍵ID值，而我們需要的是完整的表數(shù)據(jù)，我們通過兩次IO操作拿到主鍵ID值后，還要再走一遍主鍵索引的流程，才能拿到完整數(shù)據(jù)，也就是說，非主鍵索引查找我們所需的數(shù)據(jù)，要執(zhí)行四次IO操作。

通過非主鍵索引拿到ID，再執(zhí)行主鍵索引的過程，叫做回表。是不是很熟悉?

理解了這些，其實(shí)再想想為什么不用select *，盡量用到覆蓋索引，也就不難理解了，一切的初衷都是為了：減少磁盤IO。