MySQL索引的原理

MySQL資料庫支援多種索引，例如B樹索引、雜湊索引、全文索引等，本文著重講解下B樹索引。 （推薦：《mysql教學》）

#索引原理&本質

MySQL官方解釋：索引是為MySQL提高取得資料效率的數據結構，為了快速查詢資料。索引是滿足某種特定查找演算法的資料結構，而這些資料結構會以某種方式指向數據，從而實現高效查找數據。

B 樹

MySQL一般以B 樹作為其索引結構，那麼B 樹有什麼特色呢？

樹度為n的話，每個節點指針上限為2n 1

非葉子節點不存儲數據，只存儲指針索引；葉子節點存儲所有數據，不存儲指針

在經典B 樹基礎上增加了順序存取指針，每個葉子節點都有指向相鄰下一個葉子節點的指針，如圖所示。主要為了提高區間存取的效能，例如要找key為20到50的所有數據，只要以順序存取路線一次存取所有資料節點。

帶順序存取的B 樹簡圖

#局部性原理與磁碟預讀

那麼為什麼資料庫系統普遍使用B 樹作為索引結構，而不選例如紅黑樹其他結構呢？

首先要先來介紹下局部性原理和磁碟預讀的概念。

一般來說，索引本身較大，不會全部儲存在記憶體中，會以索引檔案的形式儲存在磁碟上。所以索引查找資料過程中就會產生磁碟IO操作，而磁碟IO相對於記憶體存取非常緩慢，因此索引結構要盡量減少磁碟IO的存取次數。

為了減少磁碟IO，磁碟往往會進行資料預讀，會從某個位置開始，預先向後讀取一定長度的資料放入內存，即局部性原理。因為磁碟順序讀取的效率較高，所以不需要尋道時間，因此可以提高IO效率。

預讀長度一般為頁的整數倍，主記憶體和磁碟以頁作為單位交換資料。當需要讀取的資料不在記憶體時，觸發缺頁中斷，系統會向磁碟發出讀取磁碟資料的請求，磁碟找到資料的起始位置並向後連續讀取一頁或幾頁資料載入內存，然後中斷返回，系統繼續運作。而一般資料庫系統設計時會將B 樹節點的大小設定為一頁，這樣每個節點的載入只需要一次IO。

以上是MySQL索引的原理的詳細內容。更多資訊請關注PHP中文網其他相關文章！