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

索引的常見模型

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

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

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

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

InnoDB 的索引模型

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

每一個索引在 InnoDB 中對應一棵 B+ 樹。

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

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

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

也就是說，基于非主鍵索引的查詢，會多一次搜索 B+ 樹。 所以，在實際應用中，應當盡量使用主鍵查詢。