總結(jié)下之前看到的一些關(guān)于MySQL索引原理的內(nèi)容，好記性不如爛筆頭。

1. B+樹

我們知道InnoDB的索引是以B+樹的形式組織的。B+樹是一種樹數(shù)據(jù)結(jié)構(gòu)，是一個n叉樹，每個節(jié)點通常有多個孩子，一顆B+樹包含根節(jié)點、內(nèi)部節(jié)點和葉子節(jié)點。

下面是B+樹的示例：

B+樹把所有的數(shù)據(jù)都存儲在葉子節(jié)點中，內(nèi)部節(jié)點只存放關(guān)鍵字和孩子指針，因此最大化了內(nèi)部節(jié)點的分支因子，所以B+樹的遍歷也更加高效。

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

使用B+樹作為索引結(jié)構(gòu)有如下優(yōu)勢：

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

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

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

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

2.InnoDB頁存儲結(jié)構(gòu)

2.1 存儲結(jié)構(gòu)

存儲引擎中所有數(shù)據(jù)都被存儲在表空間中，表又由Segment(段)、Extent(區(qū))、Page(頁)組成，如下為MySQL技術(shù)內(nèi)幕中介紹的InnoDB邏輯存儲結(jié)構(gòu)：

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

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

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

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

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

2.2 頁結(jié)構(gòu)

Page是整個InnoDB存儲的最基本構(gòu)件，也是InnoDB磁盤管理的最小單位，與數(shù)據(jù)庫相關(guān)的所有內(nèi)容都存儲在這種Page結(jié)構(gòu)里。每個Page使用一個32位的int值來唯一標(biāo)識，這也正好對應(yīng)InnoDB最大64TB的存儲容量（16Kib * 2^32 = 64Tib）。一個Page的結(jié)構(gòu)如下所示：

涉及的內(nèi)容包括：

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

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

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

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

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

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

將該結(jié)構(gòu)擴展到多個頁就有如下形式：

根據(jù)最大最小虛記錄將多個頁內(nèi)記錄的順序連接起來。

2.3 頁內(nèi)查詢

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

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

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

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

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

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

3. 索引結(jié)構(gòu)

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

3.1. 聚簇索引

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

考慮如下的數(shù)據(jù)：

其中Id作為主索引，Name作為輔助索引，則聚集索引的結(jié)構(gòu)如下：

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

下面以開頭的B+樹為例，再結(jié)合Page結(jié)構(gòu)，展示其內(nèi)部組織方式（只展示其中一部分）：

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

3.2 非聚簇索引

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

對于上面的表數(shù)據(jù)，非聚集索引的結(jié)構(gòu)如下：

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

3.3 聯(lián)合索引

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

4. InnoDB內(nèi)存管理

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

其中內(nèi)存池的主要工作包括：

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

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

1. 刷新內(nèi)存池中的數(shù)據(jù)，保證緩沖池中緩存的數(shù)據(jù)最新
2. 將已修改數(shù)據(jù)文件刷新到磁盤文件
3. 保證數(shù)據(jù)庫異常時InnoDB能恢復(fù)到正常運行狀態(tài)

這里主要關(guān)注內(nèi)存池的管理，上圖中緩沖池用于存放各種數(shù)據(jù)的緩存，緩沖池中的頁可以分為：空閑頁、數(shù)據(jù)頁和臟頁，如下：

Page Hash用于維護內(nèi)存Page和文件Page的映射關(guān)系，同時維護3個列表用于管理空閑頁、數(shù)據(jù)頁以及臟頁的裝載和淘汰。

1.LRU List

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

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

2.Free List

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

3.Flush List

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