大家好，我是啊粥枝誊。

接下來的幾天我們會開啟一個全新的系列文章况芒，那就是搞定面試官系列，我會把常見的面試知識通過這個專欄寫出來叶撒，比如我們常見的 Java绝骚、MySQL、Redis祠够、MQ 以及其他的一些技術(shù)框架压汪。

現(xiàn)在最先開啟的是 MySQL 系列，今天先來分享我們最常見的一個面試問題古瓤，那就是關(guān)于 MySQL 的索引止剖。

相信很多人在面試中會遇到關(guān)于 MySQL 索引的相關(guān)知識腺阳，從 MySQL 的架構(gòu)到索引模型，然后再到表設(shè)計(jì)穿香，SQL 優(yōu)化等等亭引。

首先，我們來看下索引是什么皮获？

索引概述

索引是一種幫助 MySQL 高效獲取數(shù)據(jù)的有序數(shù)據(jù)結(jié)構(gòu)焙蚓。

它的出現(xiàn)就是為了提高數(shù)據(jù)的查詢效率，就像書的目錄一樣洒宝。如果一本書沒有目錄购公，那我們就必須一頁一頁的去找我們自己想要的東西。

但是一旦有了目錄待德，那我們就可以快速的通過目錄了解書的全貌君丁，然后再根據(jù)具體的頁碼找到我們自己想要的東西。

MySQL 的索引就是類似的作用将宪，幫助我們快速且高效的獲取數(shù)據(jù)绘闷。

索引的常見模型

索引的實(shí)現(xiàn)有不同的方式，本質(zhì)上可以提高查詢效率的數(shù)據(jù)結(jié)構(gòu)有很多種较坛，這里先介紹三種比較常見的數(shù)據(jù)結(jié)構(gòu)：

• 哈希表

• 有序數(shù)組

• 樹形結(jié)構(gòu)

哈希表

以鍵值（key-value）形式存儲數(shù)據(jù)的結(jié)構(gòu)印蔗。哈希的方式非常簡單，是用一個哈希函數(shù)把 key 換算成一個確定的位置丑勤，然后把 value 放在數(shù)組的這個位置华嘹。

因?yàn)楣Ｋ惴ǖ脑颍鄠€ key 可能會存在 Hash 沖突法竞，這個時候一般會使用拉鏈法來解決沖突耙厚，也就是相同 Hash 值的拉出一個鏈表。

哈希表這種結(jié)果用來做等值查詢速度非巢戆裕快薛躬，但是因?yàn)樗菬o序的，如果是用來做區(qū)間查詢的話呆细，會非常慢型宝。

比如，我們有一張用戶的姓名和身份照號的表絮爷，如下是使用哈希表的方式存儲：

image.png

有序數(shù)組

以上數(shù)據(jù)如果使用有序數(shù)組來存儲的話趴酣，他的結(jié)構(gòu)是：

[圖片上傳失敗...(image-aaf42e-1660361093143)]

有序數(shù)組可以使用二分法很快進(jìn)行數(shù)據(jù)檢索，時間復(fù)雜度是 O(log(N))坑夯。但是更新數(shù)據(jù)會比較麻煩岖寞，因?yàn)橐S持順序，所以每次數(shù)據(jù)插入需要移動的元素太多了渊涝，成本太高慎璧。

所以床嫌，有序數(shù)組只適用于靜態(tài)存儲引擎。

搜索樹

同理胸私，使用二叉樹來存儲的話厌处，結(jié)構(gòu)如下

image.png

二叉搜索樹的特點(diǎn)是：父節(jié)點(diǎn)左子樹所有結(jié)點(diǎn)的值小于父節(jié)點(diǎn)的值，右子樹所有結(jié)點(diǎn)的值大于父節(jié)點(diǎn)的值岁疼。這樣如果你要查 id_card_03 的話阔涉，按照圖中的搜索順序就是按照 USERA -> USERC -> USERF -> USER_03 這個路徑得到。

這個時間復(fù)雜度是 O(log(N))捷绒。

當(dāng)然為了維持 O(log(N)) 的查詢復(fù)雜度瑰排，就需要保持這棵樹是平衡二叉樹。為了做這個保證暖侨，更新的時間復(fù)雜度也是 O(log(N))椭住。

二叉樹是搜索效率最高的，但是實(shí)際上大多數(shù)的數(shù)據(jù)庫存儲卻并不使用二叉樹字逗。其原因是京郑，索引不止存在內(nèi)存中，還要寫到磁盤上葫掉。

N 叉樹由于在讀寫上的性能優(yōu)點(diǎn)些举，以及適配磁盤的訪問模式，已經(jīng)被廣泛應(yīng)用在數(shù)據(jù)庫引擎中了俭厚。

但是户魏，二叉樹也是分很多種的，比如有 B-Tree挪挤、B+Tree 以及紅黑樹等等叼丑。

一般來說，一棵 100 萬節(jié)點(diǎn)的平衡二叉樹扛门，樹高 20幢码。一次查詢可能需要訪問 20 個數(shù)據(jù)塊。在機(jī)械硬盤時代尖飞，從磁盤隨機(jī)讀一個數(shù)據(jù)塊需要 10 ms 左右的尋址時間。也就是說店雅，對于一個 100 萬行的表政基，如果使用二叉樹來存儲，單獨(dú)訪問一個行可能需要 20 個 10 ms 的時間闹啦，這個查詢可真夠慢的沮明。

所以，我們需要找到另一種更加適合用來做 MySQL 索引引擎的數(shù)據(jù)結(jié)構(gòu)窍奋。

Innodb 的索引模型

InnoDB 使用了 B+ 樹作為索引結(jié)構(gòu)荐健，所有的元素都會出現(xiàn)在葉子節(jié)點(diǎn)上酱畅，同時，葉子節(jié)點(diǎn)之間會通過雙向鏈表連接江场。

InnoDB 使用 B+ Tree 使用索引結(jié)構(gòu)主要有以下原因：

• 相比于二叉樹纺酸，B+ 數(shù)層級更少，搜索效率更高址否。

  • 以 InnoDB 的一個整數(shù)字段索引為例餐蔬，這個 N 差不多是 1200。這棵樹高是 4 的時候佑附，就可以存 1200 的 3 次方個值樊诺，這已經(jīng) 17 億了∫敉考慮到樹根的數(shù)據(jù)塊總是在內(nèi)存中的词爬，一個 10 億行的表上一個整數(shù)字段的索引，查找一個值最多只需要訪問 3 次磁盤权均。其實(shí)顿膨，樹的第二層也有很大概率在內(nèi)存中，那么訪問磁盤的平均次數(shù)就更少了螺句。

• B 樹的葉子節(jié)點(diǎn)以及非葉子節(jié)點(diǎn)虽惭，都會保存數(shù)據(jù)，這樣會導(dǎo)致一頁中存儲的鍵值減少蛇尚，指針跟著減少芽唇，要保存同樣多的數(shù)據(jù)，只能增加樹的高度取劫，導(dǎo)致搜索性能降低匆笤。

在 InnoDB 中，表都是根據(jù)主鍵順序以索引的形式存放的谱邪，這種存儲方式的表稱為索引組織表炮捧。

每一個索引在 InnoDB 里面對應(yīng)一棵 B+ 樹。

假設(shè)表中 T1 ~ T5 的 (id,age) 值分別為 (1,10)惦银、(2,20)咆课、(3,30)、(5,50) 和 (6,60)扯俱，兩棵索引樹的示例示意圖如下书蚪。

主鍵索引樹

image.png

二級索引樹

image.png

從圖中不難看出，兩個索引輸?shù)娜~子結(jié)點(diǎn)內(nèi)容是不一樣的迅栅。根據(jù)葉子節(jié)點(diǎn)的內(nèi)容殊校，可以把索引類型分為主鍵索引和非主鍵索引。

主鍵索引的葉子節(jié)點(diǎn)存的是整行數(shù)據(jù)读存。而非主鍵索引的葉子結(jié)點(diǎn)存儲的是主鍵的值为流。

在 InnoDB 里呕屎，主鍵索引也被稱為聚簇索引（clustered index），非主鍵索引也被稱為二級索引（secondary index）敬察。

基于主鍵索引和普通索引的查詢有什么區(qū)別秀睛？

如果語句是 select * from test where id = 5，即主鍵查詢方式静汤，則只需要搜索 id 這棵 B+ 樹琅催；

如果語句是 select * from test where age = 50，即普通索引查詢方式虫给，則需要先搜索 age 索引樹藤抡，得到 id 的值為 5，再到 id 索引樹搜索一次抹估。

這個過程稱為回表缠黍，也就是說，基于非主鍵索引的查詢需要多掃描一棵索引樹药蜻。

因此瓷式，我們在應(yīng)用中應(yīng)該盡量使用主鍵查詢。

索引維護(hù)的開銷

B+ 樹為了維護(hù)索引有序性语泽，在插入新值的時候需要做必要的維護(hù)贸典。

以上面這個圖為例，如果插入新的行 id 值為 7踱卵，則只需要在 T5 的記錄后面插入一個新記錄廊驼。

如果新插入的 ID 值為 4，就相對麻煩了惋砂，需要在邏輯上挪動后面的數(shù)據(jù)妒挎，空出位置給 4，B+ 樹要做結(jié)構(gòu)變化西饵，維持平衡和節(jié)點(diǎn)順序酝掩。

而更糟的情況是，如果 T5 所在的數(shù)據(jù)頁已經(jīng)滿了眷柔，根據(jù) B+ 樹的算法期虾，這時候需要申請一個新的數(shù)據(jù)頁，然后挪動部分?jǐn)?shù)據(jù)過去驯嘱，這個過程稱為頁分裂彻消。

在這種情況下，性能自然會受影響宙拉。

除了影響性能外，頁分裂操作還會影響數(shù)據(jù)頁的利用率丙笋，因?yàn)樵痉旁谝粋€頁的數(shù)據(jù)谢澈，現(xiàn)在分到兩個頁中煌贴，整體空間利用率會降低大約 50%。

同理锥忿，有分裂就有合并牛郑。

當(dāng)相鄰兩個頁由于刪除了數(shù)據(jù)，利用率很低之后敬鬓，會將數(shù)據(jù)頁做合并淹朋，合并的過程，可以認(rèn)為是分裂過程的逆過程钉答。將利用率低的頁數(shù)據(jù)進(jìn)行合并之后础芍，另一個數(shù)據(jù)葉會被標(biāo)記為可復(fù)用供后續(xù)數(shù)據(jù)利用，

所以我們?yōu)槭裁唇ㄗh使用自增主鍵数尿，因?yàn)?strong>自增主鍵的插入數(shù)據(jù)模式仑性，正好符合了我們前面提到的遞增插入的場景。

每次插入一條新記錄右蹦，都是追加操作诊杆，所以不涉及到挪動其他記錄，也不會觸發(fā)葉子節(jié)點(diǎn)的分裂何陆。反之晨汹，如果是使用業(yè)務(wù)邏輯的字段做主鍵，則往往沒法保證有序插入贷盲，這樣寫數(shù)據(jù)成本會相對較高淘这。

好了，我們做個簡單的總結(jié)：

MySQL 選取了 B+ 樹作為它的索引模型來存儲數(shù)據(jù)晃洒，不但可以合理的利用磁盤特性慨灭，而且可以很方便的做范圍查詢，同時球及，因?yàn)?B+ 樹在非葉子節(jié)點(diǎn)不存儲數(shù)據(jù)氧骤，只在葉子節(jié)點(diǎn)存儲數(shù)據(jù)，同等高度的 B+ 樹和 B 樹吃引，B + 樹可以存更多的數(shù)據(jù)筹陵，反之，同等的數(shù)據(jù)量镊尺，B+ 樹高度更低朦佩，假設(shè)每次節(jié)點(diǎn)搜索都是一次磁盤 IO 的話，那么庐氮，B+ 樹可以花更少的時間來獲取到所需要的數(shù)據(jù)语稠。

MySQL 的索引模型我們今天就先介紹到這里，文末留給大家一個問題，你有沒有遇到過仙畦，你明明執(zhí)行 delete 命令把表里的數(shù)據(jù)都刪除了输涕，但是表文件的大小卻沒有發(fā)生變化的情況？

如果有的話慨畸，歡迎留言我們一起討論莱坎，答案在下一篇文章中揭曉。

我是程序員啊粥寸士，關(guān)注我檐什，我們一起在技術(shù)海洋中向上生長。