InnoDB數(shù)據(jù)頁的7個組成部分，知道了各個數(shù)據(jù)頁可以組成一個雙向鏈表，而每個數(shù)據(jù)頁中的記錄會按照主鍵值從小到大的順序組成一個單向鏈表，每個數(shù)據(jù)頁都會為存儲在它里邊兒的記錄生成一個頁目錄，在通過主鍵查找某條記錄的時候可以在頁目錄中使用二分法快速定位到對應的槽，然后再遍歷該槽對應分組中的記錄即可快速找到指定的記錄（如果你對這段話有一丁點兒疑惑，那么接下來的部分不適合你，返回去看一下數(shù)據(jù)頁結構吧）。頁和記錄的關系示意圖如下：

其中頁a、頁b、頁c ... 頁n 這些頁可以不在物理結構上相連，只要通過雙向鏈表相關聯(lián)即可。

沒有索引的查找

本集的主題是索引，在正式介紹索引之前，我們需要了解一下沒有索引的時候是怎么查找記錄的。為了方便大家理解，我們下邊先只嘮叨搜索條件為對某個列精確匹配的情況，所謂精確匹配，就是搜索條件中用等于=連接起的表達式，比如這樣：

SELECT [列名列表] FROM 表名 WHERE 列名 = xxx;

在一個頁中的查找

假設目前表中的記錄比較少，所有的記錄都可以被存放到一個頁中，在查找記錄的時候可以根據(jù)搜索條件的不同分為兩種情況：

以主鍵為搜索條件

這個查找過程我們已經(jīng)很熟悉了，可以在頁目錄中使用二分法快速定位到對應的槽，然后再遍歷該槽對應分組中的記錄即可快速找到指定的記錄。

以其他列作為搜索條件

對非主鍵列的查找的過程可就不這么幸運了，因為在數(shù)據(jù)頁中并沒有對非主鍵列建立所謂的頁目錄，所以我們無法通過二分法快速定位相應的槽。這種情況下只能從最小記錄開始依次遍歷單鏈表中的每條記錄，然后對比每條記錄是不是符合搜索條件。很顯然，這種查找的效率是非常低的。

在很多頁中查找

大部分情況下我們表中存放的記錄都是非常多的，需要好多的數(shù)據(jù)頁來存儲這些記錄。在很多頁中查找記錄的話可以分為兩個步驟：

定位到記錄所在的頁。

從所在的頁內(nèi)中查找相應的記錄。

在沒有索引的情況下，不論是根據(jù)主鍵列或者其他列的值進行查找，由于我們并不能快速的定位到記錄所在的頁，所以只能從第一個頁沿著雙向鏈表一直往下找，在每一個頁中根據(jù)我們剛剛嘮叨過的查找方式去查找指定的記錄。因為要遍歷所有的數(shù)據(jù)頁，所以這種方式顯然是超級耗時的，如果一個表有一億條記錄，使用這種方式去查找記錄那要等到猴年馬月才能等到查找結果。所以祖國和人民都在期盼一種能高效完成搜索的方法，索引同志就要亮相登臺了。

索引

為了故事的順利發(fā)展，我們先建一個表：

mysql> CREATE TABLE index_demo(

? ? ->? ? c1 INT,

? ? ->? ? c2 INT,

? ? ->? ? c3 CHAR(1),

? ? ->? ? PRIMARY KEY(c1)

? ? -> ) ROW_FORMAT = Compact;

Query OK, 0 rows affected (0.03 sec)

這個新建的index_demo表中有2個INT類型的列，1個CHAR(1)類型的列，而且我們規(guī)定了c1列為主鍵，這個表使用Compact行格式來實際存儲記錄的。為了我們理解上的方便，我們簡化了一下index_demo表的行格式示意圖：

我們只在示意圖里展示記錄的這幾個部分：

record_type：記錄頭信息的一項屬性，表示記錄的類型，0表示普通記錄、2表示最小記錄、3表示最大記錄、1我們還沒用過，等會再說～

next_record：記錄頭信息的一項屬性，表示下一條地址相對于本條記錄的地址偏移量，為了方便大家理解，我們都會用箭頭來表明下一條記錄是誰。

各個列的值：這里只記錄在index_demo表中的三個列，分別是c1、c2和c3。

其他信息：除了上述3種信息以外的所有信息，包括其他隱藏列的值以及記錄的額外信息。

為了節(jié)省篇幅，我們之后的示意圖中會把記錄的其他信息這個部分省略掉，因為它占地方并且不會有什么觀賞效果。另外，為了方便理解，我們覺得把記錄豎著放看起來感覺更好，所以將記錄格式示意圖的其他信息去掉并把它豎起來的效果就是這樣：

把一些記錄放到頁里邊的示意圖就是：

一個簡單的索引方案

回到正題，我們在根據(jù)某個搜索條件查找一些記錄時為什么要遍歷所有的數(shù)據(jù)頁呢？因為各個頁中的記錄并沒有規(guī)律，我們并不知道我們的搜索條件匹配哪些頁中的記錄，所以?不得不?依次遍歷所有的數(shù)據(jù)頁。所以如果我們想快速的定位到需要查找的記錄在哪些數(shù)據(jù)頁中該咋辦？還記得我們?yōu)楦鶕?jù)主鍵值快速定位一條記錄在頁中的位置而設立的頁目錄么？我們也可以想辦法為快速定位記錄所在的數(shù)據(jù)頁而建立一個別的目錄，建這個目錄必須完成下邊這些事兒：

下一個數(shù)據(jù)頁中用戶記錄的主鍵值必須大于上一個頁中用戶記錄的主鍵值。

為了故事的順利發(fā)展，我們這里需要做一個假設：假設我們的每個數(shù)據(jù)頁最多能存放3條記錄（實際上一個數(shù)據(jù)頁非常大，可以存放下好多記錄）。有了這個假設之后我們向index_demo表插入3條記錄：

mysql> INSERT INTO index_demo VALUES(1, 4,'u'), (3, 9,'d'), (5, 3,'y');Query OK, 3 rows affected (0.01 sec)Records: 3? Duplicates: 0? Warnings: 0

那么這些記錄已經(jīng)按照主鍵值的大小串聯(lián)成一個單向鏈表了，如圖所示：

從圖中可以看出來，index_demo表中的3條記錄都被插入到了編號為10的數(shù)據(jù)頁中了。此時我們再來插入一條記錄：

mysql> INSERT INTO index_demo VALUES(4, 4,'a');Query OK, 1 row affected (0.00 sec)

因為頁10最多只能放3條記錄，所以我們不得不再分配一個新頁：

咦？怎么分配的頁號是28呀，不應該是11么？再次強調(diào)一遍，新分配的數(shù)據(jù)頁編號可能并不是連續(xù)的，也就是說我們使用的這些頁在存儲空間里可能并不挨著。它們只是通過維護著上一個頁和下一個頁的編號而建立了鏈表關系。另外，頁10中用戶記錄最大的主鍵值是5，而頁28中有一條記錄的主鍵值是4，因為5 > 4，所以這就不符合下一個數(shù)據(jù)頁中用戶記錄的主鍵值必須大于上一個頁中用戶記錄的主鍵值的要求，所以在插入主鍵值為4的記錄的時候需要伴隨著一次記錄移動，也就是把主鍵值為5的記錄移動到頁28中，然后再把主鍵值為4的記錄插入到頁10中，這個過程的示意圖如下：

這個過程表明了在對頁中的記錄進行增刪改操作的過程中，我們必須通過一些諸如記錄移動的操作來始終保證這個狀態(tài)一直成立：下一個數(shù)據(jù)頁中用戶記錄的主鍵值必須大于上一個頁中用戶記錄的主鍵值。這個過程我們也可以稱為頁分裂。

給所有的頁建立一個目錄項。

由于數(shù)據(jù)頁的編號可能并不是連續(xù)的，所以在向index_demo表中插入許多條記錄后，可能是這樣的效果：

因為這些16KB的頁在物理存儲上可能并不挨著，所以如果想從這么多頁中根據(jù)主鍵值快速定位某些記錄所在的頁，我們需要給它們做個目錄，每個頁對應一個目錄項，每個目錄項包括下邊兩個部分：

頁的用戶記錄中最小的主鍵值，我們用key來表示。

頁號，我們用page_no表示。

所以我們?yōu)樯线厧讉€頁做好的目錄就像這樣子：

以頁28為例，它對應目錄項2，這個目錄項中包含著該頁的頁號28以及該頁中用戶記錄的最小主鍵值5。我們只需要把幾個目錄項在物理存儲器上連續(xù)存儲，比如把他們放到一個數(shù)組里，就可以實現(xiàn)根據(jù)主鍵值快速查找某條記錄的功能了。比方說我們想找主鍵值為20的記錄，具體查找過程分兩步：

先從目錄項中根據(jù)二分法快速確定出主鍵值為20的記錄在目錄項3中（因為?12 < 20 < 209），它對應的頁是頁9。

再根據(jù)前邊說的在頁中查找記錄的方式去頁9中定位具體的記錄。

至此，針對數(shù)據(jù)頁做的簡易目錄就搞定了。不過忘了說了，這個目錄有一個別名，稱為索引。

InnoDB中的索引方案

上邊之所以稱為一個簡易的索引方案，是因為我們?yōu)榱嗽诟鶕?jù)主鍵值進行查找時使用二分法快速定位具體的目錄項而假設所有目錄項都可以在物理存儲器上連續(xù)存儲，但是這樣做有幾個問題：

InnoDB是使用頁來作為管理存儲空間的基本單位，也就是最多能保證16KB的連續(xù)存儲空間，而隨著表中記錄數(shù)量的增多，需要非常大的連續(xù)的存儲空間才能把所有的目錄項都放下，這對記錄數(shù)量非常多的表是不現(xiàn)實的。

我們時常會對記錄進行增刪，假設我們把頁28中的記錄都刪除了，頁28也就沒有存在的必要了，那意味著目錄項2也就沒有存在的必要了，這就需要把目錄項2后的目錄項都向前移動一下，這種牽一發(fā)而動全身的設計不是什么好主意～

所以，設計InnoDB的大叔們需要一種可以靈活管理所有目錄項的方式。他們靈光乍現(xiàn)，忽然發(fā)現(xiàn)這些目錄項其實長得跟我們的用戶記錄差不多，只不過目錄項中的兩個列是主鍵和頁號而已，所以他們復用了之前存儲用戶記錄的數(shù)據(jù)頁來存儲目錄項，為了和用戶記錄做一下區(qū)分，我們把這些用來表示目錄項的記錄稱為目錄項記錄。那InnoDB怎么區(qū)分一條記錄是普通的用戶記錄還是目錄項記錄呢？別忘了記錄頭信息里的record_type屬性，它的各個取值代表的意思如下：

0：普通的用戶記錄

1：目錄項記錄

2：最小記錄

3：最大記錄

哈哈，原來這個值為1的record_type是這個意思呀，我們把前邊使用到的目錄項放到數(shù)據(jù)頁中的樣子就是這樣：

從圖中可以看出來，我們新分配了一個編號為30的頁來專門存儲目錄項記錄。這里再次強調(diào)一遍目錄項記錄和普通的用戶記錄的不同點：

目錄項記錄的record_type值是1，而普通用戶記錄的record_type值是0。

目錄項記錄只有主鍵值和頁的編號兩個列，而普通的用戶記錄的列是用戶自己定義的，可能包含很多列，另外還有InnoDB自己添加的隱藏列。

還記得我們之前在嘮叨記錄頭信息的時候說過一個叫min_rec_mask的屬性么，只有在存儲目錄項記錄的頁中的主鍵值最小的目錄項記錄的min_rec_mask值為1，其他別的記錄的min_rec_mask值都是0。

除了上述幾點外，這兩者就沒啥差別了，它們用的是一樣的數(shù)據(jù)頁（頁面類型都是0x45BF，這個屬性在File Header中，忘了的話可以翻到前邊的文章看），頁的組成結構也是一樣一樣的（就是我們前邊介紹過的7個部分），都會為主鍵值生成Page Directory（頁目錄），從而在按照主鍵值進行查找時可以使用二分法來加快查詢速度?，F(xiàn)在以查找主鍵為20的記錄為例，根據(jù)某個主鍵值去查找記錄的步驟就可以大致拆分成下邊兩步：

先到存儲目錄項記錄的頁，也就是頁30中通過二分法快速定位到對應目錄項，因為12 < 20 < 209，所以定位到對應的記錄所在的頁就是頁9。

再到存儲用戶記錄的頁9中根據(jù)二分法快速定位到主鍵值為20的用戶記錄。

雖然說目錄項記錄中只存儲主鍵值和對應的頁號，比用戶記錄需要的存儲空間小多了，但是不論怎么說一個頁只有16KB大小，能存放的目錄項記錄也是有限的，那如果表中的數(shù)據(jù)太多，以至于一個數(shù)據(jù)頁不足以存放所有的目錄項記錄，該咋辦呢？

當然是再多整一個存儲目錄項記錄的頁嘍～ 為了大家更好的理解新分配一個目錄項記錄頁的過程，我們假設一個存儲目錄項記錄的頁最多只能存放4條目錄項記錄（請注意是假設哦，真實情況下可以存放好多條的），所以如果此時我們再向上圖中插入一條主鍵值為320的用戶記錄的話，那就需要分配一個新的存儲目錄項記錄的頁嘍：

從圖中可以看出，我們插入了一條主鍵值為320的用戶記錄之后需要兩個新的數(shù)據(jù)頁：

為存儲該用戶記錄而新生成了頁31。

因為原先存儲目錄項記錄的頁30的容量已滿（我們前邊假設只能存儲4條目錄項記錄），所以不得不需要一個新的頁32來存放頁31對應的目錄項。

現(xiàn)在因為存儲目錄項記錄的頁不止一個，所以如果我們想根據(jù)主鍵值查找一條用戶記錄大致需要3個步驟，以查找主鍵值為20的記錄為例：

確定目錄項記錄頁

我們現(xiàn)在的存儲目錄項記錄的頁有兩個，即頁30和頁32，又因為頁30表示的目錄項的主鍵值的范圍是[1, 320)，頁32表示的目錄項的主鍵值不小于320，所以主鍵值為20的記錄對應的目錄項記錄在頁30中。

通過目錄項記錄頁確定用戶記錄真實所在的頁。

在一個存儲目錄項記錄的頁中通過主鍵值定位一條目錄項記錄的方式說過了，不贅述了～

在真實存儲用戶記錄的頁中定位到具體的記錄。

在一個存儲用戶記錄的頁中通過主鍵值定位一條用戶記錄的方式已經(jīng)說過200遍了，你再不會我就，我就，我就求你到上一篇嘮叨數(shù)據(jù)頁結構的文章中多看幾遍，求你了～

那么問題來了，在這個查詢步驟的第1步中我們需要定位存儲目錄項記錄的頁，但是這些頁在存儲空間中也可能不挨著，如果我們表中的數(shù)據(jù)非常多則會產(chǎn)生很多存儲目錄項記錄的頁，那我們怎么根據(jù)主鍵值快速定位一個存儲目錄項記錄的頁呢？其實也簡單，為這些存儲目錄項記錄的頁再生成一個更高級的目錄，就像是一個多級目錄一樣，大目錄里嵌套小目錄，小目錄里才是實際的數(shù)據(jù)，所以現(xiàn)在各個頁的示意圖就是這樣子：

如圖，我們生成了一個存儲更高級目錄項的頁33，這個頁中的兩條記錄分別代表頁30和頁32，如果用戶記錄的主鍵值在[1, 320)之間，則到頁30中查找更詳細的目錄項記錄，如果主鍵值不小于320的話，就到頁32中查找更詳細的目錄項記錄。不過這張圖好漂亮喔，隨著表中記錄的增加，這個目錄的層級會繼續(xù)增加，如果簡化一下，那么我們可以用下邊這個圖來描述它：

這玩意兒像不像一個倒過來的樹呀，上頭是樹根，下頭是樹葉！其實這是一種組織數(shù)據(jù)的形式，或者說是一種數(shù)據(jù)結構，它的名稱是B+樹。

小貼士： 為啥叫`B+`呢，`B`樹是個啥？喔對不起，這不是我們討論的范圍，你可以去找一本數(shù)據(jù)結構或算法的書來看。什么？數(shù)據(jù)結構的書看不懂？等我～

不論是存放用戶記錄的數(shù)據(jù)頁，還是存放目錄項記錄的數(shù)據(jù)頁，我們都把它們存放到B+樹這個數(shù)據(jù)結構中了，所以我們也稱這些數(shù)據(jù)頁為節(jié)點。從圖中可以看出來，我們的實際用戶記錄其實都存放在B+樹的最底層的節(jié)點上，這些節(jié)點也被稱為葉子節(jié)點或葉節(jié)點，其余用來存放目錄項的節(jié)點稱為非葉子節(jié)點或者內(nèi)節(jié)點，其中B+樹最上邊的那個節(jié)點也稱為根節(jié)點。

從圖中可以看出來，一個B+樹的節(jié)點其實可以分成好多層，設計InnoDB的大叔們?yōu)榱擞懻摲奖悖?guī)定最下邊的那層，也就是存放我們用戶記錄的那層為第0層，之后依次往上加。之前的討論我們做了一個非常極端的假設：存放用戶記錄的頁最多存放3條記錄，存放目錄項記錄的頁最多存放4條記錄。其實真實環(huán)境中一個頁存放的記錄數(shù)量是非常大的，假設，假設，假設所有存放用戶記錄的葉子節(jié)點代表的數(shù)據(jù)頁可以存放100條用戶記錄，所有存放目錄項記錄的內(nèi)節(jié)點代表的數(shù)據(jù)頁可以存放1000條目錄項記錄，那么：

如果B+樹只有1層，也就是只有1個用于存放用戶記錄的節(jié)點，最多能存放100條記錄。

如果B+樹有2層，最多能存放1000×100=100000條記錄。

如果B+樹有3層，最多能存放1000×1000×100=100000000條記錄。

如果B+樹有4層，最多能存放1000×1000×1000×100=100000000000條記錄。哇咔咔～這么多的記錄?。?！

你的表里能存放100000000000條記錄么？所以一般情況下，我們用到的B+樹都不會超過4層，那我們通過主鍵值去查找某條記錄最多只需要做4個頁面內(nèi)的查找（查找3個目錄項頁和一個用戶記錄頁），又因為在每個頁面內(nèi)有所謂的Page Directory（頁目錄），所以在頁面內(nèi)也可以通過二分法實現(xiàn)快速定位記錄，這不是很牛么，哈哈！

聚簇索引

我們上邊介紹的B+樹本身就是一個目錄，或者說本身就是一個索引。它有兩個特點：

使用記錄主鍵值的大小進行記錄和頁的排序，這包括三個方面的含義：

頁內(nèi)的記錄是按照主鍵的大小順序排成一個單向鏈表。

各個存放用戶記錄的頁也是根據(jù)頁中用戶記錄的主鍵大小順序排成一個雙向鏈表。

存放目錄項記錄的頁分為不同的層次，在同一層次中的頁也是根據(jù)頁中目錄項記錄的主鍵大小順序排成一個雙向鏈表。

B+樹的葉子節(jié)點存儲的是完整的用戶記錄。

所謂完整的用戶記錄，就是指這個記錄中存儲了所有列的值（包括隱藏列）。

我們把具有這兩種特性的B+樹稱為聚簇索引，所有完整的用戶記錄都存放在這個聚簇索引的葉子節(jié)點處。這種聚簇索引并不需要我們在MySQL語句中顯式的使用INDEX語句去創(chuàng)建（后邊會介紹索引相關的語句），InnoDB存儲引擎會自動的為我們創(chuàng)建聚簇索引。另外有趣的一點是，在InnoDB存儲引擎中，聚簇索引就是數(shù)據(jù)的存儲方式（所有的用戶記錄都存儲在了葉子節(jié)點），也就是所謂的索引即數(shù)據(jù)，數(shù)據(jù)即索引。

二級索引

大家有木有發(fā)現(xiàn)，上邊介紹的聚簇索引只能在搜索條件是主鍵值時才能發(fā)揮作用，因為B+樹中的數(shù)據(jù)都是按照主鍵進行排序的。那如果我們想以別的列作為搜索條件該咋辦呢？難道只能從頭到尾沿著鏈表依次遍歷記錄么？

不，我們可以多建幾棵B+樹，不同的B+樹中的數(shù)據(jù)采用不同的排序規(guī)則。比方說我們用c2列的大小作為數(shù)據(jù)頁、頁中記錄的排序規(guī)則，再建一棵B+樹，效果如下圖所示：

這個B+樹與上邊介紹的聚簇索引有幾處不同：

使用記錄c2列的大小進行記錄和頁的排序，這包括三個方面的含義：

頁內(nèi)的記錄是按照c2列的大小順序排成一個單向鏈表。

各個存放用戶記錄的頁也是根據(jù)頁中記錄的c2列大小順序排成一個雙向鏈表。

存放目錄項記錄的頁分為不同的層次，在同一層次中的頁也是根據(jù)頁中目錄項記錄的c2列大小順序排成一個雙向鏈表。

B+樹的葉子節(jié)點存儲的并不是完整的用戶記錄，而只是c2列+主鍵這兩個列的值。

目錄項記錄中不再是主鍵+頁號的搭配，而變成了c2列+頁號的搭配。

所以如果我們現(xiàn)在想通過c2列的值查找某些記錄的話就可以使用我們剛剛建好的這個B+樹了。以查找c2列的值為4的記錄為例，查找過程如下：

確定目錄項記錄頁

根據(jù)根頁面，也就是頁44，可以快速定位到目錄項記錄所在的頁為頁42（因為2 < 4 < 9）。

通過目錄項記錄頁確定用戶記錄真實所在的頁。

在頁42中可以快速定位到實際存儲用戶記錄的頁，但是由于c2列并沒有唯一性約束，所以c2列值為4的記錄可能分布在多個數(shù)據(jù)頁中，又因為2 < 4 ≤ 4，所以確定實際存儲用戶記錄的頁在頁34和頁35中。

在真實存儲用戶記錄的頁中定位到具體的記錄。

到頁34和頁35中定位到具體的記錄。

但是這個B+樹的葉子節(jié)點中的記錄只存儲了c2和c1（也就是主鍵）兩個列，所以我們必須再根據(jù)主鍵值去聚簇索引中再查找一遍完整的用戶記錄。

各位各位，看到步驟4的操作了么？我們根據(jù)這個以c2列大小排序的B+樹只能確定我們要查找記錄的主鍵值，所以如果我們想根據(jù)c2列的值查找到完整的用戶記錄的話，仍然需要到聚簇索引中再查一遍，這個過程也被稱為回表。也就是根據(jù)c2列的值查詢一條完整的用戶記錄需要使用到2棵B+樹?。。?/p>

為什么我們還需要一次回表操作呢？直接把完整的用戶記錄放到葉子節(jié)點不就好了么？你說的對，如果把完整的用戶記錄放到葉子節(jié)點是可以不用回表，但是太占地方了呀～相當于每建立一棵B+樹都需要把所有的用戶記錄再都拷貝一遍，這就有點太浪費存儲空間了。因為這種按照非主鍵列建立的B+樹需要一次回表操作才可以定位到完整的用戶記錄，所以這種B+樹也被稱為二級索引（英文名secondary index），或者輔助索引。由于我們使用的是c2列的大小作為B+樹的排序規(guī)則，所以我們也稱這個B+樹為為c2列建立的索引。

聯(lián)合索引

我們也可以同時以多個列的大小作為排序規(guī)則，也就是同時為多個列建立索引，比方說我們想讓B+樹按照c2和c3列的大小進行排序，這個包含兩層含義：

先把各個記錄和頁按照c2列進行排序。

在記錄的c2列相同的情況下，采用c3列進行排序

為c2和c3列建立的索引的示意圖如下：

如圖所示，我們需要注意一下幾點：

每條目錄項記錄都由c2、c3、頁號這三個部分組成，各條記錄先按照c2列的值進行排序，如果記錄的c2列相同，則按照c3列的值進行排序。

B+樹葉子節(jié)點處的用戶記錄由c2、c3和主鍵c1列組成。

千萬要注意一點，以c2和c3列的大小為排序規(guī)則建立的B+樹稱為聯(lián)合索引，本質(zhì)上也是一個二級索引。它的意思與分別為c2和c3列分別建立索引的表述是不同的，不同點如下：

建立聯(lián)合索引只會建立如上圖一樣的1棵B+樹。

為c2和c3列分別建立索引會分別以c2和c3列的大小為排序規(guī)則建立2棵B+樹。

InnoDB的B+樹索引的注意事項

根頁面萬年不動窩

我們前邊介紹B+樹索引的時候，為了大家理解上的方便，先把存儲用戶記錄的葉子節(jié)點都畫出來，然后接著畫存儲目錄項記錄的內(nèi)節(jié)點，實際上B+樹的形成過程是這樣的：

每當為某個表創(chuàng)建一個B+樹索引（聚簇索引不是人為創(chuàng)建的，默認就有）的時候，都會為這個索引創(chuàng)建一個根節(jié)點頁面。最開始表中沒有數(shù)據(jù)的時候，每個B+樹索引對應的根節(jié)點中既沒有用戶記錄，也沒有目錄項記錄。

隨后向表中插入用戶記錄時，先把用戶記錄存儲到這個根節(jié)點中。

當根節(jié)點中的可用空間用完時繼續(xù)插入記錄，此時會將根節(jié)點中的所有記錄復制到一個新分配的頁，比如頁a中，然后對這個新頁進行頁分裂的操作，得到另一個新頁，比如頁b。這時新插入的記錄根據(jù)鍵值（也就是聚簇索引中的主鍵值，二級索引中對應的索引列的值）的大小就會被分配到頁a或者頁b中，而根節(jié)點便升級為存儲目錄項記錄的頁。

這個過程需要大家特別注意的是：一個B+樹索引的根節(jié)點自誕生之日起，便不會再移動。這樣只要我們對某個表建立一個索引，那么它的根節(jié)點的頁號便會被記錄到某個地方，然后凡是InnoDB存儲引擎需要用到這個索引的時候，都會從那個固定的地方取出根節(jié)點的頁號，從而來訪問這個索引。

小貼士： 跟大家劇透一下，這個存儲某個索引的根節(jié)點在哪個頁面中的信息就是傳說中的數(shù)據(jù)字典中的一項信息，關于更多數(shù)據(jù)字典的內(nèi)容，后邊會詳細嘮叨，別著急哈。

內(nèi)節(jié)點中目錄項記錄的唯一性

我們知道B+樹索引的內(nèi)節(jié)點中目錄項記錄的內(nèi)容是索引列 + 頁號的搭配，但是這個搭配對于二級索引來說有點兒不嚴謹。還拿index_demo表為例，假設這個表中的數(shù)據(jù)是這樣的：

c1c2c3

11'u'

31'd'

51'y'

71'a'

如果二級索引中目錄項記錄的內(nèi)容只是索引列 + 頁號的搭配的話，那么為c2列建立索引后的B+樹應該長這樣：

如果我們想新插入一行記錄，其中c1、c2、c3的值分別是：9、1、'c'，那么在修改這個為c2列建立的二級索引對應的B+樹時便碰到了個大問題：由于頁3中存儲的目錄項記錄是由c2列 + 頁號的值構成的，頁3中的兩條目錄項記錄對應的c2列的值都是1，而我們新插入的這條記錄的c2列的值也是1，那我們這條新插入的記錄到底應該放到頁4中，還是應該放到頁5中??？答案是：對不起，懵逼了。

為了讓新插入記錄能找到自己在那個頁里，我們需要保證在B+樹的同一層內(nèi)節(jié)點的目錄項記錄除頁號這個字段以外是唯一的。所以對于二級索引的內(nèi)節(jié)點的目錄項記錄的內(nèi)容實際上是由三個部分構成的：

索引列的值

主鍵值

頁號

也就是我們把主鍵值也添加到二級索引內(nèi)節(jié)點中的目錄項記錄了，這樣就能保證B+樹每一層節(jié)點中各條目錄項記錄除頁號這個字段外是唯一的，所以我們?yōu)閏2列建立二級索引后的示意圖實際上應該是這樣子的：

這樣我們再插入記錄(9, 1, 'c')時，由于頁3中存儲的目錄項記錄是由c2列 + 主鍵 + 頁號的值構成的，可以先把新記錄的c2列的值和頁3中各目錄項記錄的c2列的值作比較，如果c2列的值相同的話，可以接著比較主鍵值，因為B+樹同一層中不同目錄項記錄的c2列 + 主鍵的值肯定是不一樣的，所以最后肯定能定位唯一的一條目錄項記錄，在本例中最后確定新記錄應該被插入到頁5中。

一個頁面最少存儲2條記錄

我們前邊說過一個B+樹只需要很少的層級就可以輕松存儲數(shù)億條記錄，查詢速度杠杠的！這是因為B+樹本質(zhì)上就是一個大的多層級目錄，每經(jīng)過一個目錄時都會過濾掉許多無效的子目錄，直到最后訪問到存儲真實數(shù)據(jù)的目錄。那如果一個大的目錄中只存放一個子目錄是個啥效果呢？那就是目錄層級非常非常非常多，而且最后的那個存放真實數(shù)據(jù)的目錄中只能存放一條記錄。費了半天勁只能存放一條真實的用戶記錄？逗我呢？所以InnoDB的一個數(shù)據(jù)頁至少可以存放兩條記錄，這也是我們之前嘮叨記錄行格式的時候說過一個結論（我們當時依據(jù)這個結論推導了表中只有一個列時該列在不發(fā)生行溢出的情況下最多能存儲多少字節(jié)，忘了的話回去看看吧）。

MyISAM中的索引方案簡單介紹

至此，我們介紹的都是InnoDB存儲引擎中的索引方案，為了內(nèi)容的完整性，以及各位可能在面試的時候遇到這類的問題，我們有必要再簡單介紹一下MyISAM存儲引擎中的索引方案。我們知道InnoDB中索引即數(shù)據(jù)，也就是聚簇索引的那棵B+樹的葉子節(jié)點中已經(jīng)把所有完整的用戶記錄都包含了，而MyISAM的索引方案雖然也使用樹形結構，但是卻將索引和數(shù)據(jù)分開存儲：

將表中的記錄按照記錄的插入順序單獨存儲在一個文件中，稱之為數(shù)據(jù)文件。這個文件并不劃分為若干個數(shù)據(jù)頁，有多少記錄就往這個文件中塞多少記錄就成了。我們可以通過行號而快速訪問到一條記錄。

MyISAM記錄也需要記錄頭信息來存儲一些額外數(shù)據(jù)，我們以上邊嘮叨過的index_demo表為例，看一下這個表中的記錄使用MyISAM作為存儲引擎在存儲空間中的表示：

由于在插入數(shù)據(jù)的時候并沒有刻意按照主鍵大小排序，所以我們并不能在這些數(shù)據(jù)上使用二分法進行查找。

使用MyISAM存儲引擎的表會把索引信息另外存儲到一個稱為索引文件的另一個文件中。MyISAM會單獨為表的主鍵創(chuàng)建一個索引，只不過在索引的葉子節(jié)點中存儲的不是完整的用戶記錄，而是主鍵值 + 行號的組合。也就是先通過索引找到對應的行號，再通過行號去找對應的記錄！

這一點和InnoDB是完全不相同的，在InnoDB存儲引擎中，我們只需要根據(jù)主鍵值對聚簇索引進行一次查找就能找到對應的記錄，而在MyISAM中卻需要進行一次回表操作，意味著MyISAM中建立的索引相當于全部都是二級索引！

如果有需要的話，我們也可以對其它的列分別建立索引或者建立聯(lián)合索引，原理和InnoDB中的索引差不多，不過在葉子節(jié)點處存儲的是相應的列 + 行號。這些索引也全部都是二級索引。

小貼士： MyISAM的行格式有定長記錄格式（Static）、變長記錄格式（Dynamic）、壓縮記錄格式（Compressed）。上邊用到的index_demo表采用定長記錄格式，也就是一條記錄占用存儲空間的大小是固定的，這樣就可以輕松算出某條記錄在數(shù)據(jù)文件中的地址偏移量。但是變長記錄格式就不行了，MyISAM會直接在索引葉子節(jié)點處存儲該條記錄在數(shù)據(jù)文件中的地址偏移量。通過這個可以看出，MyISAM的回表操作是十分快速的，因為是拿著地址偏移量直接到文件中取數(shù)據(jù)的，反觀InnoDB是通過獲取主鍵之后再去聚簇索引里邊兒找記錄，雖然說也不慢，但還是比不上直接用地址去訪問。 此處我們只是非常簡要的介紹了一下MyISAM的索引，具體細節(jié)全拿出來又可以寫一篇文章了。這里只是希望大家理解InnoDB中的索引即數(shù)據(jù)，數(shù)據(jù)即索引，而MyISAM中卻是索引是索引、數(shù)據(jù)是數(shù)據(jù)。

MySQL中創(chuàng)建和刪除索引的語句

光顧著嘮叨索引的原理了，那我們?nèi)绾问褂肕ySQL語句去建立這種索引呢？InnoDB和MyISAM會自動為主鍵或者聲明為UNIQUE的列去自動建立B+樹索引，但是如果我們想為其他的列建立索引就需要我們顯式的去指明。為啥不自動為每個列都建立個索引呢？別忘了，每建立一個索引都會建立一棵B+樹，每插入一條記錄都要維護各個記錄、數(shù)據(jù)頁的排序關系，這是很費性能和存儲空間的。

我們可以在創(chuàng)建表的時候指定需要建立索引的單個列或者建立聯(lián)合索引的多個列：

CREATE TALBE 表名 (

? ? 各種列的信息 ··· ,

? ? [KEY|INDEX] 索引名 (需要被索引的單個列或多個列)

)

其中的KEY和INDEX是同義詞，任意選用一個就可以。我們也可以在修改表結構的時候添加索引：

ALTER TABLE 表名 ADD [INDEX|KEY] 索引名 (需要被索引的單個列或多個列);

也可以在修改表結構的時候刪除索引：

ALTER TABLE 表名 DROP [INDEX|KEY] 索引名;

比方說我們想在創(chuàng)建index_demo表的時候就為c2和c3列添加一個聯(lián)合索引，可以這么寫建表語句：

CREATE TABLE index_demo(

? ? c1 INT,

? ? c2 INT,

? ? c3 CHAR(1),

? ? PRIMARY KEY(c1),

? ? INDEX idx_c2_c3 (c2, c3)

);

在這個建表語句中我們創(chuàng)建的索引名是idx_c2_c3，這個名稱可以隨便起，不過我們還是建議以idx_為前綴，后邊跟著需要建立索引的列名，多個列名之間用下劃線_分隔開。

如果我們想刪除這個索引，可以這么寫：

ALTER TABLE index_demo DROP INDEX idx_c2_c3;