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

二叉查找樹：

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

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

平衡二叉樹：

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

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

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

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

流程如下：

• 1）先找到根節(jié)點也就是頁 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 對應(yīng)的用戶信息為（28，bv）。

B+樹：

B+樹是對B樹的進化，其不同：

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

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

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

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

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

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

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

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

• 1）一般根節(jié)點常駐內(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)存中，然后進行查找，可以找到鍵值18，然后拿到頁3中的指針p1，定位到頁8。
• 3）將頁8讀取到內(nèi)存中，根據(jù)二分查找法定位到鍵值18, 因為是范圍查找，而且此時所有的數(shù)據(jù)又都存在葉子節(jié)點，并且是有序排列的，那么我們就可以對頁 8 中的鍵值依次進行遍歷查找并匹配滿足條件的數(shù)據(jù)。
• 我們可以一直找到鍵值為 22 的數(shù)據(jù)，然后頁 8 中就沒有數(shù)據(jù)了，此時我們需要拿著頁 8 中的 p 指針去讀取頁 9 中的數(shù)據(jù)。
• 4）因為頁 9 不在內(nèi)存中，就又會加載頁 9 到內(nèi)存中，并通過和頁 8 中一樣的方式進行數(shù)據(jù)的查找，直到將頁 12 加載到內(nèi)存中，發(fā)現(xiàn) 41 大于 40，此時不滿足條件。那么查找到此終止。

具體流程圖：

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

查找幸運數(shù)字為33的用戶信息，需要回表。

到此這篇關(guān)于如何實現(xiàn)MySQL的索引的文章就介紹到這了,更多相關(guān)實現(xiàn)MySQL的索引內(nèi)容請搜索腳本之家以前的文章或繼續(xù)瀏覽下面的相關(guān)文章希望大家以后多多支持腳本之家！

最新評論