索引的數(shù)據(jù)結構和具體存儲引擎的實現(xiàn)有關，mysql中使用較多的索引有hash索引，B+樹索引，innodb的索引實現(xiàn)為B+樹，memory存儲引擎為hash索引。

B+樹是一個平衡的多叉樹，從根節(jié)點到每個葉子節(jié)點的高度差值不超過1，而且同層級的二節(jié)點間有指針相關連接，在B+樹上的常規(guī)檢索，從根節(jié)點到葉子節(jié)點的搜索效率基本相當，不會出現(xiàn)大幅波動，而且基于索引的順序掃描時，也可以利用雙向指針快速左右移動，效率非常高。因為，B+樹索引被廣泛應用于數(shù)據(jù)庫、文件系統(tǒng)等場景。

哈希索引就是采用一定的哈希算法，把鍵值換算成新的哈希值，檢索時不需要類似B+樹那樣從根節(jié)點到葉子節(jié)點逐級查找，只需一次哈希算法即可立刻定位到相應的位置，速度非?？臁?/p>

如果是等值查詢，那么哈希索引明顯有絕對優(yōu)勢，因為只需要經過一次算法即可找到相應的鍵值，前提是鍵值都是唯一的。如果鍵值不是唯一的，就需要先找到該鍵所在位置，然后再根據(jù)鏈表往后掃描，知道找到對應的數(shù)據(jù)

如果是范圍查詢檢索，這時候哈徐索引就毫無用武之地了，因為原先是有序的鍵值，經過哈希算法后，有可能變成不連續(xù)的了，就沒辦法再利用索引完成范圍查詢檢索

哈希所有也沒辦法利用索引完成排序，以及l(fā)ike這樣的部分模糊查詢

哈希索引也不支持多列聯(lián)合索引的最左匹配規(guī)則

B+樹索引的關鍵字檢索效率比較平均，不像B樹那樣波動大，在有大量重復鍵值情況下，哈希索引的效率也是極低的，因此存在哈希碰撞問題。

【5分鐘背八股】74：mysql索引結構有哪些，各自的優(yōu)劣是什么？.jpeg