快捷導(dǎo)航

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

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

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

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

二叉查找樹(shù)：

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

如果查找id=12的用戶(hù)信息，流程如下：
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比較，滿(mǎn)足條件，從當(dāng)前節(jié)點(diǎn)去除data，即id=12，name=xm。
利用二叉查找樹(shù)，3次可找到匹配數(shù)據(jù)。如果在表中一條一條查找，需要6次。

平衡二叉樹(shù)：

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

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

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

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

流程如下：

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

B+樹(shù)：

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

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

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

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

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

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

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

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

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

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

具體流程圖：