不會MySQL索引，面試官讓回家等通知！

你是不是對于 MySQL 索引的知識點一直都像大雜燴，好像什么都知道，如果進行深究的話可能一個也答不上來。

假如你去面試，面試官讓你聊一下對索引的理解，然而你對索引的理解僅限于，檢索數據就是快，是一種數據結構這個層面，那你就只能回家等通知了。

為了避免這種尷尬的事情發(fā)生，咔咔用時兩天將索引的內容在自己理解的范圍內進行了整理，如有整理不全面的地方可以在評論區(qū)進行補充和提建議。

MySQL 索引到底是什么
相信大多數伙伴都買過技術類的書籍，看完沒看完不知道，但是目錄肯定看的次數最多。
看目錄有沒有自己目前的痛點，如果有就會根據目錄對應的頁碼用最快的速度翻閱到相應內容位置。
那么在 MySQL 中同樣也是這樣的一個道理，MySQL 的索引就是存儲引擎為了快速找到數據的一種數據結構。
同樣在 MySQL 索引中又分了幾種類型，分別為：

• B-tree 索引
  

• 哈希索引
  

• 空間索引
  

• 全文索引

下文所有內容均在 InnoDB 的基礎上討論。

為什么要使用索引

①索引可以加快數據檢索速度，這也是使用的索引的最主要原因。

②索引本身具有順序性，在進行范圍查詢時，獲取的數據已經排好了序，從而避免服務器再次排序和建立臨時表的問題。

③索引的底層實現本身具有順序性，通過磁盤預讀使得在磁盤上對數據的訪問大致呈順序的尋址，也就是將隨機的 I/O 變?yōu)轫樞?I/O。

這幾點不理解就暫時先放著，繼續(xù)看下文即可，會給你一個滿意的解釋。

任何事物都存在雙面性，既然能提供性能的提升，自然在其他方面也會付出額外的代價：

• 索引是跟數據共存，因此會占用額外的存儲空間。
  

• 索引創(chuàng)建和維護需要時間成本，這個成本隨著數據量的增大而增大。

• 索引創(chuàng)建會降低數據的增、刪、改的性能，因為在修改數據的同時還需要修改索引數據。

InnoDB 為什么使用 B+Tree 而不使用 BTree
聊到這個問題那就必須得分清楚 BTree、B+tree 的區(qū)別，首先來看一下 BTree。

Btree 解析
先來看一下 BTree 的數據結構是怎么樣的，這里咔咔給提供一個網站地址，可以看到關于數據結構的一些實現過程：

https://www.cs.usfca.edu/~galles/visualization/Algorithms.html 

 先來看 BTree 的數據結構，下圖是咔咔已經將數據填充進去的： 

這里有一個陌生區(qū)關于 Max. Degree，這個你可以理解為階，也可以理解為度。 

例如現在這個值設置的是 4，那么在一個節(jié)點中最多就可以存儲 3 條數據，設置為 5那就可以最多放 4 條記錄。 

現在可以看到目前只插入了 3 條數據：

那么再加一條數據，節(jié)點就會進行分裂，這個也就驗證了當階設置為 n 時，一個節(jié)點可存 n-1 條數據。

那接著再來插入幾條數據看看：

想要達到快速檢索數據，那就需要滿足倆個特性，一個是有序，另一個就是平衡。
從下圖中可以看到 BTree 是有一定的順序性的，平衡性更滿足，可以看上文中生成的第一張圖。

那么在 BTree 中找一個值是怎么找呢？例如現在要找一個值 9，看一下尋找過程。

首先看到的數據是 4，9 是大于 4 的，所以會往 4 的右節(jié)點尋找。繼續(xù)找到范圍在 6 到 8 的節(jié)點，9 又大于 8，所以還需要往右節(jié)點尋找。
最有一步就找到了數據 9，這個過程就是 BTree 數據結構查找數據的執(zhí)行過程。

了解到了 BTree 的數據結構后，我們在來看看在 MySQL 中關于 BTree 是如何存儲的。
在下圖中 P 代表的是指針，指向的是下一個磁盤塊。在第一個節(jié)點中的 16、24 就是代表我們的 key 值是什么。date 就是這個 key 值對應的這一行記錄是什么。

那么此時想要尋找 key 為 33 的這條記錄應該怎么找。33 在 16 和 34 中間，所以會去磁盤 3 進行尋找。

在磁盤 3 中進行判斷，指針指向磁盤 8。在磁盤 8 中即可獲取到數據 33，然后將 data 返回。

那么在這個過程中到底讀取了多少條數據呢？在計算之前需要先了解一些知識點。

從 MySQL 5.7 開始，存儲引擎默認為 innodb，并且 innodb 存儲引擎用于管理數據的最小磁盤單位就是頁。

這個頁的類型也分為好幾種，分別為數據頁，Undo 頁，系統(tǒng)頁，事物數據頁。

一般說到的頁都是數據頁。默認的頁面大小為16kb，每個頁中至少存儲2條或以上的行記錄。

那么根據 BTree 數據查找的過程中可以得知一共讀取了三個磁盤，那么每個磁盤的大小就是 16kb。

而目前的給的案例尋找了三層，那么三層存儲的數據就是：16kb*16kb*16kb=4096kb。

如果按照一條記錄所需內存 1kb，那么這三層的 BTree 就可以存儲 4096 條記錄。

各位數據庫的數據少則幾百萬，多則幾千萬數據，那么 BTree 的層級就會越來越深，相對的查詢效率也會越來越慢。

這個時候是不是應該思考一個問題，那就是為什么在 Btree 中 48kb 的內存怎么就只能存儲 4000 多條記錄？

問題就出現在 data 上，要知道在計算數據大小時指針地址和 key 的內存都是沒有計算在內的，單單就計算了 data 的內存。

因為在 BTree 結構中，節(jié)點中不僅存儲的有 key、指針地址還有對應的數據，所以就會造成單個磁盤存儲的數據相對很少的原因。

為了解決單個節(jié)點存儲數據量小的問題，于是就演變出另一種結構，也就是下文提到了 B+Tree。

B+Tree 解析
依然如初看一下 B+Tree 的數據結構。為了方便對比，將 BTree 和 B+Tree 的數據結構放到了一起。

那么可以看到在 B+Tree 中葉子節(jié)點是存放了全量的數據，而非葉子節(jié)點只存儲了 key 值。

咦！這不是就很好的解決了 BTree 帶來的問題嗎？可以讓每個節(jié)點存儲更多的數據。每個節(jié)點存儲的數據越多，那么相對的就是樹的深度就不會過深。
了解到了 B+Tree 的數據結構后，我們在來看看在 MySQL 中關于 B+Tree 是如何存儲的。

從上圖很明顯就可以看到兩點不同：

• 第一點：B+Tree 所有的數據都存儲在葉子節(jié)點上。

• 第二點：B+Tree 所有的葉子節(jié)點之間是一種鏈式環(huán)結構。

那么在這個過程中到底讀取了多少條數據呢？

如果說 B+Tree 讀取數據的深度跟 B-Tree 的深度一樣，都是三層，那么同樣的道理每個磁盤的大小為 16kb。

那在 B+Tree 中非葉子節(jié)點可以存儲多少數據呢！一般來說我們每個表都會存在一個主鍵。

根據三層來計算，第一層跟第二層存儲的是 key 值，也就是主鍵值。

都知道 int 類型所占的內存時 4Byte（字節(jié)），指針的存儲就給個 6Byte，一共就是 10Tybe，那么第一層節(jié)點就可以存儲 16*1000/10=1600。

同理第二層每個節(jié)點也是可以存儲 1600 個 key。

第三層是葉子節(jié)點，每個磁盤存儲大小同樣安裝 BTree 的計算一樣，每條數據占 1kb。

那么在 B+Tree 中三層可以存儲的數據就是 1600*1600*16=40960000。

從這點來看 B+Tree 存儲的數據跟 BTree 存儲的數據根本就不是一個級別。

所以可以得出結論：

• B+Tree 能保證檢索的數據量相對 BTree 是最多的，而且存儲的數據量也是最多的。

• B+Tree 選擇索引時盡量選擇所占內存空間小的類型，比如 int 類型。

• key 所占內存越小，在節(jié)點中存儲的范圍就越多。

Hash 索引

alter table user add index hash_gender using hash(gender); 存儲引擎使用的是 innodb： 

會發(fā)現 name 的索引類型還是為 Btree，在 innodb 上創(chuàng)建哈希索引，被稱之為偽哈希索引，和真正的哈希索引不是一回事的，這點一定要明白。

在 Innodb 存儲引擎中有一個特殊的功能叫做，自適應哈希索引，當索引值被使用的非常頻繁時，它會在內存中基于 BTree 索引之上再創(chuàng)建一個哈希索引，那么就擁有了哈希索引的一些特點，比如快速查找。
哈希索引就是基于哈希表實現的，假設對 name 建立了哈希索引，則查找過程如下圖所示，哈希表是根據鍵值對進行訪問的數據結構，它讓檢索的數據經過哈希函數映射到散列表的對應位置，查找效率非常高。

哈希索引存儲的是哈希值和行指針，沒有存儲 key 值、字段值，但哈希索引多數是在內存完成的，檢索數據是非?？斓?，所以對性能影響不大：

• 哈希索引不是按照索引值排序的，所以也就無法排序。

• 哈希索引只支持等值操作，不支持范圍查找，在 MySQL 中只能只用 =、in 、<>。
  

• 哈希索引在任何時候都不能避免表掃描。
  

• 哈希索引在遇到大量哈希沖突時，存儲引擎必須遍歷鏈表的所有行指針，逐行比較。

B+Tree 跟 BTree 區(qū)別

經過了特別漫長的計算、畫圖現在基本對倆者的區(qū)別有一定認識了吧！

咔咔在這里進行總結一下：

• B+Tree 葉子節(jié)點上存儲的是全量數據（key+data），而非葉子節(jié)點只存儲 key。

• B+Tree 在同樣的深度下存儲的數據是遠遠大于 BTree 的。

• B+Tree 每個葉子節(jié)點都有指向下一個葉子節(jié)點的鏈接。這樣的好處在于，我們可以從任意一個葉子節(jié)點開始遍歷，獲取接下來所有的數據。

B+Tree 適合做索引的原因

B+Tree 樹非葉子節(jié)點只存儲 key 值，因此相對于 BTree 節(jié)點可以存儲更多的數據，每次讀入內存的 key 值就更多，相對來說 I/O 就降低。

B+Tree 樹查詢效率穩(wěn)定，任何數據的查找都是必須從葉子節(jié)點到非葉子節(jié)點，所以說每個數據查找的效率幾乎都是相同的。

B+Tree 樹的葉子節(jié)點存儲的是全量數據，并且是有序的，所以說只需要遍歷葉子節(jié)點就可以對所有的 key 進行掃描，在范圍查找時效率更高。

以上就是關于 InnoDB 存儲引擎為什么使用 B+Tree 作為索引的解析。

聚簇索引、非聚簇索引區(qū)別

聚簇索引、非聚簇索引也被稱之為主索引、二級索引。那么如何區(qū)分聚簇索引和非聚簇索引呢？
首先看一下 InnoDB 引擎下，創(chuàng)建表生成的文件，可以看到有兩個 ibd 文件。

看到這里不知道大家有沒有疑問：為什么看有的文章中也會有 frm 文件呢？但是在這里怎么沒有呢？

原因是在 MySQL 8.0 之后將源數據都存儲到了表空間中，所以也就不存在 frm 文件嘍！
都知道這個 idb 文件會存儲數據信息和索引信息。那再來看一下 Myisam 存儲引擎創(chuàng)建表生產的文件。

從圖中可以看到創(chuàng)建一個表會生成三個文件，擴展名分別為 MYD、MYI、sdi：

• MYD：是表數據文件（保存數據的文件）

• MYI：是表索引文件（保存索引的文件）

那么就可以得出一個結論：只要數據跟索引存儲在一個文件里，那就是聚簇索引，否則就是非聚簇索引。

這個時候就會有人問了，表中有主鍵的時候，idb 文件中存儲的是主鍵+數據，那么當沒有設置主鍵時怎么辦呢？

記住這一句話，在 InnoDB 中，數據插入時必須跟一個索引值進行綁定，如果沒有主鍵那就選擇唯一索引，如果沒有唯一索引就會選擇一個 6Byte 的 rowid。

表中存在多個索引數據是如何存儲的

看了上文的解釋，有沒有產生過一絲疑問，在 InnoDB 存儲引擎下，如果存在多個索引，是不是會產生多個 idb 文件。

在 InnoDB 中數據只會保存一份，如果有多個索引，會維護多個 B+Tree，例如：表字段 id，name，age，sex。

id 設置為主鍵索引（聚簇索引），name 設置為普通索引，那么數據到底會存儲幾份呢？

不管一個表中設置多少個索引，數據只會存儲一份，但是這張表會維護多個 B+Tree。

按照這個案例中 id 為主鍵索引，name 為普通索引，那么在這張表中就會維護倆顆 B+Tree。

id 主鍵索引跟數據存儲在一起，name 索引所在的 B+Tree 中葉子節(jié)點存儲的是主鍵 id 的值。
對應的圖就是以下兩幅圖，可以好好的看一下：

最后給大家總結一個點：在 InnoDB 中，一定有聚簇索引，其它索引都是非聚簇索引。

這里簡單提一下：Myisam 中只有非聚簇索引。

索引的幾個技術名詞

在面試中往往會問這幾個關鍵詞，分別為回表、覆蓋索引、最左側原則、索引下推，一定要知道哈！

回表

網上對回表的解釋各種各樣，咔咔給你說種簡單易懂的，但前提是你需要把聚簇索引、非聚簇索引區(qū)分清楚。

還是用上邊的案例，id 為主鍵索引，name 為普通索引。此時查詢語句為：

select id,name,age from table where name = 'kaka' 

那么這條語句會先在 name 的這顆 B+Tree 中尋找到主鍵 id，然后在根據主鍵 id 的索引獲取到數據并且返回。
其實這個過程就是從非聚簇索引跳轉到聚簇索引中查找數據，被稱為回表，也就是說當你查詢的字段為非聚簇索引，但是非聚簇索引中沒有將需要查詢的字段全部包含就是回表。

覆蓋索引

覆蓋索引，根據名字都能理解的差不多，就是查詢的所有字段都創(chuàng)建了索引！

select id,name from table where name = 'kaka' 

那么這條語句就是使用了覆蓋索引，因為 id 和 name 都為索引字段，查詢的字段也是這倆個字段，所以被稱為索引覆蓋。
也就是說當非覆蓋索引的葉子節(jié)點中包含了需要查詢的字段時就被稱為覆蓋索引。

最左匹配

最左匹配原則是在組合索引中存在的。還是用之前表信息：表字段 id，name，age，sex。此時給 name，age 設置成組合索引。
以下語句中那個不符合最左側原則：

select * from table where name = ? and age = ? select * from table where name = ? select * from table where age = ? select * from table where age= ? and name= ?

可以自行做一下測驗哈！是只有第三條語句不會用到索引，其他的三條語句都會符合最左側原則。
關于這個最左側原則遠遠不止這么簡單的，一試就是一個坑，關于這部分內容咔咔后期會在優(yōu)化文章中提到。

索引下推

還是使用這條 sql 語句：

select * from table where name = ? and age = ?

索引下推是在 MySQL 5.6 及以后的版本出現的。之前的查詢過程是，先根據 name 在存儲引擎中獲取數據，然后在根據 age 在 server 層進行過濾。

在有了索引下推之后，查詢過程是根據 name、age 在存儲引擎獲取數據，返回對應的數據，不再到 server 層進行過濾。
當你使用 Explain 分析 SQL 語句時，如果出現了 Using index condition 那就是使用了索引下推，索引下推是在組合索引的情況出現幾率最大的。

索引存儲在什么地方
索引的數據文件是存儲在磁盤中的，也是需要進行持久化操作。但是當使用索引時會把數據從磁盤讀取到內存中，讀取方式為分塊讀取。

這時就要涉及到操作系統(tǒng)的概念，操作系統(tǒng)在磁盤中獲取數據，假設現在要取的數據大小是 1kb，但操作系統(tǒng)并不會只取出你需要的這 1kb，而是會取出 4kb 的數據。
為什么會是 4kb，因為在操作系統(tǒng)中一頁的數據就是 4kb。那又為什么只需要 1kb 而取出整頁的數據呢？

那就又會涉及到另一個概念那就是局部性原理：數據和程序都有聚集成群的傾向，在訪問了一條數據之后，在之后有極大的可能再次訪問這條數據和這條數據的相鄰數據。
所以說 MySQL 的 InnoDB 存儲引擎，在讀取數據時也會采取這種局部性原理，每次讀取的數據是 16kb。

如果索引數據只存儲在內存中，那么當電腦關機，服務器宕機之后，就需要重新生成索引，這種的效率是十分低的。

總結

以上就是咔咔對索引的理解，在盡最大的可能將知識點說全面。如果還有遺漏，或者文章中有錯誤的地方還請各位能給出提議。