索引是什么？ 索引就是為了提高查詢效率，類似于書(shū)的目錄的東西。

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

索引的實(shí)現(xiàn)方式有很多種，這里主要說(shuō)明三種：哈希表、有序數(shù)組和搜索樹(shù)

哈希表
哈希表就是一種 key-value 存儲(chǔ)數(shù)據(jù)的結(jié)構(gòu)，通過(guò)尋找key，就可以取出對(duì)應(yīng)的 value。 哈希的實(shí)現(xiàn)方式，就是把 key 通過(guò)一個(gè) 哈希函數(shù) 將其映射到數(shù)組的某個(gè)確定的位置，然后將 value 放入這個(gè)位置。
哈希表的優(yōu)勢(shì)就是單值查詢速度很快，并且插入速度也很快。但是缺點(diǎn)就是，因?yàn)榇鎯?chǔ)不是有序的，所以哈希索引做區(qū)間查詢的速度很慢。
總結(jié)：哈希表結(jié)構(gòu)只適用于等值查詢的場(chǎng)景，比如 Memcached 及其他一些 NoSQL 引擎。

有序數(shù)組
有序數(shù)組則在等值查詢和區(qū)間查詢都表現(xiàn)優(yōu)秀。
如果要查詢某個(gè)key，因?yàn)閿?shù)組是有序的，通過(guò) 二分法很快就能查到，復(fù)雜度為 O(log(N))
對(duì)于區(qū)間查詢，只需要先通過(guò)二分法查詢左值，然后向右遍歷找到右值。
但是有序數(shù)組的插入效率很低，如果往中間插入一個(gè)數(shù)據(jù)，就需要后面所有的記錄跟著挪動(dòng)。
總結(jié)：有序數(shù)組等值查詢和區(qū)間查詢效率都很高，但是插入效率低，只適用于靜態(tài)存儲(chǔ)引擎。

搜索樹(shù)
搜索二叉樹(shù)是非常經(jīng)典的搜索樹(shù)，其特點(diǎn)是：所有左子節(jié)點(diǎn)小于父節(jié)點(diǎn)的值，所有右節(jié)點(diǎn)大于父節(jié)點(diǎn)的值。查詢的時(shí)間復(fù)雜度為 O(log(N))。
當(dāng)然為了維持 O(log(N)) 的查詢復(fù)雜度，就必須保持這棵樹(shù)是平衡二叉樹(shù)，所以其更新復(fù)雜度也是 O(log(N))。
然而，實(shí)際上，二叉搜索樹(shù)并不適用于索引，這是因?yàn)槠胶舛鏄?shù)只有兩個(gè)子節(jié)點(diǎn)，其層高會(huì)比較高。而索引不止存在內(nèi)存中，還要寫(xiě)到磁盤(pán)上。而過(guò)高的層高會(huì)導(dǎo)致頻繁訪問(wèn)磁盤(pán)，導(dǎo)致查詢效率下降。
為了讓其盡量少訪問(wèn)磁盤(pán)，就必須讓查詢過(guò)程訪問(wèn)盡量少的數(shù)據(jù)塊。所以，索引結(jié)構(gòu)一般使用的是N叉樹(shù)，這里的N取決于數(shù)據(jù)塊大小。

InnoDB 的索引模型

在 InnoDB 中，表都是根據(jù)主鍵順序以索引的形式存放的。另外，InnoDB 使用的是 B+樹(shù)的索引模型，所以數(shù)據(jù)都是存儲(chǔ)在 B+ 樹(shù)中的。

每一個(gè)索引在 InnoDB 中對(duì)應(yīng)一棵 B+ 樹(shù)。

索引分為 主鍵索引 和 非主鍵索引。
主鍵索引（聚簇索引）的葉子節(jié)點(diǎn)存的是整行數(shù)據(jù)。
非主鍵索引（二級(jí)索引）的葉子節(jié)點(diǎn)存的是主鍵的值。

那么，基于主鍵索引和非主鍵索引的查詢有什么區(qū)別呢？

• 如果是根據(jù)主鍵查詢，那么只需要搜索主鍵對(duì)應(yīng)的 B+ 樹(shù)
• 如果是根據(jù)非主鍵查詢，那么就必須要先查詢 非主鍵 對(duì)應(yīng)的 B+ 樹(shù)，取出對(duì)應(yīng)的主鍵的值，然后再去 主鍵索引 查詢整行值。這個(gè)過(guò)程被稱回表。

也就是說(shuō)，基于非主鍵索引的查詢，會(huì)多一次搜索 B+ 樹(shù)。 所以，在實(shí)際應(yīng)用中，應(yīng)當(dāng)盡量使用主鍵查詢。