總結下之前看到的一些關于MySQL索引原理的內容，好記性不如爛筆頭。

1. B+樹

我們知道InnoDB的索引是以B+樹的形式組織的。B+樹是一種樹數據結構，是一個n叉樹，每個節點通常有多個孩子，一顆B+樹包含根節點、內部節點和葉子節點。

下面是B+樹的示例：

B+樹把所有的數據都存儲在葉子節點中，內部節點只存放關鍵字和孩子指針，因此最大化了內部節點的分支因子，所以B+樹的遍歷也更加高效。

B+樹通常用于數據庫和操作系統的文件系統中，其特點是能夠保持數據穩定有序，其插入與修改擁有較穩定的對數時間復雜度。B+樹適合作為數據庫的基礎結構，完全是因為計算機的內存-機械硬盤兩層存儲結構。內存可以完成快速的隨機訪問（隨機訪問即給出任意一個地址，要求返回這個地址存儲的數據）但是容量較小。而硬盤的隨機訪問要經過機械動作（1磁頭移動、2盤片轉動），訪問效率比內存低幾個數量級，但是硬盤容量較大。典型的數據庫容量大大超過可用內存大小，這就決定了在B+樹中檢索一條數據很可能要借助幾次磁盤IO操作來完成。

使用B+樹作為索引結構有如下優勢：

1.B+樹非葉子節點上是不存儲數據的，僅存儲鍵值（聚集索引）。

之所以這么做是因為在數據庫中頁的大小是固定的，InnoDB中頁的默認大小是 16KB。如果不存儲數據，那么就會存儲更多的鍵值，相應的樹的階數（節點的子節點樹）就會更大，樹就會更矮更胖，如此一來查找數據進行磁盤的 IO 次數又會再次減少，數據查詢的效率也會更快。

另外真實數據庫中的B+樹應該是非常扁平的，其階數是等于鍵值的數量的，如果我們的B+樹一個節點可以存儲1000個鍵值，那么3層B+樹可以存儲1000×1000×1000=10億個數據。一般根節點是常駐內存的，所以一般我們查找10億數據，只需要2次磁盤IO。

2.B+樹索引的所有數據均存儲在葉子節點，而且數據是按照順序排列的。因而B+樹使得范圍查找，排序查找，分組查找以及去重查找變得異常簡單。

2.InnoDB頁存儲結構

2.1 存儲結構

存儲引擎中所有數據都被存儲在表空間中，表又由Segment(段)、Extent(區)、Page(頁)組成，如下為MySQL技術內幕中介紹的InnoDB邏輯存儲結構：

1.表空間：在默認情況下，InnoDB存儲引擎有一個共享表空間 ibdata1，所有的數據都放在這個表空間內.如果啟用了innodb_file_per_table參數，每張表的表空間只存放數據、索引和插入緩沖bitmap頁，其他的數據如undo信息、插入緩沖、double write buffer等還是存放在共享表空間中。

2.段：常見的段有數據段、索引段、回滾段等。數據段是B+樹的葉子結點，索引段為B+樹的非葉子結點

3.區：區由連續頁組成，每個區大小固定為1MB，為保證區中page的連續性通常InnoDB會一次從磁盤中申請4-5個區。在默認page的大小為16KB的情況下，一個區則由64個連續的page。

4.頁：頁是InnoDB磁盤管理的最小單位也叫做塊，默認大小為16kB。常見的頁有數據頁、undo頁、系統頁等。類型為B-tree Node的頁存放的即是表中行的實際數據

5.行：InnoDB存儲引擎中數據是按行進行存放的，每個頁中最多存放7992行記錄

2.2 頁結構

Page是整個InnoDB存儲的最基本構件，也是InnoDB磁盤管理的最小單位，與數據庫相關的所有內容都存儲在這種Page結構里。每個Page使用一個32位的int值來唯一標識，這也正好對應InnoDB最大64TB的存儲容量（16Kib * 2^32 = 64Tib）。一個Page的結構如下所示：

涉及的內容包括：

1. 頁頭(Page Header)：記錄頁面的控制信息，包括頁的左右兄弟頁面指針、頁面空間使用情況等
2. Infimum(最小虛記錄)/Supremum(最大虛記錄)：兩個固定位置存儲的虛記錄，本身并不存儲數據。最小虛記錄比任何記錄都小，而最大虛記錄比任何記錄都大。這兩個用來代表開頭結尾的Record存儲在System Records的段里,這個System Records和User Records是兩個平行的段。
3. 記錄堆(Record Heap)：也稱為User Records,以鏈表的形式存儲一條條行記錄，表示頁面已分配的記錄空間，也是索引數據的真正存儲區域。記錄堆分為兩種，即有效記錄(黃色)和已刪除記錄(紫色)。有效記錄就是索引正常使用的記錄，而已刪除記錄表示索引已經刪除，不再使用的記錄。隨著記錄的更新和刪除越來越頻繁，記錄堆中已刪除記錄將會越多，即會出現越來越多的空洞（碎片）。這些已刪除記錄連接起來，就會成為頁面的自由空間鏈表。
4. 未分配空間(Free Space)：指頁面未使用的存儲空間，隨著頁面不斷使用，未分配空間將會越來越小。當新插入一條記錄時，首先嘗試從自由空間鏈表中獲得合適的存儲位置（空間足夠），如果沒有滿足的，就會在未分配空間中申請。
5. Slot區：也稱為Page Directory，頁中某些記錄的相對位置，用于提升查詢效率。slot是一些頁面有效記錄的指針，每個slot占兩個字節，存儲了記錄相對頁面首地址的偏移。如果頁面有n條有效記錄，那么slot的數量就在n/8+2~n/4+2之間，它是記錄頁面有序和二分查找的關鍵。
6. 頁尾(Page Tailer)：頁面最后部分，占8個字節，主要存儲頁面的校驗信息。

上面提到，頁頭里包含了唯一id，頁的左右兄弟頁面指針，從而可以將頁抽象為如下結構：

Page的頭部保存了兩個指針，分別指向前一個Page和后一個Page，根據這兩個指針我們很容易想象出Page鏈接起來就是一個雙向鏈表的結構。

InnoDB的行數據和索引的存儲都位于User Records，存在4種不同的Record，它們分別是：

1. 主鍵索引樹非葉節點
2. 主鍵索引樹葉子節點
3. 輔助鍵索引樹非葉節點
4. 輔助鍵索引樹葉子節點

這4種節點的Record格式有一些差異，但是它們都存儲著Next指針指向下一個Record。User Record在Page內以單鏈表的形式存在，最初數據是按照插入的先后順序排列的，但是隨著新數據的插入和舊數據的刪除，數據物理順序會變得混亂，但他們依然保持著邏輯上的先后順序。

將該結構擴展到多個頁就有如下形式：

根據最大最小虛記錄將多個頁內記錄的順序連接起來。

2.3 頁內查詢

前面提到User Records中的記錄是以單鏈表的形式存在，這樣在插入一條記錄時，只要修改前后兩條記錄的指針就行，這樣就可以避免記錄的移動同時保證了有序性。但是，帶來的問題是，鏈表是無法在對數時間內使用二分查找，這樣的設計會導致查詢效率低下。為了高效地在一個頁中查找指定的一條記錄，InnoDB使用Page Directory提供了解決方案。

InnoDB會將一個頁中的所有記錄劃分成若干個組，每組4-8個記錄。將每個組最后一個記錄相對于第一個記錄的地址偏移量（可以定位到真實數據記錄）提取出來存放在頁中一個叫做Page Directory的數組中，數組中的元素就是這些地址偏移量，也稱為槽(slot)。

所以在一個頁中根據主鍵查找記錄是很快的，步驟為：

1. 二分法確定該記錄所在的槽，并找到該槽所在分組中主鍵值最小的那條記錄。
2. 通過next_record屬性遍歷單鏈表找到記錄

對于插入操作，首先通過查詢的方式確定插入的位置，在自由空間鏈表或未分配空間中獲得空間并寫記錄內容，slot所指向的鏈高度加1，同時維護好原鏈表的關系。

插入記錄后，如果Slot支鏈高度超過8，那么就將該支鏈拆分為兩個子鏈，同時多申請一個slot（平移此slot及其后面的空間）。

3. 索引結構

MySql提供了兩種索引存儲方式，一種叫做聚簇索引，一種叫做非聚簇索引。

3.1. 聚簇索引

行數據和主鍵B+樹存儲在一起，輔助鍵B+樹只存儲輔助鍵和主鍵，主鍵和非主鍵B+樹幾乎是兩種類型的樹。InnoDB使用的是聚簇索引，將主鍵組織到一棵B+樹中，而行數據就儲存在葉子節點上。

考慮如下的數據：

其中Id作為主索引，Name作為輔助索引，則聚集索引的結構如下：

當通過主鍵索引查找數據時，會連帶返回對應的記錄。當通過輔助鍵查找數據時，根據索引找到葉子節點中的主鍵值，根據主鍵值再到聚簇索引中得到完整的一行記錄，該行為也即我們常說的回表。需要說明一點的是，對于聯合主鍵，當存在輔助索引時，輔助索引也會保留聯合主鍵的多個字段，從而影響到索引文件的大小。

下面以開頭的B+樹為例，再結合Page結構，展示其內部組織方式（只展示其中一部分）：

注意Page和B+樹節點之間并沒有一一對應的關系，Page只是作為一個Record的保存容器，它存在的目的是便于對磁盤空間進行批量管理。

3.2 非聚簇索引

主鍵B+樹在葉子節點存儲指向真正數據行的指針，而非主鍵。MyISAM使用的是非聚簇索引，非聚簇索引的兩棵B+樹看上去沒什么不同，節點的結構完全一致只是存儲的內容不同而已，

對于上面的表數據，非聚集索引的結構如下：

非聚集索引中，主鍵索引B+樹的節點存儲了主鍵，輔助鍵索引B+樹存儲了輔助鍵。表數據存儲在獨立的地方，這兩顆B+樹的葉子節點都使用一個地址指向真正的表數據，對于表數據來說，這兩個鍵沒有任何差別。由于索引樹是獨立的，通過輔助鍵檢索無需訪問主鍵的索引樹。

3.3 聯合索引

聯合索引又叫復合索引。對于復合索引，Mysql從左到右的使用索引中的字段，一個查詢可以只使用索引中的一部分，但只能是最左側部分，即我們常說的最左前綴匹配原則。由于聯合索引的匹配是從左往右進行，且不能跳過中間列，因而在設計聯合索引時最好按照列的索引區分度來排序。

4. InnoDB內存管理

InnoDB存儲引擎的內存管理主要采用預分配內存空間的方式，數據以頁為單位加載進內存池，交由后臺線程使用并進行維護：

其中內存池的主要工作包括：

1. 維護所有進程/線程需要訪問的多個內部數據結構
2. 緩存磁盤上的數據，方便快速讀取，同時在對磁盤文件修改之前進行緩存
3. 緩存重做日志（redo log）

后臺線程的主要工作包括:

1. 刷新內存池中的數據，保證緩沖池中緩存的數據最新
2. 將已修改數據文件刷新到磁盤文件
3. 保證數據庫異常時InnoDB能恢復到正常運行狀態

這里主要關注內存池的管理，上圖中緩沖池用于存放各種數據的緩存，緩沖池中的頁可以分為：空閑頁、數據頁和臟頁，如下：

Page Hash用于維護內存Page和文件Page的映射關系，同時維護3個列表用于管理空閑頁、數據頁以及臟頁的裝載和淘汰。

1.LRU List

Innodb總是將磁盤中的數據按頁為單位讀取到緩沖池，然后按LRU算法來保存緩沖池中的數據，即最頻繁使用的頁在LRU列表的前端，而最少使用的頁在LRU列表的尾端。當緩沖池不能存放新讀取到的頁時，將首先釋放LRU列表中尾端的頁。稍有不同的是InnoDB存儲引擎對傳統的LRU算法做了一些優化。在InnoDB的存儲引擎中，LRU列表中還加入了midpoint位置。新讀取到的頁，雖然是最新訪問的頁，但并不是直接放入到LRU列表的首部，而是放入到LRU列表的midpoint位置，等待一定時間后再加入到LRU列表的new端成為熱點數據。在默認配置下，midpoint在LRU列表長度的5/8處。

這樣做的原因在于，若直接將讀取到的page放到LRU的首部，那么某些SQL操作可能會使緩沖池中的page被刷出。常見的這類操作為索引或數據的掃描操作。這類操作訪問表中的許多頁，而這些頁通常只是在這次查詢中需要，并不是活躍數據。如果直接放入到LRU首部，那么非常可能將真正的熱點數據從LRU列表中移除，在下一次需要時，InnoDB需要重新訪問磁盤讀取，這樣性能會低下。

2.Free List

LRU列表用來管理已經讀取的頁，但當數據庫剛啟動時，LRU列表是空的，即沒有任何的頁。這時頁都存放在Free列表中。當需要從緩沖池中分頁時，首先從Free列表中查找是否有可用的空閑頁，若有則將該頁從Free列表中刪除，放入到LRU列表中。否則，根據LRU算法，淘汰LRU列表末尾的頁，將該內存空間分配給新的頁。

3.Flush List

在LRU列表中的頁被修改后，稱該頁為臟頁，即緩沖池中的頁和磁盤上的頁的數據產生了不一致。這時數據庫會通過CHECKPOINT機制將臟頁刷新回磁盤，而Flush列表中的頁即為臟頁列表。需要注意的是，臟頁既存在于LRU列表中，也存在于Flush列表中。LRU列表用來管理緩沖池中頁的可用性，Flush列表用來管理將頁刷新回磁盤，二者互不影響。