[[400403]]

本文轉載自微信公眾號「石杉的架構筆記」，作者夢。轉載本文請聯(lián)系石杉的架構筆記公眾號。

概要

本次會先從一個數(shù)據(jù)頁中如何存儲和查詢數(shù)據(jù)開始，拓展到多個數(shù)據(jù)頁中查詢數(shù)據(jù)，分析無索引查詢時的低效率問題，然后通過頁分裂過渡到主鍵目錄以及索引頁相關內(nèi)容，見證一顆索引樹是如何一步步生長起來的。

最后站在更高的角度看下常見的一些索引名詞、索引的優(yōu)缺點以及如何才能設計出更好的索引來，開始分析前我們先來思考下如下的一些面試題：

1.InnoDB的索引數(shù)據(jù)結構是什么?為什么用這種數(shù)據(jù)結構?

2.聚簇索引和普通索引的區(qū)別是什么?

3.什么是回表操作?它對索引有什么影響嗎?

Mysql索引的B+樹的生長流程如下圖所示：

2.B+索引樹是如何生長的

2.1 無索引時的數(shù)據(jù)查詢

數(shù)據(jù)頁是Mysql中數(shù)據(jù)管理的最小單元，既然我們要研究索引是如何高效查詢數(shù)據(jù)的，首先我們肯定要搞清楚數(shù)據(jù)是如何存放的，數(shù)據(jù)頁的結構通過上篇文章我們了解到大概是這樣的：

而數(shù)據(jù)表中的每行數(shù)據(jù)就存放在數(shù)據(jù)區(qū)中，數(shù)據(jù)區(qū)中每行數(shù)據(jù)以單向鏈表的方式，通過指針連接起來，如下圖所示：

同時每個數(shù)據(jù)頁之間再通過雙向鏈表的方式組織連接起來，如下圖所示：

(1)無索引時的數(shù)據(jù)查詢

通過以上對數(shù)據(jù)頁以及數(shù)據(jù)頁內(nèi)部數(shù)據(jù)結構初步的分析，現(xiàn)在我們就可以看下，如果說要查詢某張表的某行數(shù)據(jù)會經(jīng)過什么樣的流程。

數(shù)據(jù)頁一開始當然是存放在磁盤中的，一張表對一般會應著多個數(shù)據(jù)頁，查詢數(shù)據(jù)時從磁盤中依次加載數(shù)據(jù)頁到InnoDB的緩沖池中，然后對緩沖池中緩存頁的每行數(shù)據(jù)，通過數(shù)據(jù)頁的單向鏈表一個一個去遍歷查找，如果沒有找到，那么就會順著數(shù)據(jù)頁的雙向鏈表數(shù)據(jù)結構，依次遍歷加載磁盤中的其他數(shù)據(jù)頁到緩沖池中遍歷查詢。

大家可以看到，像上面這樣的查詢方式就有點傻了，因為如果恰好你要查的數(shù)據(jù)行在這張表最后一個數(shù)據(jù)頁的最后一行，那豈不是所有的數(shù)據(jù)頁都要被掃描一遍，然后每個數(shù)據(jù)頁中也是遍歷鏈表，整體的效果就是以O(n)的時間復雜度在遍歷鏈表了,這樣查詢的性能肯定是不行的。

(2)優(yōu)化數(shù)據(jù)頁內(nèi)查詢效率-槽位

我們先把目光轉移到單個數(shù)據(jù)頁內(nèi)的數(shù)據(jù)查詢，假如說我們現(xiàn)在已經(jīng)鎖定數(shù)據(jù)就在某個數(shù)據(jù)頁中了，但是我們該怎樣快速的從這個數(shù)據(jù)頁中找到我們想要的那行數(shù)據(jù)呢?

通過之前的分析我們可以知道，最傻的一種方式就是遍歷數(shù)據(jù)頁中的單向鏈表查詢，一個節(jié)點一個節(jié)點去掃描，相對應的查詢效率是肉眼可見的低。但是如果說可以像翻書一樣，根據(jù)目錄來減小我們查詢的范圍，相對應的查詢效率不就上來了嗎，根據(jù)這種想法，InnoDB存儲引擎設計了槽位這種方式來組織數(shù)據(jù)頁中的多個數(shù)據(jù)行，槽位信息存放在數(shù)據(jù)頁中的數(shù)據(jù)頁目錄中。

槽位簡單來說就是將數(shù)據(jù)頁中的多個數(shù)據(jù)行分組劃分，每個數(shù)據(jù)行組都找這個組中的主鍵值最大的那個數(shù)據(jù)行的地址作為槽位的信息，這樣數(shù)據(jù)頁目錄中的一個個槽位不就是像是一個個目錄了嗎，標記好了多個數(shù)據(jù)行分組的位置信息，如下圖所示：

這下有了數(shù)據(jù)頁目錄中的槽位信息，此時要查詢數(shù)據(jù)頁中的某行數(shù)據(jù)不就很簡答了，比如我們要查詢主鍵為4的那行數(shù)據(jù)，直接通過二分法以O(logn)的時間復雜度鎖定數(shù)據(jù)頁目錄中的槽位2，因為槽位之間都是緊密連接的，可以通過槽位2找到槽位1，從槽位1末尾開始，對分組2中的數(shù)據(jù)開始遍歷，因為每個分組中的數(shù)據(jù)量都很少，此時在這么小的范圍內(nèi)簡單遍歷下就可以快速找到主鍵為4的那行數(shù)據(jù)，時間復雜度從之前的O(n)降低到O(logn)效率還是挺可觀的。

但是如果你不是通過主鍵去查詢的，槽位此時就排不上用場，你還得一個一個遍歷數(shù)據(jù)頁中的單向鏈表去找到你想要的那行數(shù)據(jù)。

2.2 索引的前夕-頁分裂

這里我們先來個小插曲，簡單了解下頁分裂，這塊內(nèi)容也是后面索引機制能夠正常運行的基礎。

我們都知道一個數(shù)據(jù)頁就是16KB大小，當一個數(shù)據(jù)頁中的數(shù)據(jù)行足夠多時就會重新創(chuàng)建一個數(shù)據(jù)頁繼續(xù)寫數(shù)據(jù)行，如果說我們沒有用到索引還好，但是如果我們要在表中創(chuàng)建索引，那么對多個數(shù)據(jù)頁中的數(shù)據(jù)就有約束了。

如果新創(chuàng)建的數(shù)據(jù)頁中的數(shù)據(jù)行的主鍵值，存在比它上一個數(shù)據(jù)頁的主鍵值還小的情況，這種情況是不被允許的，如下圖所示：

如果出現(xiàn)上圖的情況，多個數(shù)據(jù)頁之間的主鍵就無序了，而索引機制的實現(xiàn)是要基于多個數(shù)據(jù)頁主鍵的大小是依次遞增的，所以此時就會出現(xiàn)頁分裂的情況。

其實頁分裂目的也很明確，就是調整下不同數(shù)據(jù)頁的數(shù)據(jù)順序，使得最終按順序創(chuàng)建的索引頁之間，后一個數(shù)據(jù)頁中的每一個數(shù)據(jù)行的主鍵值都要大于上一個數(shù)據(jù)頁，當然一個數(shù)據(jù)頁中當然是按照單向鏈表的方式依次遞增的，頁分裂流程如下圖所示：

我們可以看到頁分裂主要就是調整了下數(shù)據(jù)頁之間數(shù)據(jù)行的數(shù)據(jù)的順序，使得多個數(shù)據(jù)頁之間的主鍵值是按照順序來存放的，在這樣有序的數(shù)據(jù)中，高效查詢才變得可能。

頻繁的出現(xiàn)頁分裂情況，畢竟頁分裂要涉及到數(shù)據(jù)的移動，在性能上也是會有損耗的，這也警示我們減少頁分裂的出現(xiàn)概率是非常有必要的，在設計表結構時我們可以盡量使用主鍵自增長的方式，而不是用很難保證主鍵順序的自定義創(chuàng)建主鍵的方式，使用主鍵自增長方式，能大大避免說數(shù)據(jù)頁之間主鍵大小出現(xiàn)順序錯亂的問題，減少頁分裂發(fā)生的概率。

2.3從主鍵目錄到索引頁

查詢一行數(shù)據(jù)，在物理層面就是定位到哪一個數(shù)據(jù)頁中的哪一行數(shù)據(jù)。在數(shù)據(jù)頁中定位數(shù)據(jù)的問題，在之前我們已經(jīng)通過槽位的方式優(yōu)化了查詢的效率，現(xiàn)在我們要解決的是如何在大量的數(shù)據(jù)頁中定位數(shù)據(jù)頁，這就是索引的目標。

(1)主鍵目錄

InnoDB存儲引擎一開始是使用主鍵目錄的方式，將數(shù)據(jù)頁號和數(shù)據(jù)頁最小的主鍵值作為一條記錄，如下圖所示：

這樣的話，我們要查哪一條數(shù)據(jù)就不用掃描一個數(shù)據(jù)頁內(nèi)的所有數(shù)據(jù)再掃描下一個了，直接通過id去主鍵目錄看一下，通過二分查找定位到具體哪個數(shù)據(jù)頁，然后數(shù)據(jù)頁內(nèi)部通過定位槽位，遍歷那個槽位對應數(shù)據(jù)行分組找到具體的一行數(shù)據(jù)。

(2)索引頁

現(xiàn)在有一個問題就是，每張表對應的數(shù)據(jù)頁都有很多，主鍵目錄就會有大量的數(shù)據(jù)、就有可能放不下，這時InnoDB設計者們就想存放目錄數(shù)據(jù)也是數(shù)據(jù)啊，為什么不可以使用數(shù)據(jù)頁來放呢，就這樣主鍵目錄的信息就被移到數(shù)據(jù)頁來了，而這些數(shù)據(jù)頁就被稱為索引頁，如下圖所示：

從這里我們可以知道數(shù)據(jù)頁肯定不是簡單只存放數(shù)據(jù)表中的數(shù)據(jù)的。好了，現(xiàn)在主鍵目錄由于容量有限，我們把主鍵目錄信息移動到了數(shù)據(jù)頁中形成了索引頁，但同樣的問題不還是會出現(xiàn)嗎，一個數(shù)據(jù)頁的大小也才16KB，索引頁本身的容量也是有限的，容量不夠了該怎么辦呢?

為了解決索引頁容量不夠的問題，索引頁會重新創(chuàng)建和升級，先把超出容量的數(shù)據(jù)放到一個新的索引頁中，然后再加一層索引頁，如下圖所示：

由上圖我們可以看到，新的一層索引頁35它存放的就不是最小主鍵對應的數(shù)據(jù)頁目錄了，而是最小主鍵對應的索引頁目錄了，以此類推如果索引頁35這里容量也不夠呢，那就繼續(xù)往上一層擴展啊，最終效果看起來就像下面一樣：

大家看出來了嗎，由索引頁一層一層組成的結構不就是我們經(jīng)常說的索引樹嗎，而這棵樹在mysql中稱之為B+索引樹。

樹這種數(shù)據(jù)結構天然可以使用二分法查詢，所以現(xiàn)在如果我們要查詢一條數(shù)據(jù)，從樹的根節(jié)點開始通過二分法查找，以O(logn)的時間復雜度鎖定數(shù)據(jù)頁，然后在數(shù)據(jù)頁中同樣使用二分法鎖定槽位，在槽位中簡單遍歷下不就找到數(shù)據(jù)了嗎，相比于沒有索引的場景，速度那可是相當快了。

3.聚簇索引、普通索引和覆蓋索引

關于索引有一些常見的名詞我們需要加以區(qū)分。

首先聚簇索引就是像我們上面看到的一棵樹一樣，它的葉子節(jié)點是一個個數(shù)據(jù)頁，這些數(shù)據(jù)頁中存放的都是數(shù)據(jù)表中每一行的完整數(shù)據(jù)，所以說如果B+樹是以完整數(shù)據(jù)的數(shù)據(jù)頁為葉子節(jié)點的，我們把這個索引樹稱為聚簇索引;如果一個索引的索引樹，葉子節(jié)點不是以數(shù)據(jù)頁為葉子節(jié)點的，就稱為二級索引或普通索引。

聚簇索引和普通索引最大的區(qū)別就是，聚簇索引的葉子節(jié)點存放了數(shù)據(jù)行的完整數(shù)據(jù)，而二級索引葉子節(jié)點只有數(shù)據(jù)的部分字段。

而覆蓋索引本身并不是一種索引，而是一種查詢數(shù)據(jù)的方式，比如我們對表table中的字段name建立了索引，然后我們執(zhí)行查詢?nèi)纾簊elect name from table where name like '張%'，此時直接從name字段對應的B+樹種查詢到對應的一批name值，然后直接就返回就行了，也就是說我們想要的字段name它本來就在索引上，我們直接通過二分法高效的從樹上直接摘下來就行了，而這種查詢方式就稱為覆蓋索引。

當然相比于覆蓋索引方式，如果查詢改為：select * from table where name like '張%'，這就不是覆蓋索引了，因為此時你不光要從索引樹上找到具體的name，還要利用id值回表查詢所有的字段。

4.索引的優(yōu)缺點分析

索引的優(yōu)點當然就是高效查詢數(shù)據(jù)，索引將遍歷鏈表的O(n)的查詢時間復雜度優(yōu)化為了O(logn)的時間復雜度。

但是索引的缺點也是很明顯的，首先在時間角度上，它必須要求主鍵是要按順序增長的，無序的主鍵會帶來頻繁的頁分裂，影響效率;對數(shù)據(jù)庫表的增刪改操作的同時也需要維護索引，這部分的維護也是一塊性能損耗點;在空間角度上：索引相關的數(shù)據(jù)和實際數(shù)據(jù)一樣都是要占內(nèi)存空間的。

所以索引雖然能夠提高查詢效率，但是同時也要承擔它給我們的系統(tǒng)帶來的性能損耗，從這點上來看索引并不是建的越多越好。

5.三個維度設計好索引

下面我們從以下三個維度優(yōu)化下索引的設計

(1)首先我們從時間角度上

我們需要為了避免頻繁的頁分裂，需要盡可能使用主鍵自增長等方式，保證新增的數(shù)據(jù)頁中的數(shù)據(jù)行的主鍵都是遞增，避免不必要的頁分裂帶來的性能損耗和拖慢查詢效率。

另外選擇合適的字段作為索引字段也很重要，需要選擇基數(shù)較大的字段，也就是一個字段可能出現(xiàn)的值比較多，這樣我們在B+樹中查詢時，才能最高效的發(fā)揮出二分法查詢的威力，如果建立索引的字段基數(shù)比較小可能查詢時二分查找就會退化成時間復雜度為O(n)的線性查詢了。

(2)空間的角度上

因為索引數(shù)據(jù)本身也是要占空間的，可以選擇字段長度較小的作為索引字段，這樣整棵B+樹不至于那么占空間。

但是如果非得要以長字段作為索引也不是不行，可以采用折中的以字段的前綴作為索引，這樣的索引也稱為前綴索引，但是這樣可能只能用在模糊查詢上了，用在group by和order by上就不太適合了。

(3)作用范圍上

當然我們設計索引的目的，當然是為了更好的用上索引，索引在設計時，盡可能讓where、group by、order by這些語句都能用上索引。

6.面試題剖析

（1）InnoDB的索引數(shù)據(jù)結構是什么?為什么用這種數(shù)據(jù)結構?

（2）聚簇索引、普通索引區(qū)別是什么?

（3）什么是回表操作?它對索引有什么影響嗎?