總結下之前看到的一些關於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的結構如下所示：
涉及的內容包括：
- 頁頭(Page Header)：記錄頁面的控制信息，包括頁的左右兄弟頁面指針、頁面空間使用情況等
- Infimum(最小虛記錄)/Supremum(最大虛記錄)：兩個固定位置存儲的虛記錄，本身並不存儲數據。最小虛記錄比任何記錄都小，而最大虛記錄比任何記錄都大。這兩個用來代表開頭結尾的Record存儲在System Records的段裡,這個System Records和User Records是兩個平行的段。
- 記錄堆(Record Heap)：也稱為User Records,以鏈表的形式存儲一條條行記錄，表示頁面已分配的記錄空間，也是索引數據的真正存儲區域。記錄堆分為兩種，即有效記錄(黃色)和已刪除記錄(紫色)。有效記錄就是索引正常使用的記錄，而已刪除記錄表示索引已經刪除，不再使用的記錄。隨著記錄的更新和刪除越來越頻繁，記錄堆中已刪除記錄將會越多，即會出現越來越多的空洞（碎片）。這些已刪除記錄連接起來，就會成為頁面的自由空間鏈表。
- 未分配空間(Free Space)：指頁面未使用的存儲空間，隨著頁面不斷使用，未分配空間將會越來越小。當新插入一條記錄時，首先嚐試從自由空間鏈表中獲得合適的存儲位置（空間足夠），如果沒有滿足的，就會在未分配空間中申請。
- Slot區：也稱為Page Directory，頁中某些記錄的相對位置，用於提升查詢效率。slot是一些頁面有效記錄的指針，每個slot佔兩個字節，存儲了記錄相對頁面首地址的偏移。如果頁面有n條有效記錄，那麼slot的數量就在n/8+2~n/4+2之間，它是記錄頁面有序和二分查找的關鍵。
- 頁尾(Page Tailer)：頁面最後部分，佔8個字節，主要存儲頁面的校驗信息。
上面提到，頁頭裡包含了唯一id，頁的左右兄弟頁面指針，從而可以將頁抽象為如下結構：
Page的頭部保存了兩個指針，分別指向前一個Page和後一個Page，根據這兩個指針我們很容易想象出Page鏈接起來就是一個雙向鏈表的結構。
InnoDB的行數據和索引的存儲都位於User Records，存在4種不同的Record，它們分別是：
- 主鍵索引樹非葉節點
- 主鍵索引樹葉子節點
- 輔助鍵索引樹非葉節點
- 輔助鍵索引樹葉子節點
這4種節點的Record格式有一些差異，但是它們都存儲著Next指針指向下一個Record。User Record在Page內以單鏈表的形式存在，最初數據是按照插入的先後順序排列的，但是隨著新數據的插入和舊數據的刪除，數據物理順序會變得混亂，但他們依然保持著邏輯上的先後順序。
將該結構擴展到多個頁就有如下形式：
根據最大最小虛記錄將多個頁內記錄的順序連接起來。
2.3 頁內查詢
前面提到User Records中的記錄是以單鏈表的形式存在，這樣在插入一條記錄時，只要修改前後兩條記錄的指針就行，這樣就可以避免記錄的移動同時保證了有序性。但是，帶來的問題是，鏈表是無法在對數時間內使用二分查找，這樣的設計會導致查詢效率低下。為了高效地在一個頁中查找指定的一條記錄，InnoDB使用Page Directory提供瞭解決方案。
InnoDB會將一個頁中的所有記錄劃分成若干個組，每組4-8個記錄。將每個組最後一個記錄相對於第一個記錄的地址偏移量（可以定位到真實數據記錄）提取出來存放在頁中一個叫做Page Directory的數組中，數組中的元素就是這些地址偏移量，也稱為槽(slot)。
所以在一個頁中根據主鍵查找記錄是很快的，步驟為：
- 二分法確定該記錄所在的槽，並找到該槽所在分組中主鍵值最小的那條記錄。
- 通過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存儲引擎的內存管理主要採用預分配內存空間的方式，數據以頁為單位加載進內存池，交由後臺線程使用並進行維護：
其中內存池的主要工作包括：
- 維護所有進程/線程需要訪問的多個內部數據結構
- 緩存磁盤上的數據，方便快速讀取，同時在對磁盤文件修改之前進行緩存
- 緩存重做日誌（redo log）
後臺線程的主要工作包括:
- 刷新內存池中的數據，保證緩衝池中緩存的數據最新
- 將已修改數據文件刷新到磁盤文件
- 保證數據庫異常時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列表用來管理將頁刷新回磁盤，二者互不影響。
