關於MySQL B+樹索引與雜湊索引詳解

2022-03-30 13:02:10

索引介紹

索引是一種特殊的資料庫結構，被設計用來快速查詢資料庫表中的特定記錄。索引有多種型別，就像字典有拼音查詢和偏旁查詢一樣都是為了提高檢索效率。MySQL中最常見的索引型別有B+樹索引 和 雜湊索引，下面來簡單介紹一下這兩種索引型別有哪些差別和優劣。

B+樹索引

B+樹索引是一種多路徑的平衡搜尋樹，具有如下特點：

1.非葉子節點不儲存資料，只儲存索引值
2.葉子節點儲存所有的索引值和資料
3.同級節點通過指標自小而大順序連結
4.節點內的資料也是自小而大順序存放
5.葉子節點擁有父節點的所有資訊

結構如下圖：

優點

由於資料順序存放，所以無論是區間還是順序掃描都更快。
非葉子節點不儲存資料，因此幾乎都能放在記憶體中，搜尋效率更高
單節點中可儲存的資料更多，平均掃描I/O請求樹更少
平均查詢效率穩定（每次查詢都從根結點到葉子結點，查詢路徑長度相同）

缺點

新增資料不是按順序遞增時，索引樹需要重新排列，容易造成碎片和頁分裂情況。

雜湊索引

雜湊索引採用一定的雜湊演演算法，把鍵值換算成新的雜湊值，檢索時不需要類似B+樹那樣從根節點到葉子節點逐級查詢，只需一次雜湊演演算法即可立刻定位到相應的位置，速度非常快，具有如下特點：

1.雜湊索引建立在雜湊表的基礎上
2.對於每個值，需要先計算出對應的雜湊碼（Hash Code），不同值的雜湊碼唯一
3.把雜湊碼儲存在雜湊表中，同時雜湊表也儲存指向對應每行記錄的指標

結構如下圖：

優點

大量唯一等值查詢時，雜湊索引效率通常更高。

缺點

雜湊索引對於範圍查詢和模糊匹配查詢顯得無能為力。
雜湊索引不支援排序操作，對於多列聯合索引的最左匹配規則也不支援。
雜湊索引不支援字首索引，因為雜湊索引始終是使用索引列的全部內容來計算雜湊值。
如果存在雜湊衝突的情況，也就是不同的索引列有著相同的雜湊值，這時候需要遍歷連結串列中所有的行指標進行逐行比對，直到找到所有滿足條件的行，效率較低。

補充：二者區別

備註：先說下，在MySQL檔案裡，實際上是把B+樹索引寫成了BTREE，例如像下面這樣的寫法：

CREATE TABLE t(
aid int unsigned not null auto_increment,
userid int unsigned not null default 0,
username varchar(20) not null default ‘',
detail varchar(255) not null default ‘',
primary key(aid),
unique key(uid) USING BTREE,
key (username(12)) USING BTREE — 此處 uname 列只建立了最左12個字元長度的部分索引
)engine=InnoDB;

B+樹是一個平衡的多叉樹，從根節點到每個葉子節點的高度差值不超過1，而且同層級的節點間有指標相互連結。

在B+樹上的常規檢索，從根節點到葉子節點的搜尋效率基本相當，不會出現大幅波動，而且基於索引的順序掃描時，也可以利用雙向指標快速左右移動，效率非常高。

因此，B+樹索引被廣泛應用於資料庫、檔案系統等場景。順便說一下，xfs檔案系統比ext3/ext4效率高很多的原因之一就是，它的檔案及目錄索引結構全部採用B+樹索引，而ext3/ext4的檔案目錄結構則採用Linked list, hashed B-tree、Extents/Bitmap等索引資料結構，因此在高I/O壓力下，其IOPS能力不如xfs。

簡單地說，雜湊索引就是採用一定的雜湊演演算法，把鍵值換算成新的雜湊值，檢索時不需要類似B+樹那樣從根節點到葉子節點逐級查詢，只需一次雜湊演演算法即可立刻定位到相應的位置，速度非常快。

從上面的圖來看，B+樹索引和雜湊索引的明顯區別是：

如果是等值查詢，那麼雜湊索引明顯有絕對優勢，因為只需要經過一次演演算法即可找到相應的鍵值；當然了，這個前提是，鍵值都是唯一的。如果鍵值不是唯一的，就需要先找到該鍵所在位置，然後再根據連結串列往後掃描，直到找到相應的資料；
從示意圖中也能看到，如果是範圍查詢檢索，這時候雜湊索引就毫無用武之地了，因為原先是有序的鍵值，經過雜湊演演算法後，有可能變成不連續的了，就沒辦法再利用索引完成範圍查詢檢索；
同理，雜湊索引也沒辦法利用索引完成排序，以及like ‘xxx%’ 這樣的部分模糊查詢（這種部分模糊查詢，其實本質上也是範圍查詢）；
雜湊索引也不支援多列聯合索引的最左匹配規則；
B+樹索引的關鍵字檢索效率比較平均，不像B樹那樣波動幅度大，在有大量重複鍵值情況下，雜湊索引的效率也是極低的，因為存在所謂的雜湊碰撞問題。

總結

到此這篇關於MySQL B+樹索引與雜湊索引的文章就介紹到這了,更多相關MySQL B+樹索引與雜湊索引內容請搜尋it145.com以前的文章或繼續瀏覽下面的相關文章希望大家以後多多支援it145.com！

關於MySQL B+樹索引與雜湊索引詳解

目錄

索引介紹

B+樹索引

優點

缺點

雜湊索引

優點

缺點

補充：二者區別

總結

熱門文章