­

淺析InnoDB引擎的索引和索引原理

淺析InnoDB引擎的索引和索引原理

什麼是InnoDB的索引

InnoDB的索引就是一顆B+樹。頁是InnoDB引擎在內存和磁盤之間交換數據的基本單位,頁的大小一般是16KB,頁的大小可以在啟動MySQL服務的時候通過更改innodb_page_size參數來設置。而InnoDB索引的節點就是頁。

B+樹的葉節點上的頁是數據頁,用於存放用戶存入數據庫中的一條一條的記錄,而非葉子節點上的頁是索引頁,存放索引記錄。一個節點存一個頁,所以又有」索引就是數據,數據就是索引「之說。B+樹同一層上的頁又是以雙向鏈表的形式來組織的。在數據頁和索引頁中,所有的記錄中都會存儲下一條記錄相對頁0位元組處的偏移量,從而將同一個頁中的所有記錄連成一個單鏈表(可以看成是一個單鏈表)的形式。

所以從數據庫的表中查找記錄可以分為兩步:

  1. 定位到記錄所在的頁
  2. 定位到頁中的具體記錄

快速定位到頁中的記錄

數據頁的大致結構:

在數據頁中,所有的記錄都是通過主鍵來排序,在數據頁中有兩條特殊的記錄分別是InfimumSupremum分別代表最小項和最大項。數據頁中還有一個結構就是目錄項,用來快速定位頁中的記錄。其原理是:數據頁中的所有記錄會按順序被分為多個組(每組4到8條記錄),而目錄項中存的就是組中最後一條記錄相對所在頁0位元組處的偏移量。這樣在頁中查找數據就可以先在目錄項中快速定位到記錄所在的範圍,然後通過遍歷找到記錄。在索引頁中查找記錄與之類似。

定位到記錄所在的頁

索引頁中主要存的其實也是一條一條的記錄,記錄中存的是當前節點的子節點的頁號,以及對應頁中的最小主鍵值。而索引頁中的記錄也是通過記錄中的主鍵值來排序的。這樣就可以在查找一條記錄時,從B+樹的根節點開始,以一種多分的策略

Tags: