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

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

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

1. 數(shù)據(jù)庫索引是什么鸡捐？新華字典來幫你 —— 理解

2. 數(shù)據(jù)庫索引融會貫通 —— 深入

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

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

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

索引的組織形式

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

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

聚集索引

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

image.png

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

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

非聚集索引

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

image.png

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

image.png

全覆蓋索引

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

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

范圍查詢條件

image.png

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

image.png

但是如果我們將查詢條件改為范圍查詢col_a > 63 and col_b = 128，那么我們就會需要查找所有符合條件col_a > 63的下級節(jié)點(diǎn)指針盘寡，最后不得不遍歷非常多的節(jié)點(diǎn)及其子節(jié)點(diǎn)楚殿。這樣的話對于索引來說就得不償失了，所以在這種情況下竿痰，數(shù)據(jù)庫會選擇直接遍歷所有滿足條件col_a > 63的記錄脆粥，而不再使用索引上剩下的col_b字段砌溺。數(shù)據(jù)庫會從第一條滿足col_a > 63的記錄開始，橫向遍歷之后的所有記錄变隔，從里面排除掉所有不滿足col_b = 128的記錄规伐。

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