什么是索引？索引又是用來干什么的？

一句話概括就是：索引就是為了調(diào)高數(shù)據(jù)的查詢效率

就像書的目錄一樣，如果你想找到某個知識點，通常我們都是翻看書的目錄。同樣，索引其實就是數(shù)據(jù)庫表的“目錄”。

索引的常見模型

實現(xiàn)索引的數(shù)據(jù)結(jié)構(gòu)有很多，最常見的也是比較簡單的數(shù)據(jù)結(jié)構(gòu)有哈希表，有序數(shù)組和搜索樹。

哈希表

哈希表是一種以鍵-值（key-value）形式存儲數(shù)據(jù)的結(jié)構(gòu)，我們只需要輸入查找的鍵key，就可以得到對應(yīng)的值value。哈希的思路是，把值放在數(shù)組里，用一個哈希函數(shù)把key換成一個確定的位置，然后把value放在數(shù)組的這個位置。

但是會有一種情況，就是多個不同的key有可能通過哈希函數(shù)的換算得到相同的位置，解決這種情況就是在這個位置拉出一個鏈表。

假如我們有一張用戶表，用戶昵稱（nickname）字段使用的是哈希索引，我們需要根據(jù)昵稱查詢用戶信息，這時哈希索引的示意圖如下所示：

哈希表

示意圖中，user3和user4根據(jù)nickname字段算出來的位置都是4，所以在4位置用了一個鏈表表示，當(dāng)我們在查詢的時候，比如我們根據(jù)nickname4查詢，查詢步驟就是：先使用哈希函數(shù)計算nickname3得到4，然后遍歷鏈表直到找到user4。

優(yōu)點：因為哈希索引是根據(jù)索引字段計算位置，所以它的插入和根據(jù)key的查找會很快。

缺點：因為哈希索引是計算位置，而這個位置不一定是遞增的，所以使用哈希索引做范圍查詢速度會很慢。如果要根據(jù)范圍查找數(shù)據(jù)，就必須全部掃描一遍索引才能找到。

適合場景：哈希表適用于等值查詢的場景，比如Redis或者其他的NoSQL數(shù)據(jù)庫。

有序數(shù)組

還是上面的例子，如果是使用有序數(shù)組索引的話，示意圖如下：

有序數(shù)組

這個數(shù)組是根據(jù)nickname遞增順序保存的，如果我們要查nickname2對應(yīng)的用戶信息，用二分查找就可以很快找到對應(yīng)的結(jié)果，時間復(fù)雜度為O(log(N))。

當(dāng)然這個數(shù)據(jù)結(jié)構(gòu)也是支持范圍查詢的，如果我們想要查到[nicknameX,nicknameY]這個區(qū)間的用戶信息，我們只需要根據(jù)二分查找找到第一個nicknameX，然后向右遍歷數(shù)組，找到找到最后一個nicknameY的用戶即可。

優(yōu)點：有序數(shù)組因為存入的數(shù)據(jù)已經(jīng)是排好序的，所以根據(jù)等值查到和范圍查到都比較快。

缺點：如果我們需要往數(shù)組中間插入一個值或者刪除中間的某個值，那就需要挪動這個值所在位置后面的所有元素，成本比較高。

適合場景：有序數(shù)組適用于靜態(tài)存儲引擎，存儲不會再修改的數(shù)據(jù)，比如某個城市過去的人口數(shù)。

二叉搜索樹

還是上面的例子，如果是二叉搜索樹的話，示意圖如下：

二叉搜索樹

二叉樹特點：每個節(jié)點的左兒子小于父節(jié)點，父節(jié)點小于右兒子。如果我們要查user2的話，跟著上圖我們的查詢路徑就是：userA -> userB -> userD -> user2。時間復(fù)雜度為O(log(N))。

優(yōu)點：查詢效率高

缺點：因為索引不止存在于內(nèi)存中，也要寫到磁盤里。如果一個二叉樹高度為20，我們查詢某個用戶信息就要訪問20次磁盤，這個效率是非常低的。

適用場景：二叉樹適用于表數(shù)據(jù)比較少的引擎。

為了減少樹的高度，也就是減少對磁盤的訪問，數(shù)據(jù)庫索引就不能用二叉樹。那么既然有二叉數(shù)，那就有N叉樹，這里的N取決于數(shù)據(jù)塊的大小。

在MySQL中，索引是在存儲引擎層實現(xiàn)的，不同存儲引擎的索引使用的數(shù)據(jù)結(jié)構(gòu)可能都不一樣。InnoDB的索引使用的數(shù)據(jù)結(jié)構(gòu)為B+樹。

InnoDB的索引模型

在InnoDB中，表都是根據(jù)主鍵順序以索引的i形式存放的，這種存儲方式的表稱為索引組織表。每一個索引在InndDB中都對應(yīng)一棵B+樹。

假如我們有下面一張表：

create table T(
   id int primary key, 
   k int not null, 
   index (k)
)engine=InnoDB;

表中 R1~R5 的 (ID,k) 值分別為 (100,1)、(200,2)、(300,3)、(500,5) 和 (600,6)，兩棵樹的示例示意圖如下：

B+樹

從圖中可以看出，根據(jù)葉子節(jié)點的數(shù)據(jù)，索引類型分為主鍵索引和非主鍵索引。

主鍵索引和非主鍵索引的區(qū)別：

1. 主鍵索引的葉子節(jié)點存的是整行數(shù)據(jù)，在InnoDB里，主鍵索引也叫做聚簇索引；非主鍵索引的葉子節(jié)點存的內(nèi)容是主鍵的值，在InnoDB里，非主鍵索引也叫做二級索引。

2. 如果根據(jù)主鍵查詢，則只需要查找id索引樹即可；如果根據(jù)非主鍵索引查找（查找的數(shù)據(jù)不只有主鍵），則需要查找k索引樹找到對應(yīng)的主鍵，然后根據(jù)主鍵到id索引在查找一次。這個過程叫回表。

結(jié)束！