摘要：索引的各種規(guī)則紛繁復(fù)雜，不了解索引的組織形式就沒(méi)辦法真正地理解數(shù)據(jù)庫(kù)索引。順暢地閱讀這篇文章需要了解索引聯(lián)合索引聚集索引分別都是什么，如果你還不了解，可以通過(guò)另一篇文章來(lái)輕松理解數(shù)據(jù)庫(kù)索引是什么新華字典來(lái)幫你。

索引的各種規(guī)則紛繁復(fù)雜，不了解索引的組織形式就沒(méi)辦法真正地理解數(shù)據(jù)庫(kù)索引。通過(guò)本文，你可以深入地理解數(shù)據(jù)庫(kù)索引在數(shù)據(jù)庫(kù)中究竟是如何組織的，從此以后索引的規(guī)則對(duì)于你將變得清清楚楚、明明白白，再也不需要死記硬背。

順暢地閱讀這篇文章需要了解索引、聯(lián)合索引、聚集索引分別都是什么，如果你還不了解，可以通過(guò)另一篇文章來(lái)輕松理解——數(shù)據(jù)庫(kù)索引是什么？新華字典來(lái)幫你。

這篇文章是一系列數(shù)據(jù)庫(kù)索引文章中的第二篇，這個(gè)系列包括了下面四篇文章：

數(shù)據(jù)庫(kù)索引是什么？新華字典來(lái)幫你 —— 理解

數(shù)據(jù)庫(kù)索引融會(huì)貫通 —— 深入

20分鐘數(shù)據(jù)庫(kù)索引設(shè)計(jì)實(shí)戰(zhàn) —— 實(shí)戰(zhàn)

數(shù)據(jù)庫(kù)索引為什么用B+樹(shù)實(shí)現(xiàn)？ —— 擴(kuò)展

這一系列涵蓋了數(shù)據(jù)庫(kù)索引從理論到實(shí)踐的一系列知識(shí)，一站式解決了從理解到融會(huì)貫通的全過(guò)程，相信每一篇文章都可以給你帶來(lái)更深入的體驗(yàn)。

通過(guò)之前的內(nèi)容，我們已經(jīng)對(duì)數(shù)據(jù)庫(kù)索引有了相當(dāng)程度的抽象了解，那么在數(shù)據(jù)庫(kù)中，索引實(shí)際是以什么樣的形式進(jìn)行組織的呢？同一張表上的多個(gè)索引又是怎樣分工合作的呢？

目前絕大多數(shù)情況下使用的數(shù)據(jù)庫(kù)索引都是使用B+樹(shù)實(shí)現(xiàn)的，下面就以MySQL的InnoDB為例，介紹一下數(shù)據(jù)庫(kù)索引的具體實(shí)現(xiàn)。

下面是一個(gè)以B+樹(shù)形式組織的拼音索引，在B+樹(shù)中，每一個(gè)節(jié)點(diǎn)里都有N個(gè)按順序排列的值，且每個(gè)值的中間和節(jié)點(diǎn)的頭尾都有指向下一級(jí)節(jié)點(diǎn)的指針。在查找過(guò)程中，按順序從頭到尾遍歷一個(gè)節(jié)點(diǎn)中的值，當(dāng)發(fā)現(xiàn)要找的目標(biāo)值恰好在一個(gè)指針的前一個(gè)值之前、后一個(gè)值之后時(shí)，就通過(guò)這個(gè)指針進(jìn)入下一級(jí)節(jié)點(diǎn)。當(dāng)最后到達(dá)葉子節(jié)點(diǎn)，也就是最下層的節(jié)點(diǎn)時(shí)，就能夠找到自己希望查找的數(shù)據(jù)記錄了。

在上圖中如果希望找到險(xiǎn)字，那么我們首先通過(guò)拼音首字母在根節(jié)點(diǎn)上按順序查找到了X和Y之間的指針，然后通過(guò)這個(gè)指針進(jìn)入了第二級(jí)節(jié)點(diǎn)···, xia, xian, xiang, ···。之后在該節(jié)點(diǎn)上找到了xian和xiang之間的指針，這樣就定位到了第519頁(yè)開(kāi)始的一個(gè)目標(biāo)數(shù)據(jù)塊，其中就包含了我們想要找到的險(xiǎn)字。

因?yàn)槠匆羲饕蔷奂饕晕覀冊(cè)谌~子節(jié)點(diǎn)上直接就找到了我們想找的數(shù)據(jù)。

下面是一個(gè)模擬部首索引的組織形式。我們由根節(jié)點(diǎn)逐級(jí)往下查詢(xún)，但是在最后的葉子節(jié)點(diǎn)上并沒(méi)有找到我們想找的數(shù)據(jù)，那么在使用這個(gè)索引時(shí)我們是如何得到最終的結(jié)果的呢？回憶之前字典中“檢字表”的內(nèi)容，我們可以看到，在每個(gè)字邊上都有一個(gè)頁(yè)碼，這就相當(dāng)于下面這一個(gè)索引中葉子節(jié)點(diǎn)上險(xiǎn)字與院字中間的指針，這個(gè)指針會(huì)告訴我們真正的數(shù)據(jù)在什么地方。

下圖中，我們把非聚集索引（部首索引）和聚集索引（拼音索引）合在一起就能看出非聚集索引最后到底如何查找到實(shí)際數(shù)據(jù)了。非聚集索引葉子節(jié)點(diǎn)上的指針會(huì)直接指向聚集索引的葉子節(jié)點(diǎn)，因?yàn)楦鶕?jù)聚集索引的定義，所有數(shù)據(jù)都是按聚集索引組織存儲(chǔ)的，所以所有實(shí)際數(shù)據(jù)都保存在聚集索引的葉子節(jié)點(diǎn)中。而從非聚集索引的葉子節(jié)點(diǎn)鏈接到聚集索引的葉子節(jié)點(diǎn)查詢(xún)實(shí)際數(shù)據(jù)的過(guò)程就叫做——回表。

那么如果我們只是想要驗(yàn)證險(xiǎn)字的偏旁是否是雙耳旁“阝”呢？這種情況下，我們只要在部首索引中阝下游的葉子節(jié)點(diǎn)中找到了險(xiǎn)字就足夠了。這種在索引中就獲取到了SQL語(yǔ)句中需要的所有字段，所以不需要再回表查詢(xún)的情況中，這個(gè)索引就被稱(chēng)為這個(gè)SQL語(yǔ)句的全覆蓋索引。

在實(shí)際的數(shù)據(jù)庫(kù)中，非聚集索引的葉子節(jié)點(diǎn)上保存的“指針”就是聚集索引中所有字段的值，要獲取一條實(shí)際數(shù)據(jù)，就需要通過(guò)這幾個(gè)聚集索引字段的值重新在聚集索引上執(zhí)行一遍查詢(xún)操作。如果數(shù)據(jù)量不多，這個(gè)開(kāi)銷(xiāo)是非常小的；但如果非聚集索引的查詢(xún)結(jié)果中包含了大量數(shù)據(jù)，那么就會(huì)導(dǎo)致回表的開(kāi)銷(xiāo)非常大，甚至超過(guò)不走索引的成本。所以全覆蓋索引可以節(jié)約回表的開(kāi)銷(xiāo)這一點(diǎn)在一些回表開(kāi)銷(xiāo)很大的情況下就非常重要了。

上圖是一個(gè)聯(lián)合索引idx_eg(col_a, col_b)的結(jié)構(gòu)，如果我們希望查詢(xún)一條滿(mǎn)足條件col_a = 64 and col_b = 128的記錄，那么我們可以一路確定地往下找到唯一的下級(jí)節(jié)點(diǎn)最終找到實(shí)際數(shù)據(jù)。這種情況下，索引上的col_a和col_b兩個(gè)字段都能被使用。

但是如果我們將查詢(xún)條件改為范圍查詢(xún)col_a > 63 and col_b = 128，那么我們就會(huì)需要查找所有符合條件col_a > 63的下級(jí)節(jié)點(diǎn)指針，最后不得不遍歷非常多的節(jié)點(diǎn)及其子節(jié)點(diǎn)。這樣的話(huà)對(duì)于索引來(lái)說(shuō)就得不償失了，所以在這種情況下，數(shù)據(jù)庫(kù)會(huì)選擇直接遍歷所有滿(mǎn)足條件col_a > 63的記錄，而不再使用索引上剩下的col_b字段。數(shù)據(jù)庫(kù)會(huì)從第一條滿(mǎn)足col_a > 63的記錄開(kāi)始，橫向遍歷之后的所有記錄，從里面排除掉所有不滿(mǎn)足col_b = 128的記錄。

這就是范圍條件會(huì)終止使用聯(lián)合索引上的后續(xù)字段的原因。