索引是什么?為什么要有mysql 索引，解決了什么問題，其底層的原理是什么?為什么使用B+樹做為解決方案?用其他的像哈希索引或者B樹不行嗎?

簡單了解索引

首先，索引(Index)是什么?如果我直接告訴你索引是數(shù)據(jù)庫管理系統(tǒng)中的一個(gè)有序的數(shù)據(jù)結(jié)構(gòu)，你可能會有點(diǎn)懵逼。

為了避免這種情況，我打算舉幾個(gè)例子來幫助你更容易的認(rèn)識索引。

• 我們查詢字典的時(shí)候可以根據(jù)字的部首、筆畫來查找到對應(yīng)的字，這樣可以快速的找到對應(yīng)的字所在頁，在字典開頭那玩意就叫索引
• 還有一本書的目錄，可以幫我們快速的跳到不同的章節(jié)，此時(shí)這里的目錄也是索引
• 甚至，景區(qū)的地圖，會告訴你你現(xiàn)在在哪里，其他景點(diǎn)在哪兒，這個(gè)地圖從某些方面來說也是索引

再結(jié)合開篇較專業(yè)的解釋，你可能就能夠理解索引是什么了。

[[399779]]

為什么需要索引

了解了索引的概念，我們就需要知道為什么我們需要索引?從剛剛的例子可以看出來，索引的存在的目的就是：

[[399780]]

• 字典中的索引幫助我們快速的找到對應(yīng)的字
• 書的目錄幫助我們快速的跳到我們需要看的章節(jié)
• 景區(qū)的地圖幫助我們快速的找到想要去的景區(qū)的路

在數(shù)據(jù)庫中，索引可以幫助我們快速的查詢到對應(yīng)的數(shù)據(jù)行，從而順利的取出所有列的數(shù)據(jù)。這個(gè)過程必須要快，對于現(xiàn)在的 Web 應(yīng)用來說，DB 如果響應(yīng)慢，將會直接影響到整個(gè)請求的響應(yīng)時(shí)間，而這對用戶體驗(yàn)來說是災(zāi)難性的。

對于點(diǎn)個(gè)按鈕，等個(gè)好幾秒才有返回，那么之后用戶大概率是不會再使用你開發(fā)的應(yīng)用了。

MySQL中的索引

首先，MySQL 和索引其實(shí)沒有直接的關(guān)系。索引其實(shí)是 MySQL 中使用的存儲引擎 InnoDB 中的概念。在 InnoDB 中，索引分為：

• 聚簇索引
• 非聚簇索引

對于聚簇索引，是 InnoDB 根據(jù)主鍵(Primary Key)構(gòu)建的索引。你可以暫時(shí)理解為 key 為主鍵，value 則是整行數(shù)據(jù)。并且一張表只能有一個(gè)聚簇索引。

[[399781]]

當(dāng)然，你可以不定義主鍵。但是正常情況下我們都會創(chuàng)建一個(gè)單調(diào)遞增的主鍵，或者是通過統(tǒng)一的 ID 生成算法生成。如果沒有定義任何主鍵，InnoDB 會有自己的兜底策略。InnoDB 會選擇我們定義的第一個(gè)所有值的都不為空的唯一索引作為聚簇索引。

[[399782]]

不過實(shí)際的生產(chǎn)環(huán)境中，的確會有這樣的 Corner Case。InnoDB 還有一個(gè)究極兜底，如果連僅剩的唯一索引也不符合要求，InnoDB 會自己創(chuàng)建一個(gè)隱藏的6個(gè)字節(jié)的主鍵 RowID，然后根據(jù)這個(gè)隱藏的主鍵來生成聚簇索引。

而對于非聚簇索引，是根據(jù)指定的列創(chuàng)建的索引，也叫二級索引(Secondary Index)，一張表最多可以創(chuàng)建64個(gè)二級索引。key 為創(chuàng)建二級索引的列的值，value 為主鍵。換句話說，如果通過非聚簇索引查詢，最終只能得到索引列本身的值 + 主鍵的值，如果想要獲取到完整的列數(shù)據(jù)，還需要根據(jù)得到的主鍵去聚簇索引中再查詢一次，這個(gè)過程叫回表。

• 這里說明一下，現(xiàn)在有很多的博客說，MySQL 使用 InnoDB 時(shí)，一張表最多只能創(chuàng)建 16 個(gè)索引，首先這是錯的，明顯是從其他的地方直接抄過來的，自己沒有去做任何的驗(yàn)證。
• 在 MySQL 的官方文章中，明確的說明了，一張表最多可以創(chuàng)建 64 個(gè)非聚簇索引，而且創(chuàng)建非聚簇索引時(shí)，列的數(shù)量不能超過16個(gè)。

注意，是創(chuàng)建非聚簇索引的列不能超過16個(gè)!

 [[399783]]

這也順便提一下題外話，所謂的技術(shù)嚴(yán)謹(jǐn)，什么叫嚴(yán)謹(jǐn)?對你通過其他渠道獲取到的知識，它最多叫作者的觀點(diǎn)，我們持一種懷疑態(tài)度，并想辦法自己去求證。求證后，它才會變成事實(shí)。

而不是對某些名詞死記硬背，現(xiàn)在的新玩意層出不窮，但當(dāng)你溯其根源，你會發(fā)現(xiàn)就那么回事。

索引底層原理

前面提到了 InnoDB 中索引的類型，簡單的了解了其分類和區(qū)別，那 InnoDB 中的索引是如何做到加速查詢的呢?其底層的原理是啥呢?InnoDB 中的索引的底層結(jié)構(gòu)為 B+ 樹，是B樹的一個(gè)變種。

先給大家看看B+樹到底長個(gè)什么鳥樣，下圖是一顆存儲了數(shù)字「1-7」的B+樹。

可以看到，B+樹中，每個(gè)節(jié)點(diǎn)可以有多個(gè)子節(jié)點(diǎn)，而像我們平常熟悉的二叉樹中，每個(gè)節(jié)點(diǎn)最多只能有2個(gè)。并且，B+樹中，節(jié)點(diǎn)的存儲數(shù)據(jù)是有序的，而有序的數(shù)據(jù)結(jié)構(gòu)就可以讓我們進(jìn)行快速的精確匹配和范圍查詢。而且B+樹中的葉子結(jié)點(diǎn)之間有指向下一個(gè)節(jié)點(diǎn)的指針，而B樹中的葉子節(jié)點(diǎn)是沒有的。

• 在 MySQL InnoDB 的實(shí)際實(shí)現(xiàn)中，頁節(jié)點(diǎn)之間其實(shí)是個(gè)雙鏈表，存儲了分別指向上一個(gè)、下一個(gè)節(jié)點(diǎn)的指針

下圖是包含了整數(shù)「1-7」的B樹，這個(gè)圖應(yīng)該會幫助你加深對兩者區(qū)別的理解。

并且，在B+樹中，除了葉子節(jié)點(diǎn)存儲了真實(shí)的數(shù)據(jù)之外，其余的節(jié)點(diǎn)都只存儲了指向下一節(jié)點(diǎn)的指針。換句話說，數(shù)據(jù)全部都在葉子節(jié)點(diǎn)上。而在B樹中，所有的節(jié)點(diǎn)都可以存儲數(shù)據(jù)，這是一個(gè)最主要的區(qū)別。

知道了B樹和B+樹的基礎(chǔ)結(jié)構(gòu)長啥樣之后，我們需要再深入了解 InnoDB 是如何利用B+樹來存儲數(shù)據(jù)的。首先，MySQL 并不會把數(shù)據(jù)存儲在內(nèi)存中，內(nèi)存只是作為運(yùn)行時(shí)的一種優(yōu)化，關(guān)于 InnoDB 內(nèi)存架構(gòu)相關(guān)的東西，之前已經(jīng)寫了一篇文章，感興趣的可以先去看看。

InnoDB 會將數(shù)據(jù)存儲在磁盤上，而當(dāng)我們查詢數(shù)據(jù)的時(shí)候，OS 會將存儲在磁盤上的數(shù)據(jù)一頁一頁的加載到內(nèi)存里。這里的頁是 OS 管理內(nèi)存的一種方式，當(dāng)其加載數(shù)據(jù)到內(nèi)存時(shí)，會將某個(gè)磁盤塊上的數(shù)據(jù)按照頁的大小加載。在這里，你可以理解為B樹中每個(gè)節(jié)點(diǎn)就是一個(gè)磁盤塊。

那既然B樹和B+樹在查找的時(shí)候都需要進(jìn)行 I/O 操作將需要的節(jié)點(diǎn)加載到內(nèi)存，B+樹相對于B樹的優(yōu)勢到底在哪兒?

[[399787]]

個(gè)人認(rèn)為主要有三點(diǎn)。

一是B+樹能夠減少 I/O 的次數(shù)。為啥呢?憑啥數(shù)據(jù)結(jié)構(gòu)長的差不多，B+樹就能夠減少 I/O 的次數(shù)?之前說到，單個(gè)節(jié)點(diǎn)就代表了一個(gè)磁盤塊，而單個(gè)磁盤塊的大小是固定的。B+樹僅有葉子結(jié)點(diǎn)才存儲值，相對于所有節(jié)點(diǎn)都存完整數(shù)據(jù)的B樹而言，B+樹中單個(gè)磁盤塊能夠容納更多的數(shù)據(jù)。

 [[399788]]

單個(gè)磁盤塊，容量固定的前提下，存儲的元素大小越小，則能夠存儲的元素的數(shù)量就會更多。換句話說，一次 I/O 能夠把更多的數(shù)據(jù)加載進(jìn)內(nèi)存，而這些多加載的元素很可能是你會用到的，而這就一定程度上能減少 I/O 的次數(shù)。

除此之外，單個(gè)節(jié)點(diǎn)能夠存儲的元素增多了，還能夠起到減少樹的高度的作用。

二是查詢效率更加穩(wěn)定。什么叫更穩(wěn)定呢?那就在數(shù)據(jù)量相同的情況下，不會因?yàn)槟悴樵兊臄?shù)據(jù) ID 不同而造成查詢所耗費(fèi)時(shí)間大相徑庭，換句話說，這次請求可能花了10ms，下一次同樣的請求啪的一下花了20ms，這就讓人很不能接受，合著接口的性能還要看你數(shù)據(jù)庫的心情?

那為什么說使用B+樹就能夠做到查詢效率穩(wěn)定呢?因?yàn)锽+樹非葉子結(jié)點(diǎn)不會存儲數(shù)據(jù)，所以如果要獲取到最終的數(shù)據(jù)，必然會查到葉子結(jié)點(diǎn)，換句話說，每次查詢的 I/O 次數(shù)是相同的。而B樹由于所有節(jié)點(diǎn)均可存儲數(shù)據(jù)，有的數(shù)據(jù)可能1次 I/O 就查詢到了，而有的則需要查詢到葉子結(jié)點(diǎn)才找到數(shù)據(jù)，而這就會帶來查詢效率的不穩(wěn)定。

三是能夠更好的支持范圍查詢。那B樹為啥就不能很好的支持呢?讓我們回到B樹這張圖。

假設(shè)我們需要查詢 [3, 5] 這個(gè)區(qū)間內(nèi)的數(shù)據(jù)，會經(jīng)歷什么呢?不廢話，直接把圖給出來。 

可以看到，如果到葉子結(jié)點(diǎn)仍然沒有查詢到完整的數(shù)據(jù)，會重新返回到根結(jié)點(diǎn)再次進(jìn)行遍歷。而反觀 B+ 樹，當(dāng)找到了葉子結(jié)點(diǎn)之后就可以通過葉子結(jié)點(diǎn)之間的指針直接進(jìn)行鏈表遍歷，可以大大的提升范圍查詢的效率。

• 知道了這點(diǎn)之后，舉一反三就能夠知道，為什么 InnoDB 不使用 Hash 在做底層的數(shù)據(jù)結(jié)構(gòu)了。即使查詢時(shí) Hash 的時(shí)間復(fù)雜度甚至能做到 O(1)

最后聊聊 I/O

全篇提到了很多次 I/O，以及在 MySQL 的索引設(shè)計(jì)中，需要盡量的減少 I/O 次數(shù)，為啥呢?是因?yàn)?I/O 很昂貴。當(dāng)我們執(zhí)行一次 I/O，到底發(fā)生了什么?

本來像詳細(xì)講講磁盤結(jié)構(gòu)的，但是看了一眼篇幅，已經(jīng)快超了，所以這里就簡單的聊聊就好

機(jī)械硬盤中，一次 I/O 操作，由三個(gè)步驟組成：

首先需要尋道，尋道是指磁盤的磁頭移動道磁盤上的磁道上面，這個(gè)時(shí)間一般在3-15ms內(nèi)。

然后是旋轉(zhuǎn)，磁盤會將存儲對應(yīng)數(shù)據(jù)的盤片旋轉(zhuǎn)至磁頭下方，這又花掉2ms左右，具體的時(shí)延與磁盤的轉(zhuǎn)速有關(guān)。

最后是數(shù)據(jù)傳輸。

一波操作下來，花費(fèi)就在10ms左右。不要以為10ms還好...對比于SSD(固態(tài)硬盤)和內(nèi)存的微秒、納秒來說，簡直有著天壤之別。

這也是為啥在 MySQL 中，隨機(jī) I/O 對其查詢的性能影響很大的原因。