本篇介紹下Mysql的InnoDB索引相關(guān)知識(shí)，從各種樹(shù)到索引原理到存儲(chǔ)的細(xì)節(jié)。

InnoDB是Mysql的默認(rèn)存儲(chǔ)引擎(Mysql5.5.5之前是MyISAM，文檔)。本著高效學(xué)習(xí)的目的，本篇以介紹InnoDB為主，少量涉及MyISAM作為對(duì)比。

這篇文章是我在學(xué)習(xí)過(guò)程中總結(jié)完成的，內(nèi)容主要來(lái)自書(shū)本和博客(參考文獻(xiàn)會(huì)給出)，過(guò)程中加入了一些自己的理解，描述不準(zhǔn)確的地方煩請(qǐng)指出。

本來(lái)不打算從二叉搜索樹(shù)開(kāi)始，因?yàn)榫W(wǎng)上已經(jīng)有太多相關(guān)文章，但是考慮到清晰的圖示對(duì)理解問(wèn)題有很大幫助，也為了保證文章完整性，最后還是加上了這部分。

先看看幾種樹(shù)形結(jié)構(gòu)：

1 搜索二叉樹(shù)：每個(gè)節(jié)點(diǎn)有兩個(gè)子節(jié)點(diǎn)，數(shù)據(jù)量的增大必然導(dǎo)致高度的快速增加，顯然這個(gè)不適合作為大量數(shù)據(jù)存儲(chǔ)的基礎(chǔ)結(jié)構(gòu)。

2 B樹(shù)：一棵m階B樹(shù)是一棵平衡的m路搜索樹(shù)。最重要的性質(zhì)是每個(gè)非根節(jié)點(diǎn)所包含的關(guān)鍵字個(gè)數(shù) j 滿足：┌m/2┐ - 1 <= j <= m - 1；一個(gè)節(jié)點(diǎn)的子節(jié)點(diǎn)數(shù)量會(huì)比關(guān)鍵字個(gè)數(shù)多1，這樣關(guān)鍵字就變成了子節(jié)點(diǎn)的分割標(biāo)志。一般會(huì)在圖示中把關(guān)鍵字畫(huà)到子節(jié)點(diǎn)中間，非常形象，也容易和后面的B+樹(shù)區(qū)分。由于數(shù)據(jù)同時(shí)存在于葉子節(jié)點(diǎn)和非葉子結(jié)點(diǎn)中，無(wú)法簡(jiǎn)單完成按順序遍歷B樹(shù)中的關(guān)鍵字，必須用中序遍歷的方法。

3 B+樹(shù)：一棵m階B樹(shù)是一棵平衡的m路搜索樹(shù)。最重要的性質(zhì)是每個(gè)非根節(jié)點(diǎn)所包含的關(guān)鍵字個(gè)數(shù) j 滿足：┌m/2┐ - 1 <= j <= m；子樹(shù)的個(gè)數(shù)最多可以與關(guān)鍵字一樣多。非葉節(jié)點(diǎn)存儲(chǔ)的是子樹(shù)里最小的關(guān)鍵字。同時(shí)數(shù)據(jù)節(jié)點(diǎn)只存在于葉子節(jié)點(diǎn)中，且葉子節(jié)點(diǎn)間增加了橫向的指針，這樣順序遍歷所有數(shù)據(jù)將變得非常容易。

4 B*樹(shù)：一棵m階B樹(shù)是一棵平衡的m路搜索樹(shù)。最重要的兩個(gè)性質(zhì)是1每個(gè)非根節(jié)點(diǎn)所包含的關(guān)鍵字個(gè)數(shù) j 滿足：┌m2/3┐ - 1 <= j <= m；2非葉節(jié)點(diǎn)間添加了橫向指針。

B/B+/B*三種樹(shù)有相似的操作，比如檢索/插入/刪除節(jié)點(diǎn)。這里只重點(diǎn)關(guān)注插入節(jié)點(diǎn)的情況，且只分析他們?cè)诋?dāng)前節(jié)點(diǎn)已滿情況下的插入操作，因?yàn)檫@個(gè)動(dòng)作稍微復(fù)雜且能充分體現(xiàn)幾種樹(shù)的差異。與之對(duì)比的是檢索節(jié)點(diǎn)比較容易實(shí)現(xiàn)，而刪除節(jié)點(diǎn)只要完成與插入相反的過(guò)程即可（在實(shí)際應(yīng)用中刪除并不是插入的完全逆操作，往往只刪除數(shù)據(jù)而保留下空間為后續(xù)使用）。

先看B樹(shù)的分裂，下圖的紅色值即為每次新插入的節(jié)點(diǎn)。每當(dāng)一個(gè)節(jié)點(diǎn)滿后，就需要發(fā)生分裂（分裂是一個(gè)遞歸過(guò)程，參考下面7的插入導(dǎo)致了兩層分裂），由于B樹(shù)的非葉子節(jié)點(diǎn)同樣保存了鍵值，所以已滿節(jié)點(diǎn)分裂后的值將分布在三個(gè)地方：1原節(jié)點(diǎn)，2原節(jié)點(diǎn)的父節(jié)點(diǎn)，3原節(jié)點(diǎn)的新建兄弟節(jié)點(diǎn)（參考5，7的插入過(guò)程）。分裂有可能導(dǎo)致樹(shù)的高度增加（參考3，7的插入過(guò)程），也可能不影響樹(shù)的高度（參考5，6的插入過(guò)程）。

B+樹(shù)的分裂：當(dāng)一個(gè)結(jié)點(diǎn)滿時(shí)，分配一個(gè)新的結(jié)點(diǎn)，并將原結(jié)點(diǎn)中1/2的數(shù)據(jù)復(fù)制到新結(jié)點(diǎn)，最后在父結(jié)點(diǎn)中增加新結(jié)點(diǎn)的指針；B+樹(shù)的分裂只影響原結(jié)點(diǎn)和父結(jié)點(diǎn)，而不會(huì)影響兄弟結(jié)點(diǎn)，所以它不需要指向兄弟節(jié)點(diǎn)的指針。

B*樹(shù)的分裂：當(dāng)一個(gè)結(jié)點(diǎn)滿時(shí)，如果它的下一個(gè)兄弟結(jié)點(diǎn)未滿，那么將一部分?jǐn)?shù)據(jù)移到兄弟結(jié)點(diǎn)中，再在原結(jié)點(diǎn)插入關(guān)鍵字，最后修改父結(jié)點(diǎn)中兄弟結(jié)點(diǎn)的關(guān)鍵字（因?yàn)樾值芙Y(jié)點(diǎn)的關(guān)鍵字范圍改變了）。如果兄弟也滿了，則在原結(jié)點(diǎn)與兄弟結(jié)點(diǎn)之間增加新結(jié)點(diǎn)，并各復(fù)制1/3的數(shù)據(jù)到新結(jié)點(diǎn)，最后在父結(jié)點(diǎn)增加新結(jié)點(diǎn)的指針。可以看到B*樹(shù)的分裂非常巧妙，因?yàn)锽*樹(shù)要保證分裂后的節(jié)點(diǎn)還要2/3滿，如果采用B+樹(shù)的方法，只是簡(jiǎn)單的將已滿的節(jié)點(diǎn)一分為二，會(huì)導(dǎo)致每個(gè)節(jié)點(diǎn)只有1/2滿，這不滿足B*樹(shù)的要求了。所以B*樹(shù)采取的策略是在本節(jié)點(diǎn)滿后，繼續(xù)插入兄弟節(jié)點(diǎn)（這也是為什么B*樹(shù)需要在非葉子節(jié)點(diǎn)加一個(gè)兄弟間的鏈表），直到把兄弟節(jié)點(diǎn)也塞滿，然后拉上兄弟節(jié)點(diǎn)一起湊份子，自己和兄弟節(jié)點(diǎn)各出資1/3成立新節(jié)點(diǎn)，這樣的結(jié)果是3個(gè)節(jié)點(diǎn)剛好是2/3滿，達(dá)到B*樹(shù)的要求，皆大歡喜。

B+樹(shù)適合作為數(shù)據(jù)庫(kù)的基礎(chǔ)結(jié)構(gòu)，完全是因?yàn)橛?jì)算機(jī)的內(nèi)存-機(jī)械硬盤(pán)兩層存儲(chǔ)結(jié)構(gòu)。內(nèi)存可以完成快速的隨機(jī)訪問(wèn)（隨機(jī)訪問(wèn)即給出任意一個(gè)地址，要求返回這個(gè)地址存儲(chǔ)的數(shù)據(jù)）但是容量較小。而硬盤(pán)的隨機(jī)訪問(wèn)要經(jīng)過(guò)機(jī)械動(dòng)作（1磁頭移動(dòng) 2盤(pán)片轉(zhuǎn)動(dòng)），訪問(wèn)效率比內(nèi)存低幾個(gè)數(shù)量級(jí)，但是硬盤(pán)容量較大。典型的數(shù)據(jù)庫(kù)容量大大超過(guò)可用內(nèi)存大小，這就決定了在B+樹(shù)中檢索一條數(shù)據(jù)很可能要借助幾次磁盤(pán)IO操作來(lái)完成。如下圖所示：通常向下讀取一個(gè)節(jié)點(diǎn)的動(dòng)作可能會(huì)是一次磁盤(pán)IO操作，不過(guò)非葉節(jié)點(diǎn)通常會(huì)在初始階段載入內(nèi)存以加快訪問(wèn)速度。同時(shí)為提高在節(jié)點(diǎn)間橫向遍歷速度，真實(shí)數(shù)據(jù)庫(kù)中可能會(huì)將圖中藍(lán)色的CPU計(jì)算/內(nèi)存讀取優(yōu)化成二叉搜索樹(shù)（InnoDB中的page directory機(jī)制）。

真實(shí)數(shù)據(jù)庫(kù)中的B+樹(shù)應(yīng)該是非常扁平的，可以通過(guò)向表中順序插入足夠數(shù)據(jù)的方式來(lái)驗(yàn)證InnoDB中的B+樹(shù)到底有多扁平。我們通過(guò)如下圖的CREATE語(yǔ)句建立一個(gè)只有簡(jiǎn)單字段的測(cè)試表，然后不斷添加數(shù)據(jù)來(lái)填充這個(gè)表。通過(guò)下圖的統(tǒng)計(jì)數(shù)據(jù)（來(lái)源見(jiàn)參考文獻(xiàn)1）可以分析出幾個(gè)直觀的結(jié)論，這幾個(gè)結(jié)論宏觀的展現(xiàn)了數(shù)據(jù)庫(kù)里B+樹(shù)的尺度。

1 每個(gè)葉子節(jié)點(diǎn)存儲(chǔ)了468行數(shù)據(jù)，每個(gè)非葉子節(jié)點(diǎn)存儲(chǔ)了大約1200個(gè)鍵值，這是一棵平衡的1200路搜索樹(shù)！

2 對(duì)于一個(gè)22.1G容量的表，也只需要高度為3的B+樹(shù)就能存儲(chǔ)了，這個(gè)容量大概能滿足很多應(yīng)用的需要了。如果把高度增大到4，則B+樹(shù)的存儲(chǔ)容量立刻增大到25.9T之巨！

3 對(duì)于一個(gè)22.1G容量的表，B+樹(shù)的高度是3，如果要把非葉節(jié)點(diǎn)全部加載到內(nèi)存也只需要少于18.8M的內(nèi)存（如何得出的這個(gè)結(jié)論？因?yàn)閷?duì)于高度為2的樹(shù)，1203個(gè)葉子節(jié)點(diǎn)也只需要18.8M空間，而22.1G從良表的高度是3，非葉節(jié)點(diǎn)1204個(gè)。同時(shí)我們假設(shè)葉子節(jié)點(diǎn)的尺寸是大于非葉節(jié)點(diǎn)的，因?yàn)槿~子節(jié)點(diǎn)存儲(chǔ)了行數(shù)據(jù)而非葉節(jié)點(diǎn)只有鍵和少量數(shù)據(jù)。），只使用如此少的內(nèi)存就可以保證只需要一次磁盤(pán)IO操作就檢索出所需的數(shù)據(jù)，效率是非常之高的。

可以說(shuō)數(shù)據(jù)庫(kù)必須有索引，沒(méi)有索引則檢索過(guò)程變成了順序查找，O(n)的時(shí)間復(fù)雜度幾乎是不能忍受的。我們非常容易想象出一個(gè)只有單關(guān)鍵字組成的表如何使用B+樹(shù)進(jìn)行索引，只要將關(guān)鍵字存儲(chǔ)到樹(shù)的節(jié)點(diǎn)即可。當(dāng)數(shù)據(jù)庫(kù)一條記錄里包含多個(gè)字段時(shí)，一棵B+樹(shù)就只能存儲(chǔ)主鍵，如果檢索的是非主鍵字段，則主鍵索引失去作用，又變成順序查找了。這時(shí)應(yīng)該在第二個(gè)要檢索的列上建立第二套索引。 這個(gè)索引由獨(dú)立的B+樹(shù)來(lái)組織。有兩種常見(jiàn)的方法可以解決多個(gè)B+樹(shù)訪問(wèn)同一套表數(shù)據(jù)的問(wèn)題，一種叫做聚簇索引（clustered index ），一種叫做非聚簇索引（secondary index）。這兩個(gè)名字雖然都叫做索引，但這并不是一種單獨(dú)的索引類型，而是一種數(shù)據(jù)存儲(chǔ)方式。對(duì)于聚簇索引存儲(chǔ)來(lái)說(shuō)，行數(shù)據(jù)和主鍵B+樹(shù)存儲(chǔ)在一起，輔助鍵B+樹(shù)只存儲(chǔ)輔助鍵和主鍵，主鍵和非主鍵B+樹(shù)幾乎是兩種類型的樹(shù)。對(duì)于非聚簇索引存儲(chǔ)來(lái)說(shuō)，主鍵B+樹(shù)在葉子節(jié)點(diǎn)存儲(chǔ)指向真正數(shù)據(jù)行的指針，而非主鍵。

InnoDB使用的是聚簇索引，將主鍵組織到一棵B+樹(shù)中，而行數(shù)據(jù)就儲(chǔ)存在葉子節(jié)點(diǎn)上，若使用"where id = 14"這樣的條件查找主鍵，則按照B+樹(shù)的檢索算法即可查找到對(duì)應(yīng)的葉節(jié)點(diǎn)，之后獲得行數(shù)據(jù)。若對(duì)Name列進(jìn)行條件搜索，則需要兩個(gè)步驟：第一步在輔助索引B+樹(shù)中檢索Name，到達(dá)其葉子節(jié)點(diǎn)獲取對(duì)應(yīng)的主鍵。第二步使用主鍵在主索引B+樹(shù)種再執(zhí)行一次B+樹(shù)檢索操作，最終到達(dá)葉子節(jié)點(diǎn)即可獲取整行數(shù)據(jù)。

MyISM使用的是非聚簇索引，非聚簇索引的兩棵B+樹(shù)看上去沒(méi)什么不同，節(jié)點(diǎn)的結(jié)構(gòu)完全一致只是存儲(chǔ)的內(nèi)容不同而已，主鍵索引B+樹(shù)的節(jié)點(diǎn)存儲(chǔ)了主鍵，輔助鍵索引B+樹(shù)存儲(chǔ)了輔助鍵。表數(shù)據(jù)存儲(chǔ)在獨(dú)立的地方，這兩顆B+樹(shù)的葉子節(jié)點(diǎn)都使用一個(gè)地址指向真正的表數(shù)據(jù)，對(duì)于表數(shù)據(jù)來(lái)說(shuō)，這兩個(gè)鍵沒(méi)有任何差別。由于索引樹(shù)是獨(dú)立的，通過(guò)輔助鍵檢索無(wú)需訪問(wèn)主鍵的索引樹(shù)。

為了更形象說(shuō)明這兩種索引的區(qū)別，我們假想一個(gè)表如下圖存儲(chǔ)了4行數(shù)據(jù)。其中Id作為主索引，Name作為輔助索引。圖示清晰的顯示了聚簇索引和非聚簇索引的差異。

我們重點(diǎn)關(guān)注聚簇索引，看上去聚簇索引的效率明顯要低于非聚簇索引，因?yàn)槊看问褂幂o助索引檢索都要經(jīng)過(guò)兩次B+樹(shù)查找，這不是多此一舉嗎？聚簇索引的優(yōu)勢(shì)在哪？

1 由于行數(shù)據(jù)和葉子節(jié)點(diǎn)存儲(chǔ)在一起，這樣主鍵和行數(shù)據(jù)是一起被載入內(nèi)存的，找到葉子節(jié)點(diǎn)就可以立刻將行數(shù)據(jù)返回了，如果按照主鍵Id來(lái)組織數(shù)據(jù)，獲得數(shù)據(jù)更快。

2 輔助索引使用主鍵作為"指針" 而不是使用地址值作為指針的好處是，減少了當(dāng)出現(xiàn)行移動(dòng)或者數(shù)據(jù)頁(yè)分裂時(shí)輔助索引的維護(hù)工作，使用主鍵值當(dāng)作指針會(huì)讓輔助索引占用更多的空間，換來(lái)的好處是InnoDB在移動(dòng)行時(shí)無(wú)須更新輔助索引中的這個(gè)"指針"。也就是說(shuō)行的位置（實(shí)現(xiàn)中通過(guò)16K的Page來(lái)定位，后面會(huì)涉及）會(huì)隨著數(shù)據(jù)庫(kù)里數(shù)據(jù)的修改而發(fā)生變化（前面的B+樹(shù)節(jié)點(diǎn)分裂以及Page的分裂），使用聚簇索引就可以保證不管這個(gè)主鍵B+樹(shù)的節(jié)點(diǎn)如何變化，輔助索引樹(shù)都不受影響。

如果說(shuō)前面的內(nèi)容偏向于解釋原理，那后面就開(kāi)始涉及具體實(shí)現(xiàn)了。

理解InnoDB的實(shí)現(xiàn)不得不提Page結(jié)構(gòu)，Page是整個(gè)InnoDB存儲(chǔ)的最基本構(gòu)件，也是InnoDB磁盤(pán)管理的最小單位，與數(shù)據(jù)庫(kù)相關(guān)的所有內(nèi)容都存儲(chǔ)在這種Page結(jié)構(gòu)里。Page分為幾種類型，常見(jiàn)的頁(yè)類型有數(shù)據(jù)頁(yè)（B-tree Node）Undo頁(yè)（Undo Log Page）系統(tǒng)頁(yè)（System Page） 事務(wù)數(shù)據(jù)頁(yè)（Transaction System Page）等。單個(gè)Page的大小是16K（編譯宏UNIV_PAGE_SIZE控制），每個(gè)Page使用一個(gè)32位的int值來(lái)唯一標(biāo)識(shí)，這也正好對(duì)應(yīng)InnoDB最大64TB的存儲(chǔ)容量（16Kib * 2^32 = 64Tib）。一個(gè)Page的基本結(jié)構(gòu)如下圖所示：

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

我們重點(diǎn)關(guān)注和數(shù)據(jù)組織結(jié)構(gòu)相關(guān)的字段：Page的頭部保存了兩個(gè)指針，分別指向前一個(gè)Page和后一個(gè)Page，頭部還有Page的類型信息和用來(lái)唯一標(biāo)識(shí)Page的編號(hào)。根據(jù)這兩個(gè)指針我們很容易想象出Page鏈接起來(lái)就是一個(gè)雙向鏈表的結(jié)構(gòu)。

再看看Page的主體內(nèi)容，我們主要關(guān)注行數(shù)據(jù)和索引的存儲(chǔ)，他們都位于Page的User Records部分，User Records占據(jù)Page的大部分空間，User Records由一條一條的Record組成，每條記錄代表索引樹(shù)上的一個(gè)節(jié)點(diǎn)（非葉子節(jié)點(diǎn)和葉子節(jié)點(diǎn)）。在一個(gè)Page內(nèi)部，單鏈表的頭尾由固定內(nèi)容的兩條記錄來(lái)表示，字符串形式的"Infimum"代表開(kāi)頭，"Supremum"代表結(jié)尾。這兩個(gè)用來(lái)代表開(kāi)頭結(jié)尾的Record存儲(chǔ)在System Records的段里，這個(gè)System Records和User Records是兩個(gè)平行的段。InnoDB存在4種不同的Record，它們分別是1主鍵索引樹(shù)非葉節(jié)點(diǎn) 2主鍵索引樹(shù)葉子節(jié)點(diǎn) 3輔助鍵索引樹(shù)非葉節(jié)點(diǎn) 4輔助鍵索引樹(shù)葉子節(jié)點(diǎn)。這4種節(jié)點(diǎn)的Record格式有一些差異，但是它們都存儲(chǔ)著Next指針指向下一個(gè)Record。后續(xù)我們會(huì)詳細(xì)介紹這4種節(jié)點(diǎn)，現(xiàn)在只需要把Record當(dāng)成一個(gè)存儲(chǔ)了數(shù)據(jù)同時(shí)含有Next指針的單鏈表節(jié)點(diǎn)即可。

User Record在Page內(nèi)以單鏈表的形式存在，最初數(shù)據(jù)是按照插入的先后順序排列的，但是隨著新數(shù)據(jù)的插入和舊數(shù)據(jù)的刪除，數(shù)據(jù)物理順序會(huì)變得混亂，但他們依然保持著邏輯上的先后順序。

把User Record的組織形式和若干Page組合起來(lái)，就看到了稍微完整的形式。

現(xiàn)在看下如何定位一個(gè)Record：

1 通過(guò)根節(jié)點(diǎn)開(kāi)始遍歷一個(gè)索引的B+樹(shù)，通過(guò)各層非葉子節(jié)點(diǎn)最終到達(dá)一個(gè)Page，這個(gè)Page里存放的都是葉子節(jié)點(diǎn)。

2 在Page內(nèi)從"Infimum"節(jié)點(diǎn)開(kāi)始遍歷單鏈表（這種遍歷往往會(huì)被優(yōu)化），如果找到該鍵則成功返回。如果記錄到達(dá)了"supremum"，說(shuō)明當(dāng)前Page里沒(méi)有合適的鍵，這時(shí)要借助Page的Next Page指針，跳轉(zhuǎn)到下一個(gè)Page繼續(xù)從"Infimum"開(kāi)始逐個(gè)查找。

詳細(xì)看下不同類型的Record里到底存儲(chǔ)了什么數(shù)據(jù)，根據(jù)B+樹(shù)節(jié)點(diǎn)的不同，User Record可以被分成四種格式，下圖種按照顏色予以區(qū)分。

1 主索引樹(shù)非葉節(jié)點(diǎn)（綠色）

1 子節(jié)點(diǎn)存儲(chǔ)的主鍵里最小的值（Min Cluster Key on Child），這是B+樹(shù)必須的，作用是在一個(gè)Page里定位到具體的記錄的位置。

2 最小的值所在的Page的編號(hào)（Child Page Number），作用是定位Record。

2 主索引樹(shù)葉子節(jié)點(diǎn)（黃色）

1 主鍵（Cluster Key Fields），B+樹(shù)必須的，也是數(shù)據(jù)行的一部分

2 除去主鍵以外的所有列（Non-Key Fields），這是數(shù)據(jù)行的除去主鍵的其他所有列的集合。

這里的1和2兩部分加起來(lái)就是一個(gè)完整的數(shù)據(jù)行。

3 輔助索引樹(shù)非葉節(jié)點(diǎn)非（藍(lán)色）

1 子節(jié)點(diǎn)里存儲(chǔ)的輔助鍵值里的最小的值（Min Secondary-Key on Child），這是B+樹(shù)必須的，作用是在一個(gè)Page里定位到具體的記錄的位置。

2 主鍵值（Cluster Key Fields），非葉子節(jié)點(diǎn)為什么要存儲(chǔ)主鍵呢？因?yàn)檩o助索引是可以不唯一的，但是B+樹(shù)要求鍵的值必須唯一，所以這里把輔助鍵的值和主鍵的值合并起來(lái)作為在B+樹(shù)中的真正鍵值，保證了唯一性。但是這也導(dǎo)致在輔助索引B+樹(shù)中非葉節(jié)點(diǎn)反而比葉子節(jié)點(diǎn)多了4個(gè)字節(jié)。（即下圖中藍(lán)色節(jié)點(diǎn)反而比紅色多了4字節(jié)）

3 最小的值所在的Page的編號(hào)（Child Page Number），作用是定位Record。

4 輔助索引樹(shù)葉子節(jié)點(diǎn)（紅色）

1 輔助索引鍵值（Secondary Key Fields），這是B+樹(shù)必須的。

2 主鍵值（Cluster Key Fields），用來(lái)在主索引樹(shù)里再做一次B+樹(shù)檢索來(lái)找到整條記錄。

下面是本篇最重要的部分了，結(jié)合B+樹(shù)的結(jié)構(gòu)和前面介紹的4種Record的內(nèi)容，我們終于可以畫(huà)出一幅全景圖。由于輔助索引的B+樹(shù)與主鍵索引有相似的結(jié)構(gòu)，這里只畫(huà)出了主鍵索引樹(shù)的結(jié)構(gòu)圖，只包含了"主鍵非葉節(jié)點(diǎn)"和"主鍵葉子節(jié)點(diǎn)"兩種節(jié)點(diǎn)，也就是上圖的的綠色和黃色的部分。

把上圖還原成下面這個(gè)更簡(jiǎn)潔的樹(shù)形示意圖，這就是B+樹(shù)的一部分。注意Page和B+樹(shù)節(jié)點(diǎn)之間并沒(méi)有一一對(duì)應(yīng)的關(guān)系，Page只是作為一個(gè)Record的保存容器，它存在的目的是便于對(duì)磁盤(pán)空間進(jìn)行批量管理，上圖中的編號(hào)為47的Page在樹(shù)形結(jié)構(gòu)上就被拆分成了兩個(gè)獨(dú)立節(jié)點(diǎn)。

至此本篇就算結(jié)束了，本篇只是對(duì)InnoDB索引相關(guān)的數(shù)據(jù)結(jié)構(gòu)和實(shí)現(xiàn)進(jìn)行了一些梳理總結(jié)，并未涉及到Mysql的實(shí)戰(zhàn)經(jīng)驗(yàn)。這主要是基于幾點(diǎn)原因：

1 原理是基石，只有充分了解InnoDB索引的工作方式，我們才有能力高效的使用好它。

2 原理性知識(shí)特別適合使用圖示，我個(gè)人非常喜歡這種表達(dá)方式。

3 關(guān)于InnoDB優(yōu)化，在《高性能Mysql》里有更加全面的介紹，對(duì)優(yōu)化Mysql感興趣的同學(xué)完全可以自己獲取相關(guān)知識(shí)，我自己的積累還未達(dá)到能分享這些內(nèi)容的地步。

另：對(duì)InnoDB實(shí)現(xiàn)有更多興趣的同學(xué)可以看看Jeremy Cole的博客（參考文獻(xiàn)三篇文章的來(lái)源），這位老兄曾先后在Mysql，Yahoo，Twitter，Google從事數(shù)據(jù)庫(kù)相關(guān)工作，他的文章非常棒！