背景

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

按照id查詢唯一一條記錄

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

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

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

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

預(yù)備知識

什么是索引？

上一篇中有詳細(xì)的介紹露懒，可以過去看一下：什么是索引寡具？

索引的本質(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]使用二叉查找樹存儲如下：

Mysql索引的詳解知識送給大家

每個節(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)就變成下面這樣：

Mysql索引的詳解知識送給大家

二叉樹退化為了一個鏈表結(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-樹在是平衡二叉樹上進(jìn)化來的，前面介紹的幾種樹播瞳，每個節(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：

Mysql索引的詳解知識送給大家

每個節(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)圖：

Mysql索引的詳解知識送給大家

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ù)载佳，進(jìn)而影響查詢效率。

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作為輔助索引奄抽。

Mysql索引的詳解知識送給大家

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ù)的最小單位，和磁盤交互的時候都是以頁來進(jìn)行的敌呈，默認(rèn)是16kb贸宏，mysql中采用b+樹存儲數(shù)據(jù)，頁相當(dāng)于b+樹中的一個節(jié)點磕洪。

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

Mysql索引的詳解知識送給大家

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

Mysql索引的詳解知識送給大家

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

Mysql索引的詳解知識送給大家

再看看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ù)物理順序會變得混亂迹淌，但他們依然通過鏈表的方式保持著邏輯上的先后順序河绽，如下圖：

Mysql索引的詳解知識送給大家

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

Mysql索引的詳解知識送給大家

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

Mysql索引的詳解知識送給大家

看上圖笋额，每個行記錄的都有一個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ù)量進(jìn)行調(diào)整杆故。