索引的重要性應該不需要我講，做后端服務的同學都知道。但是索引是以什么結構存儲的？每種數(shù)據(jù)庫引擎都一樣嗎？為什么索引的查詢這么快？讓我們一起來解下這些問題。

復雜度選擇

索引存在的意義就是為了提高我們查詢的速度，而查詢的速度一般與所做查詢的次數(shù)成正比。

算法時間復雜度

上圖列出了各種復雜度在數(shù)據(jù)量變化下的操作次數(shù)變化曲線?？梢钥闯觯?/p>

• O(1) 是最好的，但是這種時間復雜度比較難以達到。搜索一個好的哈希表復雜度是 O(1)。
• O(n2) 是很差的，如果達到這種復雜度基本是讓人難以接受的。糟糕的排序算法如冒泡排序的平局時間復雜度就是 O(n2)
• O(2n)、O(nn) 直接就不用考慮
• O(n)、O(log(n)n) 的復雜度在隨著數(shù)據(jù)量的增長下也增長較快。最好的排序算法復雜度為 O(log(n)n)。
• O(log(n)) 的復雜度較為容易實現(xiàn)，并且隨著數(shù)據(jù)量的增長也可以保持很緩慢的增長。搜索一個均衡的樹的復雜度為 O(log(n))。

索引數(shù)據(jù)結構

從上面的復雜度分析中我們可以看出，O(1)，O(log(n))肯定是構建索引時候比較傾向的復雜度。而數(shù)據(jù)庫采用的 Hash 結構，B+TREE 結構也是可以達到這兩種復雜度。

Hash

hash索引

這個一個有 10 個哈希桶哈希表（跟java中的HashMap結構一致）。

如果要找元素 78：1)計算 78 的哈希碼等于 8。2)查找哈希桶8，找到的第一個元素是78并返回。查詢僅耗費了 2 次運算。

如果要找元素 59：1)計算 59 的哈希碼等于 9。2)查找哈希桶 9，第一個找到的元素是 99。99 不等于 59。用同樣的邏輯，查找第二個元素(9)，第三個(79)，……，最后一個(29)。元素不存在。搜索耗費了 7 次運算。

你可以看到，根據(jù)你查找的值，成本并不相同。如果我把哈希函數(shù)改為關鍵字對 1,000,000 取模（就是說取后 6 位數(shù)字），第二次搜索只消耗一次運算，因為哈希桶 00059 里面沒有元素。Hash 真正的挑戰(zhàn)是找到好的哈希函數(shù)，讓哈希桶里包含非常少的元素。

如果有了好的哈希函數(shù)，在哈希表里搜索的時間復雜度是 O(1)。

但是 MySql 中除了 Memory 引擎外其他引擎都不支持Hash索引，主要是因為：

• 不能進行范圍查詢
• 不支持聯(lián)合索引的最左側原則
• 不支持 ORDER BY 排序
• 也無法進行模糊查詢

Hash 索引比較適合進行等值查詢。

二叉樹

二叉查找樹是帶有特殊屬性的二叉樹，每個節(jié)點的關鍵字必須：1)比保存在左子樹的任何鍵值都要大。2)比保存在右子樹的任何鍵值都要小。

二叉樹索引

這個樹有 N = 15 個元素。比方說要找 208：

• 從鍵值為 136 的根開始，因為 136 < 208，我去找節(jié)點 136 的右子樹。
• 398 > 208，所以去找節(jié)點 398 的左子樹
• 250 > 208，所以去找節(jié)點 250 的左子樹
• 200 < 208，所以去找節(jié)點 200 的右子樹。但是 200 沒有右子樹，值不存在（因為如果存在，它會在 200 的右子樹）

現(xiàn)在比方說要找 40

• 從鍵值為 136 的根開始，因為 136 > 40，所以去找節(jié)點 136 的左子樹。
• 80 > 40，所以去找節(jié)點 80 的左子樹
• 40 = 40，節(jié)點存在。抽取出節(jié)點內部行的 ID（圖中沒有畫）再去表中查找對應的數(shù)據(jù)。

兩次查詢的成本就是樹內部的層數(shù)。也就是時間復雜度為 O(log(n))。

B+Tree

查找一個特定值二叉樹挺好用，但是進行范圍查詢時候就有比較大的問題。成本將是 O(N)，因為必須查找樹的每一個節(jié)點，以判斷它是否處于 2 個值之間（例如，對樹使用中序遍歷）。為了解決這個問題，現(xiàn)代數(shù)據(jù)庫使用了一種修訂版的樹，叫做 B+ 樹。在一個 B+ 樹里：1)只有最底層的節(jié)點（葉子節(jié)點）才保存信息（相關表的行位置）2)其它節(jié)點只是在搜索中用來指引到正確節(jié)點的。

這個圖只是為了跟上面的圖進行對應，實際的 B+Tree 并不是這種二叉樹結構，可以看下文的圖。

模擬B+樹索引

可以看到，節(jié)點多了一倍。它們是幫助你找到正確節(jié)點的『決策節(jié)點』（正確節(jié)點保存著相關表中行的位置）。但是搜索復雜度還是在 O(log(N))（只多了一層）。一個重要的不同點是，最底層的節(jié)點是跟后續(xù)節(jié)點相連接的。

用這個 B+樹，假設你要找 40 到 100 間的值：

• 你只需要找 40（若 40 不存在則找 40 之后最貼近的值），就像你在上一個樹中所做的那樣。
• 然后用那些連接來收集 40 的后續(xù)節(jié)點，直到找到 100。

現(xiàn)代數(shù)據(jù)庫中大多數(shù)的索引都是采用 B+Tree 這種數(shù)據(jù)結構來構建索引。

索引類型

非聚集索引

MyISAM 引擎使用 B+Tree 作為索引結構，葉節(jié)點的 data 域存放的是數(shù)據(jù)記錄的地址。下圖是 MyISAM 索引的原理圖：

主鍵索引	輔助索引

這兩個圖是一個 MyISAM 表的主索引（Primary key）及輔助索引（Secondary key）的示意?？梢钥闯鯩yISAM 的索引文件僅僅保存數(shù)據(jù)記錄的地址。在 MyISAM 中，主索引和輔助索引在結構上沒有任何區(qū)別，只是主索引要求key是唯一的，而輔助索引的 key 可以重復。

MyISAM 中索引檢索過程是首先按照 B+Tree 搜索算法搜索索引，如果指定的 Key 存在，則取出其 data 域的值，然后使用 data 域的值為地址讀取相應數(shù)據(jù)記錄。

MyISAM 的索引方式也叫做“非聚集索引”，之所以這么稱呼是為了與 InnoDB 的聚集索引區(qū)分。

聚集索引

主鍵索引	輔助索引

雖然 InnoDB 也使用 B+Tree 作為索引結構，但具體實現(xiàn)方式卻與 MyISAM 截然不同。

第一個重大區(qū)別是 InnoDB 的數(shù)據(jù)文件本身就是索引文件，表數(shù)據(jù)文件本身就是按 B+Tree 組織的一個索引結構，這棵樹的葉節(jié)點 data 域保存了完整的數(shù)據(jù)記錄。這個索引的 key 是數(shù)據(jù)表的主鍵，因此 InnoDB 表數(shù)據(jù)文件本身就是主索引。這種索引叫做聚集索引。

因為 InnoDB 的數(shù)據(jù)文件本身要按主鍵聚集，所以 InnoDB 要求表必須有主鍵（MyISAM可以沒有），如果沒有顯式指定，則 MySQL 系統(tǒng)會自動選擇一個可以唯一標識數(shù)據(jù)記錄的列作為主鍵，如果不存在這種列，則 MySQL自動為 InnoDB 表生成一個隱含字段作為主鍵，這個字段長度為 6 個字節(jié)，類型為長整形。

第二個與 MyISAM 索引的不同是 InnoDB 的輔助索引data域存儲相應記錄主鍵的值而不是地址。所以使用輔助索引搜索需要檢索兩遍索引：首先檢索輔助索引獲得主鍵，然后用主鍵到主索引中檢索獲取記錄。

聯(lián)合索引

從上面我們看到的都是單列索引的結構，那么聯(lián)合索引是如何存儲建立索引的呢？其實聯(lián)合索引只不過比單值索引多了幾列，而這些索引列全都出現(xiàn)在索引樹上。存儲引擎會首先根據(jù)第一個索引列排序，如果第一列相等則再根據(jù)第二列排序，依次類推。

多列輔助索引

如圖，表有字段 id，a，b，c，其中 id 是主鍵，并創(chuàng)建了一個聯(lián)合索引包含列 a，b，c，那么生成如上圖所示的的 B+ 樹索引結構。

查找過程

還是以上表為例，我們執(zhí)行語句： select * from T1 where a = 12 and b = 14 and c = 3。存儲引擎首先從根節(jié)點（一般常駐內存）開始查找，第一個索引的第一個索引列為 1，12 大于 1 小于第二個索引列 56，于是從這倆索引的中間讀到下一個節(jié)點的磁盤文件地址，從磁盤上 Load 這個節(jié)點，通常伴隨一次磁盤 IO，然后在內存里去查找。當 Load 葉子節(jié)點的第二個節(jié)點時又是一次磁盤 IO，比較第一個元素 a = 12，再比較 b 列 c 列查詢到符合條件的索引，于是找到該索引下的 data 元素即表的主鍵值，再從主鍵索引樹上找到最終數(shù)據(jù)。

最左前綴匹配原則

之所以會有最左前綴匹配原則和聯(lián)合索引的索引構建方式及存儲結構是有關系的。我們創(chuàng)建的idx_t1_bcd(b,c,d) 索引，相當于創(chuàng)建了 (b)、(b,c)、(b,c,d) 三個索引。

聯(lián)合索引是首先使用多列索引的第一列構建的索引樹，用上面 idx_t1_bcd(b,c,d) 的例子就是優(yōu)先使用 b 列構建（相當于創(chuàng)建了索引(b)），當b列值相等時再以 c 列排序（相當于創(chuàng)建了索引(b,c)），若 c 列的值也相等則以 d 列排序。這種數(shù)據(jù)存儲結構決定了聯(lián)合索引只能從第一列開始依次進行查找，否則根據(jù)無法定位數(shù)據(jù)。

使用聯(lián)合索引支持指定前序字段查詢，按照后續(xù)字段排序。但是要注意查詢不能是范圍查詢如 >、<、in，否則只能取出數(shù)據(jù)內存排序了。

索引樹高度計算

從上面的知識我們知道了索引的構建方式，而決定查詢快慢的主要條件就是查詢的次數(shù)，其實也就是索引樹的高度。索引樹的高度決定了查詢的效率，如果一棵索引樹過高勢必會影響查詢速度，那么數(shù)據(jù)庫的索引樹高度究竟是多少呢？

假設：表的記錄數(shù)是n，每一個 B+Tree 節(jié)點平均有 m 個索引 KEY。

那么 B+Tree 索引樹的高度就是 （等價于 logN/logM）。n 是可變得，那么我們只要知道 m 就可以計算出來樹的高度了。

現(xiàn)代數(shù)據(jù)庫經過不斷的探索和優(yōu)化，并結合磁盤的預讀特點，每個索引節(jié)點一般都是操作系統(tǒng)頁的整數(shù)倍，操作系統(tǒng)頁一般是 4k。而 InnoDB 的 pageSize 可以通過命令得到，默認值是 16k，用下面這個 SQL 就是可以查到 show global status like 'Innodb_page_size' 。

每個節(jié)點的大小是 16k，那么只要知道每個索引的組成數(shù)據(jù)就可以知道一個節(jié)點下可以存儲多少個索引了，假設我們索引列為 bigint 類型（8bit），非葉子節(jié)點每兩個元素之間存的是下一個節(jié)點的地址，Mysql 分配的是 6bit?？梢运阋幌?16K 的非葉子節(jié)點可以存多少個索引，16K/(8b+6b)≈1170 個索引。葉子節(jié)點由于存儲的有可能是數(shù)據(jù)、指針、主鍵，需要根據(jù)實際情況計算。

假設葉子節(jié)點為 1K 的數(shù)據(jù)，我們算下 3 層的樹可以索引的數(shù)據(jù)量大約為：1170+11701170+11701170*(16K/1K) ≈ 2千萬。

Mysql中索引的高度一般是 3-4。

How does a relational database work
如果有人問你數(shù)據(jù)庫的原理，叫他看這篇文章
MySQL索引背后的數(shù)據(jù)結構及算法原理
MySQL索引那些事
掌握MySQL的B＋Tree索引暨如何計算索引樹高度'
聯(lián)合索引在B+樹上的存儲結構及數(shù)據(jù)查找方式