1. 全表遍歷

• 將磁盤(pán)中存儲(chǔ)的所有數(shù)據(jù)記錄依次加載，與給定條件對(duì)比，直到找到目標(biāo)記錄；
• 類(lèi)比數(shù)組結(jié)構(gòu)的線(xiàn)性查找，效率較低；

2. 哈希結(jié)構(gòu)

• 結(jié)合數(shù)組和鏈表結(jié)構(gòu)（或者樹(shù)結(jié)構(gòu)）存儲(chǔ)數(shù)據(jù)；
• 通過(guò)哈希函數(shù)（散列函數(shù)）計(jì)算哈希地址，相同輸入在固定函數(shù)下輸出保持不變；
• 哈希結(jié)構(gòu)會(huì)發(fā)生哈希沖突，使用哈希桶或者紅黑樹(shù)可緩解哈希沖突；
• 哈希結(jié)構(gòu)查找效率較高，為O(1)；
• InnoDB和MyISAM存儲(chǔ)引擎均不支持哈希索引，而Memory存儲(chǔ)引擎支持哈希索引；

2.1 使用哈希結(jié)構(gòu)創(chuàng)建索引的缺點(diǎn)

• 哈希索引可滿(mǎn)足等值查詢(xún)（==、!=、IN），對(duì)于范圍查詢(xún)，效率較低；
• 哈希索引下數(shù)據(jù)存儲(chǔ)無(wú)序，對(duì)于排序查詢(xún)效率較低；
• 對(duì)于聯(lián)合索引，哈希索引將多個(gè)列結(jié)合進(jìn)行哈希計(jì)算，因此對(duì)于單獨(dú)的列無(wú)法進(jìn)行查詢(xún)；
• 哈希索引容易發(fā)生哈希沖突，此時(shí)查找效率降低；

2.2 哈希索引的適用性

• InnoDB存儲(chǔ)引擎不支持哈希索引，但提供了自適應(yīng)哈希索引（Adaptive Hash Index）提高數(shù)據(jù)檢索效率；
• 可通過(guò)show variables like '%adaptive_hash_index';查看MySQL是否開(kāi)啟了自適應(yīng)哈希索引；
• 自適應(yīng)哈希索引（Adaptive Hash Index）：如果某個(gè)數(shù)據(jù)頁(yè)被頻繁訪(fǎng)問(wèn)，則當(dāng)滿(mǎn)足一定條件時(shí)將該數(shù)據(jù)頁(yè)對(duì)應(yīng)地址存儲(chǔ)在哈希表中，如此下次訪(fǎng)問(wèn)該數(shù)據(jù)頁(yè)時(shí)可直接由哈希表中的地址獲取，而不用在B+樹(shù)中檢索；
  

3. 二叉搜索樹(shù)

• 本質(zhì)是二叉樹(shù)；
• 限制條件：左<根<右，即任意一顆子樹(shù)，其根節(jié)點(diǎn)的值大于左子樹(shù)所有節(jié)點(diǎn)的值，同時(shí)小于右子樹(shù)所有節(jié)點(diǎn)的值；
• 二叉搜索樹(shù)一般查找效率較高，時(shí)間復(fù)雜度為O(log₂ⁿ)；

• 缺點(diǎn)：極端情況下會(huì)退化為單鏈表，查找效率降低；
  

4. AVL樹(shù)

• AVL樹(shù)即平衡二叉搜索樹(shù)；
• 限制條件：二叉搜索樹(shù)的任意子樹(shù)的左右子樹(shù)高度差絕對(duì)值不能超過(guò)1；
• 優(yōu)點(diǎn)：解決了二叉搜索樹(shù)退化為單鏈表的問(wèn)題；
• 缺點(diǎn)：雖然二叉樹(shù)實(shí)現(xiàn)簡(jiǎn)單，但如果數(shù)據(jù)量巨大，會(huì)導(dǎo)致二叉樹(shù)高度過(guò)大，查找效率降低；
  

5. B樹(shù)

• 本質(zhì)是多叉平衡搜索樹(shù)，可解決AVL樹(shù)高度過(guò)高的問(wèn)題，提高查找效率；
  

6. B+樹(shù)

• 本質(zhì)是多叉平衡搜索樹(shù)，基于B樹(shù)做了一定改進(jìn)，更適合于文件索引系統(tǒng)；
• B+樹(shù)非葉節(jié)點(diǎn)中不存儲(chǔ)真實(shí)數(shù)據(jù)，只存儲(chǔ)索引；
  

6.1 B+ 樹(shù)和 B 樹(shù)的差異

• 有 k 個(gè)孩子的節(jié)點(diǎn)就有 k 個(gè)關(guān)鍵字。也就是孩子數(shù)量 = 關(guān)鍵字?jǐn)?shù)，而 B 樹(shù)中，孩子數(shù)量 = 關(guān)鍵字?jǐn)?shù)
  +1；
• 非葉子節(jié)點(diǎn)的關(guān)鍵字也會(huì)同時(shí)存在在子節(jié)點(diǎn)中，并且是在子節(jié)點(diǎn)中所有關(guān)鍵字的最大（或最小）；
• 非葉子節(jié)點(diǎn)僅用于索引，不保存數(shù)據(jù)記錄，跟記錄有關(guān)的信息都放在葉子節(jié)點(diǎn)中。而 B 樹(shù)中， 非
  葉子節(jié)點(diǎn)既保存索引，也保存數(shù)據(jù)記錄；
• 所有關(guān)鍵字都在葉子節(jié)點(diǎn)出現(xiàn)，葉子節(jié)點(diǎn)構(gòu)成一個(gè)有序鏈表，而且葉子節(jié)點(diǎn)本身按照關(guān)鍵字的大小從小到大順序鏈接；

6.2 采用B+樹(shù)創(chuàng)建索引的優(yōu)勢(shì)

• B+樹(shù)的內(nèi)節(jié)點(diǎn)不存儲(chǔ)真實(shí)數(shù)據(jù)記錄，而B(niǎo)樹(shù)內(nèi)節(jié)點(diǎn)會(huì)存儲(chǔ)部分真實(shí)數(shù)據(jù)；
• B+樹(shù)查詢(xún)效率更加穩(wěn)定；
• B+樹(shù)高度更低，查詢(xún)效率更高；
• 對(duì)于范圍查詢(xún)，B+樹(shù)只有葉子結(jié)點(diǎn)存儲(chǔ)有序的真實(shí)數(shù)據(jù)，因此查詢(xún)效率更高；

6.3 一些需要注意的問(wèn)題

1）為了減少I(mǎi)O，索引樹(shù)會(huì)一次性加載嗎？

• 如果數(shù)據(jù)表存儲(chǔ)的數(shù)據(jù)量非常大，則對(duì)應(yīng)的索引文件可能也會(huì)很大，如果一次性加載到內(nèi)存，對(duì)于內(nèi)存要求較高；
• 實(shí)際情況下，對(duì)于索引文件的加載是逐一進(jìn)行的；

2）B+樹(shù)的存儲(chǔ)能力如何？為何說(shuō)一般查找行記錄，最多只需1~3次磁盤(pán)IO？

• B+樹(shù)為多叉平衡搜索樹(shù)，每個(gè)節(jié)點(diǎn)對(duì)應(yīng)一個(gè)真實(shí)數(shù)據(jù)頁(yè)，每個(gè)數(shù)據(jù)頁(yè)默認(rèn)大小為16KB；
• 主鍵類(lèi)型一般采用INT（4B）或BIGINT（8B），指針類(lèi)型一般也占據(jù)4B或8B ，最大情況下一個(gè)數(shù)據(jù)頁(yè)可以存儲(chǔ)16KB/(8B+8B)≈1000條記錄；
• 對(duì)于目錄項(xiàng)記錄頁(yè)，每個(gè)數(shù)據(jù)頁(yè)假設(shè)可存儲(chǔ)1000條記錄，則當(dāng)B+樹(shù)高度為3時(shí)，可存儲(chǔ)約10⁹條記錄，數(shù)據(jù)量非常龐大；
• 實(shí)際情況中，B+樹(shù)上面三層可能不會(huì)完全填充，因此實(shí)際B+樹(shù)一般設(shè)計(jì)為2~4層，也就是磁盤(pán)I/O次數(shù)為2~4次。但I(xiàn)nnoDB存儲(chǔ)引擎設(shè)計(jì)時(shí)將根節(jié)點(diǎn)常駐在內(nèi)存，所以實(shí)際磁盤(pán)I/O次數(shù)為1~3次；

3）為什么說(shuō)B+樹(shù)比B-樹(shù)更適合實(shí)際應(yīng)用中操作系統(tǒng)的文件索引和數(shù)據(jù)庫(kù)索引？

B+樹(shù)只有葉子結(jié)點(diǎn)存儲(chǔ)真實(shí)數(shù)據(jù)，查詢(xún)效率更高更穩(wěn)定，磁盤(pán)占用更少；

4）Hash 索引與 B+ 樹(shù)索引的區(qū)別？

• InnoDB存儲(chǔ)引擎不支持Hash索引；
• Hash索引數(shù)據(jù)存儲(chǔ)無(wú)序，不支持ORDER BY排序，也不支持模糊查詢(xún)；
• Hash索引數(shù)據(jù)存儲(chǔ)無(wú)序，不能進(jìn)行范圍查詢(xún)；
• Hash索引不支持聯(lián)合索引的最左側(cè)原則，即聯(lián)合索引的部分索引無(wú)法使用；

5）Hash 索引與 B+ 樹(shù)索引是在建索引的時(shí)候手動(dòng)指定的嗎？

• InnoDB、MyISAM存儲(chǔ)引擎不支持Hash索引，對(duì)于InnoDB提供的自適應(yīng)哈希索引默認(rèn)開(kāi)啟，不需要手動(dòng)指定；
• Memory存儲(chǔ)引擎默認(rèn)采用Hash索引；

參考《尚硅谷》文章來(lái)源地址http://www.zghlxwxcb.cn/news/detail-536530.html

到了這里，關(guān)于MySQL為什么選擇B+樹(shù)創(chuàng)建索引的文章就介紹完了。如果您還想了解更多內(nèi)容，請(qǐng)?jiān)谟疑辖撬阉鱐OY模板網(wǎng)以前的文章或繼續(xù)瀏覽下面的相關(guān)文章，希望大家以后多多支持TOY模板網(wǎng)！