— — 寫在前面

記得剛開(kāi)始工作那會(huì)，年輕無(wú)知 [dog]，有一段時(shí)間對(duì) MySQL 的索引極為迷惑，看公司的 wiki 有著一堆的使用規(guī)則，于是我就挑了其中的一個(gè)詢問(wèn)了一位 年長(zhǎng)的老濕傅，“為何聯(lián)合索引要最左則原則？” ，濕傅：“這常識(shí)問(wèn)題??？就我們?cè)谑褂玫臅r(shí)候應(yīng)該.......”。我 ....... 所以在回答別人問(wèn)題的時(shí)候最好還是要有點(diǎn)深度準(zhǔn)備好了再說(shuō)，否則 [dog][dog][dog] 此處省略一萬(wàn)字 .....
后來(lái)經(jīng)過(guò)業(yè)余時(shí)間的資料補(bǔ)充，可算是了解了一點(diǎn)皮毛，以此一來(lái)不管是在平時(shí)的使用、設(shè)計(jì)都有諸多的好處。最近又看到一些文章，于是決定我也來(lái)做碗湯，下文主要就圍繞 Innodb 來(lái)講解其頁(yè)結(jié)構(gòu)、B+ Tree 主鍵索引、及聯(lián)合索引和普通索引。最后的答案也就隨之浮現(xiàn)。為何會(huì)有這么多的使用原則？

一、索引的作用

索引，當(dāng)然是為了提高查詢或檢索的效率。就舉個(gè)通俗的栗子吧，我們?cè)谑褂脻h字字典拼音查詢時(shí)，比如要查詢 某個(gè)字時(shí)，是不是需要從其拼音的開(kāi)頭字母開(kāi)始查詢，慢慢縮小其查詢的范圍，最終找到匹配的拼音的索引頁(yè)，定位到所要查詢的字。而在數(shù)據(jù)庫(kù)中索引的作用也是如此。

二、聚簇索引和非聚簇索引

對(duì)于聚簇索引，其實(shí)就是葉子節(jié)點(diǎn)的順序和物理存儲(chǔ)的順序是一樣的，所以其 范圍查詢效率很高，任何事物都是有兩面性的，所以它的弊端就是在一些DML操作的時(shí)候，需要涉及到數(shù)據(jù)的位移。聚簇索引的順序就是數(shù)據(jù)的物理儲(chǔ)存順序，所以這樣一來(lái)，一個(gè)表就只能有一個(gè)聚簇索引。（ MySQL Innodb 中默認(rèn)為主鍵，當(dāng)然沒(méi)有定義主鍵， InnoDB 會(huì)隱式定義一個(gè)主鍵 ）
對(duì)于非聚簇索引本文就不做太多介紹，其葉級(jí)頁(yè)指向表中的記錄行（ 實(shí)際上就是內(nèi)節(jié)點(diǎn)會(huì)存儲(chǔ)指針，指向記錄的物理地址 ），所以其物理順序與邏輯順序是沒(méi)有聯(lián)系的。

三、MySQL InnoDB 數(shù)據(jù)頁(yè)結(jié)構(gòu)

額 .... 這塊其實(shí)內(nèi)容比較多，圍繞本文的核心，我就挑 Page Directory （ 頁(yè)目錄 ） 來(lái)說(shuō)下吧。
上面說(shuō)到查字典，總得有個(gè)目錄去找到對(duì)應(yīng)的數(shù)據(jù)吧 （ 有目錄當(dāng)然是為了更好的管理數(shù)據(jù) ）。在 InnoDB 中是分為數(shù)據(jù)頁(yè)和索引頁(yè)的。
所以 MySQL 為了方便管理這些記錄，就規(guī)定了用頁(yè)作為基本單位存放記錄，默認(rèn)的大小是 16 KB，所以一頁(yè)能存放多少數(shù)據(jù)是由這些記錄的大小決定的，比如一條記錄的大小為 10字節(jié)的話，那么 16 * 1024 / 10 = 1,638.4 ，所以大約一頁(yè)可以存放 1638 條記錄（ 理論值 ）。那么數(shù)據(jù)量一多肯定會(huì)存在多頁(yè)，那么頁(yè)與頁(yè)之間是怎么關(guān)聯(lián)的呢？見(jiàn)下文圖一。
Page和B+樹(shù)之間并沒(méi)有一一對(duì)應(yīng)的關(guān)系，Page 只是作為一個(gè) Record的 保存容器，它存在的目的是便于對(duì)磁盤空間進(jìn)行批量管理。

圖一 InnoDB 頁(yè)目錄剖析圖

四、B+ 樹(shù) （ B+ Tree ）

這里推薦大家一個(gè)網(wǎng)站，可以去模擬各種數(shù)據(jù)結(jié)構(gòu)的插入、刪除、轉(zhuǎn)換過(guò)程。https://www.cs.usfca.edu/~galles/visualization/Algorithms.html
所以我這邊在此 亂序 插入了一些數(shù)據(jù)（ 7,8,9,12,15,18,24,27 ），生成了 Degree 為 3 的 B+ 樹(shù)。

圖二 B+ Tree 索引數(shù)據(jù)結(jié)構(gòu)模擬

• 葉子結(jié)點(diǎn)包含了所有結(jié)點(diǎn)，除葉子結(jié)點(diǎn)之外，其它結(jié)點(diǎn)不包含值，而葉子結(jié)點(diǎn)包含具體的值
• 層級(jí)更低（ 相比B樹(shù)，此文不做 B 樹(shù)分析 ），葉子結(jié)點(diǎn)形成 鏈表（ 有序 ），范圍查詢（留個(gè)心眼）方便；
  由此，經(jīng)過(guò)一些官方資料查閱，畫(huà)了一張 InnoDB 引擎中的 B+ 樹(shù)索引的數(shù)據(jù)結(jié)構(gòu)圖：
  
  圖三 InnoDB 索引數(shù)據(jù)結(jié)構(gòu)
  
  原圖地址：https://www.processon.com/view/link/6077a5ae0791293688854242

五、聯(lián)合索引和普通索引

上文二中曾提到因?yàn)槠浔举|(zhì)結(jié)構(gòu)原因一個(gè)表就只能有一個(gè)聚簇索引，而 InnoDB 默認(rèn)的聚簇索引就是 主鍵，那么聯(lián)合索引和普通索引在查詢時(shí)是怎么使用的呢？
為此，根據(jù)個(gè)人的理解本人作圖以便于更直觀的理解。

圖四 聯(lián)合索引或普通索引檢索流程（ 回表 ）

六、為何 MySQL 會(huì)選擇 B+ 樹(shù)作為索引？

A、相對(duì)于 B 樹(shù)

讀取成本（ IO 次數(shù) ）：B+樹(shù)的非葉子結(jié)點(diǎn)沒(méi)有存儲(chǔ)數(shù)據(jù)，所以如果把所有同一內(nèi)部節(jié)點(diǎn)的關(guān)鍵字存放在同一盤塊中，那么盤塊所能容納的關(guān)鍵字?jǐn)?shù)量也越多。一次性讀內(nèi)存中的需要查找的關(guān)鍵字也就越多。
查詢效率：由于B+樹(shù)的分支結(jié)點(diǎn)并不是最終指向文件內(nèi)容的結(jié)點(diǎn)，只是葉子結(jié)點(diǎn)的索引，所以任意關(guān)鍵字的查找都必須從根節(jié)點(diǎn)走向分支結(jié)點(diǎn)，查詢路徑相同。但B樹(shù)的分支結(jié)點(diǎn)保存有數(shù)據(jù)，所以查詢路徑可能不同。

B、相對(duì)于 Hash 索引

Hash 應(yīng)該無(wú)需多言了，Hash 的優(yōu)勢(shì)是在于精確定位查詢，常見(jiàn)的有 HashMap ，但不適合做范圍查詢
Hash 索引每次查詢時(shí)都需要將所有的索引數(shù)據(jù)加載到內(nèi)存中，而 B+ 索引只需要選定某個(gè)范圍，再加載到內(nèi)存中，進(jìn)行檢索。

寫在最后

自下而上的分析，根據(jù)文章中一些標(biāo)紅的地方，不難發(fā)現(xiàn)也就是 MySQL 的一些優(yōu)勢(shì)和一些規(guī)則的來(lái)源也就浮現(xiàn)出來(lái)了。另外，了解這些東西只是為了更加清晰的對(duì) MySQL 索引有個(gè)稍微深層次的一個(gè)認(rèn)知，才能夠運(yùn)用得當(dāng)。