【51CTO.com原創稿件】你是不是對于 MySQL 索引的知識點一直都像大雜燴，好像什么都知道，如果進行深究的話可能一個也答不上來。

[[380981]] 

圖片來自 Pexels

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

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

MySQL 索引到底是什么

相信大多數伙伴都買過技術類的書籍，看完沒看完不知道，但是目錄肯定看的次數最多。

看目錄有沒有自己目前的痛點，如果有就會根據目錄對應的頁碼用最快的速度翻閱到相應內容位置。

那么在 MySQL 中同樣也是這樣的一個道理，MySQL 的索引就是存儲引擎為了快速找到數據的一種數據結構。

同樣在 MySQL 索引中又分了幾種類型，分別為：

• B-tree 索引
• 哈希索引
• 空間索引
• 全文索引

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

為什么要使用索引

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

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

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

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

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

• 索引是跟數據共存，因此會占用額外的存儲空間。
• 索引創建和維護需要時間成本，這個成本隨著數據量的增大而增大。
• 索引創建會降低數據的增、刪、改的性能，因為在修改數據的同時還需要修改索引數據。

InnoDB 為什么使用 B+Tree 而不使用 BTree

聊到這個問題那就必須得分清楚 BTree、B+tree 的區別，首先來看一下 BTree。

Btree 解析

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

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

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

 

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

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

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

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

 

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

 

想要達到快速檢索數據，那就需要滿足倆個特性，一個是有序，另一個就是平衡。

從下圖中可以看到 BTree 是有一定的順序性的，平衡性更滿足，可以看上文中生成的第一張圖。

 

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

首先看到的數據是 4，9 是大于 4 的，所以會往 4 的右節點尋找。繼續找到范圍在 6 到 8 的節點，9 又大于 8，所以還需要往右節點尋找。

最有一步就找到了數據 9，這個過程就是 BTree 數據結構查找數據的執行過程。

 

了解到了 BTree 的數據結構后，我們在來看看在 MySQL 中關于 BTree 是如何存儲的。

在下圖中 P 代表的是指針，指向的是下一個磁盤塊。在第一個節點中的 16、24 就是代表我們的 key 值是什么。date 就是這個 key 值對應的這一行記錄是什么。

 

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

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

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

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

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

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

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

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

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

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

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

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

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

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

B+Tree 解析

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

 

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

咦!這不是就很好的解決了 BTree 帶來的問題嗎?可以讓每個節點存儲更多的數據。每個節點存儲的數據越多，那么相對的就是樹的深度就不會過深。

了解到了 B+Tree 的數據結構后，我們在來看看在 MySQL 中關于 B+Tree 是如何存儲的。

 

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

• 第一點：B+Tree 所有的數據都存儲在葉子節點上。
• 第二點：B+Tree 所有的葉子節點之間是一種鏈式環結構。

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

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

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

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

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

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

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

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

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

所以可以得出結論：

• B+Tree 能保證檢索的數據量相對 BTree 是最多的，而且存儲的數據量也是最多的。
• B+Tree 選擇索引時盡量選擇所占內存空間小的類型，比如 int 類型。
• key 所占內存越小，在節點中存儲的范圍就越多。

Hash 索引

先來創建一個 hash 索引：

alter table user add index hash_gender using hash(gender); 

存儲引擎使用的是 innodb：

 

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

在 Innodb 存儲引擎中有一個特殊的功能叫做，自適應哈希索引，當索引值被使用的非常頻繁時，它會在內存中基于 BTree 索引之上再創建一個哈希索引，那么就擁有了哈希索引的一些特點，比如快速查找。

哈希索引就是基于哈希表實現的，假設對 name 建立了哈希索引，則查找過程如下圖所示，哈希表是根據鍵值對進行訪問的數據結構，它讓檢索的數據經過哈希函數映射到散列表的對應位置，查找效率非常高。

 

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

• 哈希索引不是按照索引值排序的，所以也就無法排序。
• 哈希索引只支持等值操作，不支持范圍查找，在 MySQL 中只能只用 =、in 、<>。
• 哈希索引在任何時候都不能避免表掃描。
• 哈希索引在遇到大量哈希沖突時，存儲引擎必須遍歷鏈表的所有行指針，逐行比較。

B+Tree 跟 BTree 區別

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

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

• B+Tree 葉子節點上存儲的是全量數據(key+data)，而非葉子節點只存儲 key。
• B+Tree 在同樣的深度下存儲的數據是遠遠大于 BTree 的。
• B+Tree 每個葉子節點都有指向下一個葉子節點的鏈接。這樣的好處在于，我們可以從任意一個葉子節點開始遍歷，獲取接下來所有的數據。

B+Tree 適合做索引的原因

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

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

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

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

聚簇索引、非聚簇索引區別

聚簇索引、非聚簇索引也被稱之為主索引、二級索引。那么如何區分聚簇索引和非聚簇索引呢?

首先看一下 InnoDB 引擎下，創建表生成的文件，可以看到有兩個 ibd 文件。

 

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

原因是在 MySQL 8.0 之后將源數據都存儲到了表空間中，所以也就不存在 frm 文件嘍!

都知道這個 idb 文件會存儲數據信息和索引信息。那再來看一下 Myisam 存儲引擎創建表生產的文件。

 

從圖中可以看到創建一個表會生成三個文件，擴展名分別為 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 中葉子節點存儲的是主鍵 id 的值。

對應的圖就是以下兩幅圖，可以好好的看一下： 

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

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

索引的幾個技術名詞

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

回表

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

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

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

那么這條語句會先在 name 的這顆 B+Tree 中尋找到主鍵 id，然后在根據主鍵 id 的索引獲取到數據并且返回。

其實這個過程就是從非聚簇索引跳轉到聚簇索引中查找數據，被稱為回表，也就是說當你查詢的字段為非聚簇索引，但是非聚簇索引中沒有將需要查詢的字段全部包含就是回表。

在這個案例中，非聚簇索引 name 的葉子節點只有 id，并沒有 age，所以會跳轉到聚簇索引中，根據 id 在查詢整條記錄返回需要的字段數據。

覆蓋索引

覆蓋索引，根據名字都能理解的差不多，就是查詢的所有字段都創建了索引!

此時查詢語句為：

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

那么這條語句就是使用了覆蓋索引，因為 id 和 name 都為索引字段，查詢的字段也是這倆個字段，所以被稱為索引覆蓋。

也就是說當非覆蓋索引的葉子節點中包含了需要查詢的字段時就被稱為覆蓋索引。

最左匹配

最左匹配原則是在組合索引中存在的。還是用之前表信息：表字段 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= ? 

可以自行做一下測驗哈!是只有第三條語句不會用到索引，其他的三條語句都會符合最左側原則。

關于這個最左側原則遠遠不止這么簡單的，一試就是一個坑，關于這部分內容咔咔后期會在優化文章中提到。

索引下推

還是使用這條 sql 語句：

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

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

在有了索引下推之后，查詢過程是根據 name、age 在存儲引擎獲取數據，返回對應的數據，不再到 server 層進行過濾。

當你使用 Explain 分析 SQL 語句時，如果出現了 Using index condition 那就是使用了索引下推，索引下推是在組合索引的情況出現幾率最大的。

索引存儲在什么地方

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

這時就要涉及到操作系統的概念，操作系統在磁盤中獲取數據，假設現在要取的數據大小是 1kb，但操作系統并不會只取出你需要的這 1kb，而是會取出 4kb 的數據。

為什么會是 4kb，因為在操作系統中一頁的數據就是 4kb。那又為什么只需要 1kb 而取出整頁的數據呢?

那就又會涉及到另一個概念那就是局部性原理：數據和程序都有聚集成群的傾向，在訪問了一條數據之后，在之后有極大的可能再次訪問這條數據和這條數據的相鄰數據。

所以說 MySQL 的 InnoDB 存儲引擎，在讀取數據時也會采取這種局部性原理，每次讀取的數據是 16kb。

在 InnoDB 存儲引擎下每頁的大小默認為 16kb，這個參數也可以進行調整，參數為 innodb_page_size。

最后一點：既然標題問的是索引數據存儲在什么地方，在第一句就直接回答了索引是存儲在磁盤中，并且以頁為單位進行從磁盤往內存讀取。

那為什么不直接存儲在內存中呢?你有沒有這個疑問呢?

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

總結

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

[[380983]]

作者：咔咔 

編輯：陶家龍 

征稿：有投稿、尋求報道意向技術人請添加小編微信 gordonlonglong

【51CTO原創稿件，合作站點轉載請注明原文作者和出處為51CTO.com】