快捷導(dǎo)航

如何實(shí)現(xiàn)MySQL的索引

更新時(shí)間：2022年01月26日 17:42:04 作者：?LiveEveryDay?

這篇文章主要介紹了如何實(shí)現(xiàn)MySQL的索引，MySQL中索引分三類，有B+樹索引、Hash索引和全文索引，下面我們一起來看看MySQL索引的具體實(shí)現(xiàn)，需要的小伙伴可以參考一下

MySQL中索引分三類：B+樹索引、Hash索引、全文索引。InnoDB存儲(chǔ)引擎中用的是B+樹索引。要介紹B+樹索引，不得不提二叉查找樹、平衡二叉樹和B樹這三種數(shù)據(jù)結(jié)構(gòu)。B+樹是從它們?nèi)齻€(gè)演化來的。

二叉查找樹：

圖中為user表建立了一個(gè)二叉查找樹的索引。節(jié)點(diǎn)中存儲(chǔ)了鍵（key）和數(shù)據(jù)（data）。數(shù)據(jù)對(duì)應(yīng)user表中的行數(shù)據(jù)。

如果查找id=12的用戶信息，流程如下：
1）將根節(jié)點(diǎn)作為當(dāng)前節(jié)點(diǎn)，12大于10，將10的右子節(jié)點(diǎn)（13節(jié)點(diǎn)）作為當(dāng)前節(jié)點(diǎn)。
2）12與13比較，將13的左子節(jié)點(diǎn)（12節(jié)點(diǎn)）作為當(dāng)前節(jié)點(diǎn)。
3）12與12比較，滿足條件，從當(dāng)前節(jié)點(diǎn)去除data，即id=12，name=xm。
利用二叉查找樹，3次可找到匹配數(shù)據(jù)。如果在表中一條一條查找，需要6次。

平衡二叉樹：

如果上面的二叉樹這樣構(gòu)造：

變成了一個(gè)鏈表，查詢id=17的用戶信息，需要查7次，相當(dāng)于全表掃描。導(dǎo)致這個(gè)現(xiàn)象是因?yàn)槎娌檎覙洳黄胶饬?。為了解決這個(gè)問題，需要用平衡二叉樹。
平衡二叉樹又稱 AVL 樹，在滿足二叉查找樹特性的基礎(chǔ)上，要求每個(gè)節(jié)點(diǎn)的左右子樹的高度差不能超過 1。

B樹：
因?yàn)閮?nèi)存的易失性，一般會(huì)將數(shù)據(jù)和索引存儲(chǔ)到磁盤中。和內(nèi)存比，從磁盤讀數(shù)據(jù)會(huì)慢很多，所以應(yīng)當(dāng)減少讀取次數(shù)。此外，從磁盤讀數(shù)據(jù)按照磁盤塊來讀取，而非一條一條的讀。
如果我們能把盡可能多的數(shù)據(jù)放進(jìn)磁盤塊中，那一次磁盤讀取操作就會(huì)讀取更多數(shù)據(jù)，那我們查找數(shù)據(jù)的時(shí)間也會(huì)大幅度降低。如果我們用樹這種數(shù)據(jù)結(jié)構(gòu)作為索引的數(shù)據(jù)結(jié)構(gòu)，那我們每查找一次數(shù)據(jù)就需要從磁盤中讀取一個(gè)節(jié)點(diǎn)，也就是我們說的一個(gè)磁盤塊。我們都知道平衡二叉樹可是每個(gè)節(jié)點(diǎn)只存儲(chǔ)一個(gè)鍵值和數(shù)據(jù)的。那說明什么？說明每個(gè)磁盤塊僅僅存儲(chǔ)一個(gè)鍵值和數(shù)據(jù)！那如果我們要存儲(chǔ)海量的數(shù)據(jù)呢？
可以想象到二叉樹的節(jié)點(diǎn)將會(huì)非常多，高度也會(huì)極其高，我們查找數(shù)據(jù)時(shí)也會(huì)進(jìn)行很多次磁盤 IO，我們查找數(shù)據(jù)的效率將會(huì)極低！
為了解決平衡二叉樹的這個(gè)弊端，我們應(yīng)該尋找一種單個(gè)節(jié)點(diǎn)可以存儲(chǔ)多個(gè)鍵值和數(shù)據(jù)的平衡樹。也就是我們接下來要說的 B 樹。

圖中的每個(gè)節(jié)點(diǎn)稱為頁（就是磁盤塊），在MySQL中數(shù)據(jù)讀取的基本單位都是頁。每個(gè)節(jié)點(diǎn)存儲(chǔ)了更多的鍵值和數(shù)據(jù)。子節(jié)點(diǎn)的個(gè)數(shù)一般稱為階，上述圖中B樹為3階B樹。
查找id=28的用戶信息，

流程如下：

1）先找到根節(jié)點(diǎn)也就是頁 1，判斷 28 在鍵值 17 和 35 之間，那么我們根據(jù)頁 1 中的指針 p2 找到頁 3。
2）將 28 和頁 3 中的鍵值相比較，28 在 26 和 30 之間，我們根據(jù)頁 3 中的指針 p2 找到頁 8。
3）將 28 和頁 8 中的鍵值相比較，發(fā)現(xiàn)有匹配的鍵值 28，鍵值 28 對(duì)應(yīng)的用戶信息為（28，bv）。

B+樹：

B+樹是對(duì)B樹的進(jìn)化，其不同：

1）B+樹非葉子節(jié)點(diǎn)不存儲(chǔ)數(shù)據(jù)，僅存儲(chǔ)鍵值，B樹則存儲(chǔ)鍵值和數(shù)據(jù)（為什么這么做？數(shù)據(jù)庫中頁的大小是固定的，InnoDB中默認(rèn)是16KB，如果不存數(shù)據(jù)，就可以存更多的鍵值，樹的階數(shù)會(huì)更大，樹就會(huì)更矮胖，查找數(shù)據(jù)進(jìn)行磁盤IO的次數(shù)就會(huì)減少，查詢效率快）。一般根節(jié)點(diǎn)是常駐內(nèi)存的。
2）B+樹索引的所有數(shù)據(jù)存儲(chǔ)在葉子節(jié)點(diǎn)，而且數(shù)據(jù)是按照順序排列的（使得范圍查找、排序查找、分組查找及去重查找很簡(jiǎn)單，而B樹因?yàn)閿?shù)據(jù)分散在各個(gè)節(jié)點(diǎn)，實(shí)現(xiàn)這一點(diǎn)很不容易），B+樹的葉子節(jié)點(diǎn)中的數(shù)據(jù)通過單向鏈表連接，各個(gè)頁之間通過雙向鏈表連接。

過上圖可以看到，在 InnoDB 中，我們通過數(shù)據(jù)頁之間通過雙向鏈表連接以及葉子節(jié)點(diǎn)中數(shù)據(jù)之間通過單向鏈表連接的方式可以找到表中所有的數(shù)據(jù)。

在 MySQL 中，B+ 樹索引按照存儲(chǔ)方式的不同分為聚集索引和非聚集索引。

利用聚集索引查找數(shù)據(jù)：

現(xiàn)在假設(shè)我們要查找 id>=18 并且 id<40 的用戶數(shù)據(jù)。

對(duì)應(yīng)的 sql 語句為：

select * from user where id>=18 and id<40;

其中id為主鍵，具體的查找過程如下：

1）一般根節(jié)點(diǎn)常駐內(nèi)存的，頁1已經(jīng)在內(nèi)存中了，不用讀磁盤，直接內(nèi)存讀取。
在內(nèi)存中頁1查找id>=18 and id<40或者范圍值，先找到id=18的鍵值。從頁1找到指針p2，定位到頁3。
2）從磁盤中讀取頁3，然后將頁3放入內(nèi)存中，然后進(jìn)行查找，可以找到鍵值18，然后拿到頁3中的指針p1，定位到頁8。
3）將頁8讀取到內(nèi)存中，根據(jù)二分查找法定位到鍵值18, 因?yàn)槭欠秶檎?，而且此時(shí)所有的數(shù)據(jù)又都存在葉子節(jié)點(diǎn)，并且是有序排列的，那么我們就可以對(duì)頁 8 中的鍵值依次進(jìn)行遍歷查找并匹配滿足條件的數(shù)據(jù)。
我們可以一直找到鍵值為 22 的數(shù)據(jù)，然后頁 8 中就沒有數(shù)據(jù)了，此時(shí)我們需要拿著頁 8 中的 p 指針去讀取頁 9 中的數(shù)據(jù)。
4）因?yàn)轫?9 不在內(nèi)存中，就又會(huì)加載頁 9 到內(nèi)存中，并通過和頁 8 中一樣的方式進(jìn)行數(shù)據(jù)的查找，直到將頁 12 加載到內(nèi)存中，發(fā)現(xiàn) 41 大于 40，此時(shí)不滿足條件。那么查找到此終止。

具體流程圖：