前言

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

索引概述

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

這是一段很抽象的描述，我們很難想象出它到底是怎樣的一種結構。

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

我們所說的掃描過程實際上是將磁盤中的數據加載到內存中的過程，這就是我們通常所說的磁盤IO操作，磁盤IO是非常高昂的操作，訪問磁盤的成本大概是訪問內存的十萬倍左右。因此，我們優化的出發點就有了：要盡可能的減少IO。

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

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

有一種經典的數據結構，二叉樹，大概長這樣：

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

看到這里我們就明白了，樹越矮，節點數就越少，所需磁盤IO次數越少，效率就越高。

如果讓樹矮一點呢?數據量一定的情況下，自然是每個節點掛載的數據越多，節點就越少，樹也就越矮!

這就出現了B樹的概念。B樹是一個多叉樹，每個節點可以掛載多個子節點，大概是這么個樣子：

很顯然，樹矮了。

實際上，mysql的InnoDB 引擎使用的正是B樹的存儲結構，更為準確一點，是B+樹，它是在B-樹的基礎上改進而來，它將表數據只存儲在葉子節點上， 而其他非葉子節點只存儲索引的key。大概是這么個樣子：

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

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

主鍵索引

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

再來看一下非主鍵索引。

非主鍵索引

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

這樣就完了嗎?

顯然不是，因為非主鍵索引存儲的，只是一個主鍵ID值，而我們需要的是完整的表數據，我們通過兩次IO操作拿到主鍵ID值后，還要再走一遍主鍵索引的流程，才能拿到完整數據，也就是說，非主鍵索引查找我們所需的數據，要執行四次IO操作。

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

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