什么是索引？索引又是用來(lái)干什么的？

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

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

索引的常見(jiàn)模型

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

哈希表

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

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

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

哈希表

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

優(yōu)點(diǎn)：因?yàn)楣Ｋ饕歉鶕?jù)索引字段計(jì)算位置，所以它的插入和根據(jù)key的查找會(huì)很快。

缺點(diǎn)：因?yàn)楣Ｋ饕怯?jì)算位置，而這個(gè)位置不一定是遞增的，所以使用哈希索引做范圍查詢速度會(huì)很慢。如果要根據(jù)范圍查找數(shù)據(jù)，就必須全部掃描一遍索引才能找到。

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

有序數(shù)組

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

有序數(shù)組

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

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

優(yōu)點(diǎn)：有序數(shù)組因?yàn)榇嫒氲臄?shù)據(jù)已經(jīng)是排好序的，所以根據(jù)等值查到和范圍查到都比較快。

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

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

二叉搜索樹(shù)

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

二叉搜索樹(shù)

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

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

缺點(diǎn)：因?yàn)樗饕恢勾嬖谟趦?nèi)存中，也要寫(xiě)到磁盤(pán)里。如果一個(gè)二叉樹(shù)高度為20，我們查詢某個(gè)用戶信息就要訪問(wèn)20次磁盤(pán)，這個(gè)效率是非常低的。

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

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

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

InnoDB的索引模型

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

假如我們有下面一張表：

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)，兩棵樹(shù)的示例示意圖如下：

B+樹(shù)

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

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

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

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

結(jié)束！