背景

使用mysql最多的就是查詢枫虏，我們迫切的希望mysql能查詢的更快一些嗦篱，我們經(jīng)常用到的查詢有：

按照id查詢唯一一條記錄

按照某些個字段查詢對應(yīng)的記錄

查找某個范圍的所有記錄（between and）

對查詢出來的結(jié)果排序

mysql的索引的目的是使上面的各種查詢能夠更快。

預(yù)備知識

什么是索引霹粥？

上一篇中有詳細的介紹渺氧，可以過去看一下：什么是索引嫂沉？

索引的本質(zhì)：通過不斷地縮小想要獲取數(shù)據(jù)的范圍來篩選出最終想要的結(jié)果，同時把隨機的事件變成順序的事件缚态，也就是說磁椒，有了這種索引機制，我們可以總是用同一種查找方式來鎖定數(shù)據(jù)玫芦。

磁盤中數(shù)據(jù)的存取

以機械硬盤來說浆熔，先了解幾個概念。

扇區(qū)：磁盤存儲的最小單位桥帆，扇區(qū)一般大小為512Byte医增。

磁盤塊：文件系統(tǒng)與磁盤交互的的最小單位（計算機系統(tǒng)讀寫磁盤的最小單位），一個磁盤塊由連續(xù)幾個（2^n）扇區(qū)組成老虫，塊一般大小一般為4KB叶骨。

磁盤讀取數(shù)據(jù)：磁盤讀取數(shù)據(jù)靠的是機械運動，每次讀取數(shù)據(jù)花費的時間可以分為尋道時間祈匙、旋轉(zhuǎn)延遲忽刽、傳輸時間三個部分，尋道時間指的是磁臂移動到指定磁道所需要的時間菊卷，主流磁盤一般在5ms以下缔恳；旋轉(zhuǎn)延遲就是我們經(jīng)常聽說的磁盤轉(zhuǎn)速，比如一個磁盤7200轉(zhuǎn)洁闰，表示每分鐘能轉(zhuǎn)7200次歉甚，也就是說1秒鐘能轉(zhuǎn)120次，旋轉(zhuǎn)延遲就是1/120/2 = 4.17ms扑眉；傳輸時間指的是從磁盤讀出或?qū)?shù)據(jù)寫入磁盤的時間纸泄，一般在零點幾毫秒，相對于前兩個時間可以忽略不計腰素。那么訪問一次磁盤的時間聘裁，即一次磁盤IO的時間約等于5+4.17 = 9ms左右，聽起來還挺不錯的弓千，但要知道一臺500 -MIPS的機器每秒可以執(zhí)行5億條指令衡便，因為指令依靠的是電的性質(zhì)，換句話說執(zhí)行一次IO的時間可以執(zhí)行40萬條指令，數(shù)據(jù)庫動輒十萬百萬乃至千萬級數(shù)據(jù)镣陕，每次9毫秒的時間谴餐，顯然是個災(zāi)難。

mysql中的頁

mysql中和磁盤交互的最小單位稱為頁呆抑，頁是mysql內(nèi)部定義的一種數(shù)據(jù)結(jié)構(gòu)岂嗓，默認(rèn)為16kb，相當(dāng)于4個磁盤塊鹊碍，也就是說mysql每次從磁盤中讀取一次數(shù)據(jù)是16KB厌殉，要么不讀取，要讀取就是16KB侈咕，此值可以修改的公罕。

數(shù)據(jù)檢索過程

我們對數(shù)據(jù)存儲方式不做任何優(yōu)化，直接將數(shù)據(jù)庫中表的記錄存儲在磁盤中乎完，假如某個表只有一個字段熏兄，為int類型，int占用4個byte树姨，每個磁盤塊可以存儲1000條記錄摩桶，100萬的記錄需要1000個磁盤塊，如果我們需要從這100萬記錄中檢索所需要的記錄帽揪，需要讀取1000個磁盤塊的數(shù)據(jù)（需要1000次io）硝清，每次io需要9ms，那么1000次需要9000ms=9s转晰，100條數(shù)據(jù)隨便一個查詢就是9秒蔗崎，這種情況我們是無法接受的邓深，顯然是不行的冬耿。

我們迫切的需求是什么日月？

我們迫切需要這樣的數(shù)據(jù)結(jié)構(gòu)和算法：

需要一種數(shù)據(jù)存儲結(jié)構(gòu)：當(dāng)從磁盤中檢索數(shù)據(jù)的時候能，夠減少磁盤的io次數(shù)褐望，最好能夠降低到一個穩(wěn)定的常量值

需要一種檢索算法：當(dāng)從磁盤中讀取磁盤塊的數(shù)據(jù)之后，這些塊中可能包含多條記錄，這些記錄被加載到內(nèi)存中，那么需要一種算法能夠快速從內(nèi)存多條記錄中快速檢索出目標(biāo)數(shù)據(jù)

我們來找找，看是否能夠找到這樣的算法和數(shù)據(jù)結(jié)構(gòu)箕昭。

我們看一下常見的檢索算法和數(shù)據(jù)結(jié)構(gòu)泌霍。

循環(huán)遍歷查找

從一組無序的數(shù)據(jù)中查找目標(biāo)數(shù)據(jù)，常見的方法是遍歷查詢，n條數(shù)據(jù)，時間復(fù)雜度為O(n)窿吩，最快需要1次，最壞的情況需要n次，查詢效率不穩(wěn)定。

二分法查找

二分法查找也稱為折半查找，用于在一個有序數(shù)組中快速定義某一個需要查找的數(shù)據(jù)。

原理是：

先將一組無序的數(shù)據(jù)排序（升序或者降序）之后放在數(shù)組中，此處用升序來舉例說明：用數(shù)組中間位置的數(shù)據(jù)A和需要查找的數(shù)據(jù)F對比初坠，如果A=F锁保，則結(jié)束查找者填；如果A<F瘫筐，則將查找的范圍縮小至數(shù)組中A數(shù)據(jù)右邊的部分铐姚；如果A>F策肝，則將查找范圍縮小至數(shù)組中A數(shù)據(jù)左邊的部分，繼續(xù)按照上面的方法直到找到F為止谦屑。

示例：

從下列有序數(shù)字中查找數(shù)字9驳糯，過程如下

[1,2,3,4,5,6,7,8,9]

第1次查找：[1,2,3,4,5,6,7,8,9]中間位置值為5，9>5氢橙，將查找范圍縮小至5右邊的部分：[6、7恬偷、8悍手、9]

第2次查找：[6、7袍患、8坦康、9]中間值為8，9>8 诡延，將范圍縮小至8右邊部分：[9]

第3次查找：在[9]中查找9滞欠，找到了。

可以看到查找速度是相當(dāng)快的肆良，每次查找都會使范圍減半筛璧，如果我們采用順序查找，上面數(shù)據(jù)最快需要1次惹恃，最多需要9次夭谤，而二分法查找最多只需要3次，耗時時間也比較穩(wěn)定巫糙。

二分法查找時間復(fù)雜度是:O(logN)(N為數(shù)據(jù)量)朗儒，100萬數(shù)據(jù)查找最多只需要20次（2^20=1048576）

二分法查找數(shù)據(jù)的優(yōu)點：定位數(shù)據(jù)非常快参淹，前提是：目標(biāo)數(shù)組是有序的醉锄。

有序數(shù)組

如果我們將mysql中表的數(shù)據(jù)以有序數(shù)組的方式存儲在磁盤中，那么我們定位數(shù)據(jù)步驟是：

取出目標(biāo)表的所有數(shù)據(jù)浙值，存放在一個有序數(shù)組中

如果目標(biāo)表的數(shù)據(jù)量非常大恳不，從磁盤中加載到內(nèi)存中需要的內(nèi)存也非常大

步驟取出所有數(shù)據(jù)耗費的io次數(shù)太多，步驟2耗費的內(nèi)存空間太大亥鸠，還有新增數(shù)據(jù)的時候妆够，為了保證數(shù)組有序识啦，插入數(shù)據(jù)會涉及到數(shù)組內(nèi)部數(shù)據(jù)的移動，也是比較耗時的神妹，顯然用這種方式存儲數(shù)據(jù)是不可取的颓哮。

鏈表

鏈表相當(dāng)于在每個節(jié)點上增加一些指針，可以和前面或者后面的節(jié)點連接起來鸵荠，就像一列火車一樣冕茅，每節(jié)車廂相當(dāng)于一個節(jié)點，車廂內(nèi)部可以存儲數(shù)據(jù)蛹找，每個車廂和下一節(jié)車廂相連姨伤。

鏈表分為單鏈表和雙向鏈表。

單鏈表

每個節(jié)點中有持有指向下一個節(jié)點的指針庸疾，只能按照一個方向遍歷鏈表乍楚，結(jié)構(gòu)如下：

//單項鏈表

class Node1{

private Object data;//存儲數(shù)據(jù)

private Node1 nextNode;//指向下一個節(jié)點

}

雙向鏈表

每個節(jié)點中兩個指針，分別指向當(dāng)前節(jié)點的上一個節(jié)點和下一個節(jié)點届慈，結(jié)構(gòu)如下：

//雙向鏈表

class Node2{

private Object data;//存儲數(shù)據(jù)

private Node1 prevNode;//指向上一個節(jié)點

private Node1 nextNode;//指向下一個節(jié)點

}

鏈表的優(yōu)點：

可以快速定位到上一個或者下一個節(jié)點

可以快速刪除數(shù)據(jù)徒溪，只需改變指針的指向即可，這點比數(shù)組好

鏈表的缺點：

無法向數(shù)組那樣金顿，通過下標(biāo)隨機訪問數(shù)據(jù)

查找數(shù)據(jù)需從第一個節(jié)點開始遍歷臊泌，不利于數(shù)據(jù)的查找，查找時間和無需數(shù)據(jù)類似揍拆，需要全遍歷渠概，最差時間是O(N)

二叉查找樹

二叉樹是每個結(jié)點最多有兩個子樹的樹結(jié)構(gòu)，通常子樹被稱作“左子樹”（left subtree）和“右子樹”（right subtree）嫂拴。二叉樹常被用于實現(xiàn)二叉查找樹和二叉堆播揪。二叉樹有如下特性：

1、每個結(jié)點都包含一個元素以及n個子樹顷牌，這里0≤n≤2剪芍。2、左子樹和右子樹是有順序的窟蓝，次序不能任意顛倒罪裹，左子樹的值要小于父結(jié)點，右子樹的值要大于父結(jié)點运挫。

數(shù)組[20,10,5,15,30,25,35]使用二叉查找樹存儲如下：

每個節(jié)點上面有兩個指針（left,rigth）状共，可以通過這2個指針快速訪問左右子節(jié)點，檢索任何一個數(shù)據(jù)最多只需要訪問3個節(jié)點谁帕，相當(dāng)于訪問了3次數(shù)據(jù)峡继，時間為O(logN)，和二分法查找效率一樣匈挖，查詢數(shù)據(jù)還是比較快的碾牌。

但是如果我們插入數(shù)據(jù)是有序的康愤，如[5,10,15,20,30,25,35]，那么結(jié)構(gòu)就變成下面這樣：

二叉樹退化為了一個鏈表結(jié)構(gòu)舶吗，查詢數(shù)據(jù)最差就變?yōu)榱薕(N)征冷。

二叉樹的優(yōu)缺點：

查詢數(shù)據(jù)的效率不穩(wěn)定，若樹左右比較平衡的時誓琼，最差情況為O(logN)检激，如果插入數(shù)據(jù)是有序的，退化為了鏈表腹侣，查詢時間變成了O(N)

數(shù)據(jù)量大的情況下叔收，會導(dǎo)致樹的高度變高，如果每個節(jié)點對應(yīng)磁盤的一個塊來存儲一條數(shù)據(jù)傲隶，需io次數(shù)大幅增加饺律，顯然用此結(jié)構(gòu)來存儲數(shù)據(jù)是不可取的

平衡二叉樹（AVL樹）

平衡二叉樹是一種特殊的二叉樹，所以他也滿足前面說到的二叉查找樹的兩個特性跺株，同時還有一個特性：

它的左右兩個子樹的高度差的絕對值不超過1蓝晒，并且左右兩個子樹都是一棵平衡二叉樹。

平衡二叉樹相對于二叉樹來說帖鸦，樹的左右比較平衡，不會出現(xiàn)二叉樹那樣退化成鏈表的情況胚嘲，不管怎么插入數(shù)據(jù)作儿，最終通過一些調(diào)整，都能夠保證樹左右高度相差不大于1馋劈。

這樣可以讓查詢速度比較穩(wěn)定攻锰，查詢中遍歷節(jié)點控制在O(logN)范圍內(nèi)

如果數(shù)據(jù)都存儲在內(nèi)存中，采用AVL樹來存儲妓雾，還是可以的娶吞，查詢效率非常高。不過我們的數(shù)據(jù)是存在磁盤中械姻，用過采用這種結(jié)構(gòu)妒蛇，每個節(jié)點對應(yīng)一個磁盤塊，數(shù)據(jù)量大的時候楷拳，也會和二叉樹一樣绣夺，會導(dǎo)致樹的高度變高，增加了io次數(shù)欢揖，顯然用這種結(jié)構(gòu)存儲數(shù)據(jù)也是不可取的陶耍。

B-樹

B杠樹，千萬不要讀作B減樹了她混，B-樹在是平衡二叉樹上進化來的烈钞，前面介紹的幾種樹泊碑，每個節(jié)點上面只有一個元素涂籽，而B-樹節(jié)點中可以放多個元素待牵，主要是為了降低樹的高度。

一棵m階的B-Tree有如下特性【特征描述的有點繞座菠，看不懂的可以跳過仪媒，看后面的圖】：

每個節(jié)點最多有m個孩子沉桌，m稱為b樹的階

除了根節(jié)點和葉子節(jié)點外，其它每個節(jié)點至少有Ceil(m/2)個孩子

若根節(jié)點不是葉子節(jié)點算吩，則至少有2個孩子

所有葉子節(jié)點都在同一層留凭，且不包含其它關(guān)鍵字信息

每個非終端節(jié)點包含n個關(guān)鍵字（健值）信息

關(guān)鍵字的個數(shù)n滿足：ceil(m/2)-1 <= n <= m-1

ki(i=1,…n)為關(guān)鍵字，且關(guān)鍵字升序排序

Pi(i=1,…n)為指向子樹根節(jié)點的指針偎巢。P(i-1)指向的子樹的所有節(jié)點關(guān)鍵字均小于ki蔼夜，但都大于k(i-1)

B-Tree結(jié)構(gòu)的數(shù)據(jù)可以讓系統(tǒng)高效的找到數(shù)據(jù)所在的磁盤塊。為了描述B-Tree压昼，首先定義一條記錄為一個二元組[key, data] 求冷，key為記錄的鍵值，對應(yīng)表中的主鍵值窍霞，data為一行記錄中除主鍵外的數(shù)據(jù)匠题。對于不同的記錄，key值互不相同但金。

B-Tree中的每個節(jié)點根據(jù)實際情況可以包含大量的關(guān)鍵字信息和分支韭山，如下圖所示為一個3階的B-Tree：

每個節(jié)點占用一個盤塊的磁盤空間，一個節(jié)點上有兩個升序排序的關(guān)鍵字和三個指向子樹根節(jié)點的指針冷溃，指針存儲的是子節(jié)點所在磁盤塊的地址钱磅。兩個鍵將數(shù)據(jù)劃分成的三個范圍域，對應(yīng)三個指針指向的子樹的數(shù)據(jù)的范圍域似枕。以根節(jié)點為例盖淡，關(guān)鍵字為17和35，P1指針指向的子樹的數(shù)據(jù)范圍為小于17凿歼，P2指針指向的子樹的數(shù)據(jù)范圍為17~35褪迟，P3指針指向的子樹的數(shù)據(jù)范圍為大于35。

模擬查找關(guān)鍵字29的過程：

根據(jù)根節(jié)點找到磁盤塊1毅往，讀入內(nèi)存牵咙。【磁盤I/O操作第1次】

比較關(guān)鍵字29在區(qū)間（17,35）攀唯，找到磁盤塊1的指針P2

根據(jù)P2指針找到磁盤塊3洁桌，讀入內(nèi)存『钹郑【磁盤I/O操作第2次】

比較關(guān)鍵字29在區(qū)間（26,30）另凌，找到磁盤塊3的指針P2

根據(jù)P2指針找到磁盤塊8谱轨，讀入內(nèi)存》托唬【磁盤I/O操作第3次】

在磁盤塊8中的關(guān)鍵字列表中找到關(guān)鍵字29

分析上面過程土童，發(fā)現(xiàn)需要3次磁盤I/O操作，和3次內(nèi)存查找操作工坊，由于內(nèi)存中的關(guān)鍵字是一個有序表結(jié)構(gòu)献汗，可以利用二分法快速定位到目標(biāo)數(shù)據(jù)，而3次磁盤I/O操作是影響整個B-Tree查找效率的決定因素王污。

B-樹相對于avl樹罢吃，通過在節(jié)點中增加節(jié)點內(nèi)部數(shù)據(jù)的個數(shù)來減少磁盤的io操作。

上面我們說過mysql是采用頁方式來讀寫數(shù)據(jù)昭齐，每頁是16KB尿招，我們用B-樹來存儲mysql的記錄，每個節(jié)點對應(yīng)mysql中的一頁（16KB）阱驾，假如每行記錄加上樹節(jié)點中的1個指針占160Byte就谜，那么每個節(jié)點可以存儲1000（16KB/160byte）條數(shù)據(jù)，樹的高度為3的節(jié)點大概可以存儲（第一層1000+第二層1000^2+第三層1000^3）10億條記錄里覆，是不是非常驚訝丧荐，一個高度為3個B-樹大概可以存儲10億條記錄，我們從10億記錄中查找數(shù)據(jù)只需要3次io操作可以定位到目標(biāo)數(shù)據(jù)所在的頁喧枷，而頁內(nèi)部的數(shù)據(jù)又是有序的篮奄，然后將其加載到內(nèi)存中用二分法查找，是非掣钊ィ快的。

可以看出使用B-樹定位某個值還是很快的(10億數(shù)據(jù)中3次io操作+內(nèi)存中二分法)昼丑，但是也是有缺點的：B-不利于范圍查找呻逆，比如上圖中我們需要查找[15,36]區(qū)間的數(shù)據(jù)，需要訪問7個磁盤塊（1/2/7/3/8/4/9）菩帝，io次數(shù)又上去了咖城，范圍查找也是我們經(jīng)常用到的，所以b-樹也不太適合在磁盤中存儲需要檢索的數(shù)據(jù)呼奢。

b+樹

先看個b+樹結(jié)構(gòu)圖：

b+樹的特征

每個結(jié)點至多有m個子女

除根結(jié)點外,每個結(jié)點至少有[m/2]個子女宜雀，根結(jié)點至少有兩個子女

有k個子女的結(jié)點必有k個關(guān)鍵字

父節(jié)點中持有訪問子節(jié)點的指針

父節(jié)點的關(guān)鍵字在子節(jié)點中都存在（如上面的1/20/35在每層都存在），要么是最小值握础，要么是最大值辐董，如果節(jié)點中關(guān)鍵字是升序的方式，父節(jié)點的關(guān)鍵字是子節(jié)點的最小值

最底層的節(jié)點是葉子節(jié)點

除葉子節(jié)點之外禀综，其他節(jié)點不保存數(shù)據(jù)简烘，只保存關(guān)鍵字和指針

葉子節(jié)點包含了所有數(shù)據(jù)的關(guān)鍵字以及data苔严，葉子節(jié)點之間用鏈表連接起來，可以非常方便的支持范圍查找

b+樹與b-樹的幾點不同

b+樹中一個節(jié)點如果有k個關(guān)鍵字孤澎，最多可以包含k個子節(jié)點（k個關(guān)鍵字對應(yīng)k個指針）届氢；而b-樹對應(yīng)k+1個子節(jié)點（多了一個指向子節(jié)點的指針）

b+樹除葉子節(jié)點之外其他節(jié)點值存儲關(guān)鍵字和指向子節(jié)點的指針，而b-樹還存儲了數(shù)據(jù)覆旭，這樣同樣大小情況下退子，b+樹可以存儲更多的關(guān)鍵字

b+樹葉子節(jié)點中存儲了所有關(guān)鍵字及data，并且多個節(jié)點用鏈表連接型将，從上圖中看子節(jié)點中數(shù)據(jù)從左向右是有序的寂祥，這樣快速可以支撐范圍查找（先定位范圍的最大值和最小值，然后子節(jié)點中依靠鏈表遍歷范圍數(shù)據(jù)）

B-Tree和B+Tree該如何選擇茶敏？

B-Tree因為非葉子結(jié)點也保存具體數(shù)據(jù)壤靶，所以在查找某個關(guān)鍵字的時候找到即可返回。而B+Tree所有的數(shù)據(jù)都在葉子結(jié)點惊搏，每次查找都得到葉子結(jié)點贮乳。所以在同樣高度的B-Tree和B+Tree中，B-Tree查找某個關(guān)鍵字的效率更高恬惯。

由于B+Tree所有的數(shù)據(jù)都在葉子結(jié)點向拆，并且結(jié)點之間有指針連接，在找大于某個關(guān)鍵字或者小于某個關(guān)鍵字的數(shù)據(jù)的時候酪耳，B+Tree只需要找到該關(guān)鍵字然后沿著鏈表遍歷就可以了浓恳，而B-Tree還需要遍歷該關(guān)鍵字結(jié)點的根結(jié)點去搜索。

由于B-Tree的每個結(jié)點（這里的結(jié)點可以理解為一個數(shù)據(jù)頁）都存儲主鍵+實際數(shù)據(jù)碗暗，而B+Tree非葉子結(jié)點只存儲關(guān)鍵字信息颈将，而每個頁的大小有限是有限的，所以同一頁能存儲的B-Tree的數(shù)據(jù)會比B+Tree存儲的更少言疗。這樣同樣總量的數(shù)據(jù)晴圾，B-Tree的深度會更大，增大查詢時的磁盤I/O次數(shù)噪奄，進而影響查詢效率死姚。

Mysql的存儲引擎和索引

mysql內(nèi)部索引是由不同的引擎實現(xiàn)的，主要說一下InnoDB和MyISAM這兩種引擎中的索引勤篮，這兩種引擎中的索引都是使用b+樹的結(jié)構(gòu)來存儲的都毒。

InnoDB中的索引

Innodb中有2種索引：主鍵索引（聚集索引）、輔助索引（非聚集索引）碰缔。

主鍵索引：每個表只有一個主鍵索引账劲，葉子節(jié)點同時保存了主鍵的值也數(shù)據(jù)記錄。

輔助索引：葉子節(jié)點保存了索引字段的值以及主鍵的值。

MyISAM引擎中的索引

不管是主鍵索引還是輔助索引結(jié)構(gòu)都是一樣的涤垫，葉子節(jié)點保存了索引字段的值以及數(shù)據(jù)記錄的地址姑尺。

如下圖：

有一張表，Id作為主索引蝠猬，Name作為輔助索引切蟋。

InnoDB數(shù)據(jù)檢索過程

如果需要查詢id=14的數(shù)據(jù)，只需要在左邊的主鍵索引中檢索就可以了榆芦。

如果需要搜索name='Ellison'的數(shù)據(jù)柄粹，需要2步：

先在輔助索引中檢索到name='Ellison'的數(shù)據(jù)，獲取id為14

再到主鍵索引中檢索id為14的記錄

輔助索引這個查詢過程在mysql中叫做回表匆绣。

MyISAM數(shù)據(jù)檢索過程

在索引中找到對應(yīng)的關(guān)鍵字驻右，獲取關(guān)鍵字對應(yīng)的記錄的地址

通過記錄的地址查找到對應(yīng)的數(shù)據(jù)記錄

我們用的最多的是innodb存儲引擎，所以此處主要說一下innodb索引的情況崎淳，innodb中最好是采用主鍵查詢堪夭，這樣只需要一次索引，如果使用輔助索引檢索拣凹，涉及到回表操作森爽，比主鍵查詢要耗時一些。

innodb中輔助索引為什么不像myisam那樣存儲記錄的地址嚣镜？

表中的數(shù)據(jù)發(fā)生變更的時候爬迟，會影響其他記錄地址的變化，如果輔助索引中記錄數(shù)據(jù)的地址菊匿，此時會受影響付呕，而主鍵的值一般是很少更新的，當(dāng)頁中的記錄發(fā)生地址變更的時候跌捆，對輔助索引是沒有影響的徽职。

我們來看一下mysql中頁的結(jié)構(gòu)，頁是真正存儲記錄的地方佩厚，對應(yīng)B+樹中的一個節(jié)點活箕，也是mysql中讀寫數(shù)據(jù)的最小單位，頁的結(jié)構(gòu)設(shè)計也是相當(dāng)有水平的可款，能夠加快數(shù)據(jù)的查詢。

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

mysql中頁是innodb中存儲數(shù)據(jù)的基本單位克蚂，也是mysql中管理數(shù)據(jù)的最小單位闺鲸，和磁盤交互的時候都是以頁來進行的，默認(rèn)是16kb埃叭，mysql中采用b+樹存儲數(shù)據(jù)摸恍，頁相當(dāng)于b+樹中的一個節(jié)點。

頁的結(jié)構(gòu)如下圖：

每個Page都有通用的頭和尾，但是中部的內(nèi)容根據(jù)Page的類型不同而發(fā)生變化立镶。Page的頭部里有我們關(guān)心的一些數(shù)據(jù)壁袄，下圖把Page的頭部詳細信息顯示出來：

我們重點關(guān)注和數(shù)據(jù)組織結(jié)構(gòu)相關(guān)的字段：Page的頭部保存了兩個指針，分別指向前一個Page和后一個Page媚媒，根據(jù)這兩個指針我們很容易想象出Page鏈接起來就是一個雙向鏈表的結(jié)構(gòu)嗜逻，如下圖：

再看看Page的主體內(nèi)容，我們主要關(guān)注行數(shù)據(jù)和索引的存儲缭召，他們都位于Page的User Records部分栈顷，User Records占據(jù)Page的大部分空間，User Records由一條一條的Record組成嵌巷。在一個Page內(nèi)部萄凤，單鏈表的頭尾由固定內(nèi)容的兩條記錄來表示，字符串形式的"Infimum"代表開頭搪哪，"Supremum"代表結(jié)尾靡努，這兩個用來代表開頭結(jié)尾的Record存儲在System Records的，Infinum晓折、Supremum和User Records組成了一個單向鏈表結(jié)構(gòu)惑朦。最初數(shù)據(jù)是按照插入的先后順序排列的，但是隨著新數(shù)據(jù)的插入和舊數(shù)據(jù)的刪除已维，數(shù)據(jù)物理順序會變得混亂行嗤，但他們依然通過鏈表的方式保持著邏輯上的先后順序，如下圖：

把User Record的組織形式和若干Page組合起來垛耳，就看到了稍微完整的形式栅屏。

innodb為了快速查找記錄，在頁中定義了一個稱之為page directory的目錄槽（slots）,每個槽位占用兩個字節(jié)（用于保存指向記錄的地址）堂鲜，page directory中的多個slot組成了一個有序數(shù)組（可用于二分法快速定位記錄栈雳，向下看），行記錄被Page Directory邏輯的分成了多個塊缔莲，塊與塊之間是有序的哥纫，能夠加速記錄的查找，如下圖：

看上圖痴奏，每個行記錄的都有一個n_owned的區(qū)域（圖中粉色區(qū)域）蛀骇，n_owned標(biāo)識所屬的slot這個這個塊有多少條數(shù)據(jù)，偽記錄Infimum的n_owned值總是1读拆，記錄Supremum的n_owned的取值范圍為[1,8]擅憔，其他用戶記錄n_owned的取值范圍[4,8]，并且只有每個塊中最大的那條記錄的n_owned才會有值檐晕，其他的用戶記錄的n_owned為0暑诸。

數(shù)據(jù)檢索過程

在page中查詢數(shù)據(jù)的時候蚌讼，先通過b+樹中查詢方法定位到數(shù)據(jù)所在的頁，然后將頁內(nèi)整體加載到內(nèi)存中个榕，通過二分法在page directory中檢索數(shù)據(jù)篡石，縮小范圍，比如需要檢索7西采，通過二分法查找到7位于slot2和slot3所指向的記錄中間凰萨，然后從slot3指向的記錄5開始向后向后一個個找，可以找到記錄7苛让，如果里面沒有7沟蔑，走到slot2向的記錄8結(jié)束。

n_owned范圍控制在[4,8]內(nèi)狱杰，能保證每個slot管轄的范圍內(nèi)數(shù)據(jù)量控制在[4,8]個瘦材，能夠加速目標(biāo)數(shù)據(jù)的查找，當(dāng)有數(shù)據(jù)插入的時候仿畸，page directory為了控制每個slot對應(yīng)塊中記錄的個數(shù)（[4,8]）食棕，此時page directory中會對slot的數(shù)量進行調(diào)整。