作者：小孩子
來源：我們都是小青蛙
InnoDB數據頁有7個部分組成，各個數據頁可以組成一個雙向鍊表，而每個數據頁中的記錄又可以組成一個單向鍊表，每個數據頁都會為存儲在它裡邊兒的記錄生成一個頁目錄，在通過主鍵查找某條記錄的時候可以在頁目錄中使用二分法快速定位到對應的槽，然後再遍歷該槽對應分組中的記錄即可快速找到指定的記錄。
頁和記錄的關係的示意圖如下：
本集的主題是索引，在正式介紹索引之前，我們需要了解一下沒有索引的時候是怎麼查找記錄的。為了方便大家理解，我們下邊先只嘮叨搜索條件為對某個列精確匹配的情況，所謂精確匹配，就是搜索條件中用等於=連接起的表達式，比如這樣：
SELECT [列名列表] FROM 表名 WHERE 列名 = xxx;
假設目前表中的記錄比較少，所有的記錄都可以被存放到一個頁中，在查找記錄的時候可以根據搜索條件的不同分為兩種情況：
大部分情況下我們表中存放的記錄都是非常多的，需要好多的數據頁來存儲這些記錄。在很多頁中查找記錄的話可以分為兩個步驟：
定位到記錄所在的頁。
從所在的頁內中查找相應的記錄。
不論是根據主鍵列或者其他列的值進行查找，由於我們並不能快速的定位到記錄所在的頁，所以只能從第一個頁沿著雙向鍊表一直往下找，在每一個頁中根據我們上邊已經嘮叨過的查找方式去查找指定的記錄。因為要遍歷所有的數據頁，所以這種方式顯然是超級耗時的，如果一個表有一億條記錄，使用這種方式去查找記錄那要等到猴年馬月才能等到查找結果。
索引為了故事的順利發展，我們先建一個表：
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)
mysql>
這個新建的index_demo表中有2個INT類型的列，1個CHAR(1)類型的列，而且我們規定了c1列為主鍵，這個表使用Compact行格式來實際存儲記錄的。
為了我們理解上的方便，我們簡化了一下index_demo表的行格式示意圖：
我們只在示意圖裡展示記錄的這幾個部分：
record_type：記錄頭信息的一項屬性，表示記錄的類型，0表示普通記錄、2表示最小記錄、3表示最大記錄、1我們還沒用過，等會再說～
next_type：記錄頭信息的一項屬性，表示下一條地址的偏移量，為了方便大家理解，我們都會用箭頭來表明下一條記錄是誰。
各個列的值：就是各個數據列的值，其中我們用橘黃色的格子代表c1列，深藍色的格子代表c2列，紅色格子代表c3列。
其他信息：除了上述3種信息以外的所有信息，包括其他隱藏列的值以及記錄的額外信息。
為了節省篇幅，我們之後的示意圖中會把記錄的其他信息這個部分省略掉，因為它佔地方並且不會有什麼觀賞效果。另外，為了方便理解，我們覺得把記錄豎著放看起來感覺更好，所以將記錄格式示意圖的其他信息去掉並把它豎起來的效果就是這樣：
把一些記錄放到頁裡邊的示意圖就是：
回到正題，我們為什麼要遍歷所有的數據頁呢？因為各個頁中的記錄並沒有規律，我們並不知道我們的搜索條件匹配哪些頁中的記錄，所以 不得不 依次遍歷。
所以如果我們想快速的定位到需要查找的記錄在哪些數據頁中該咋辦？就像為數據頁中的記錄建立一個目錄一樣，我們也可以為所有的數據頁建立一個目錄呀，建這個目錄必須完成下邊這些事兒：
其實這句話的完整表述是這樣的：下一個數據頁中用戶記錄的主鍵值必須大於上一個頁中用戶記錄的主鍵值。為了故事的順利發展，我們這裡需要做一個假設：假設我們的每個數據頁最多能存放3條記錄（實際上一個數據頁非常大，可以存放下好多記錄）。有了這個假設之後我們向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
mysql>
那麼這些記錄已經按照主鍵值的大小串聯成一個單向鍊表了，如圖所示：
從途中可以看出來，index_demo表中的3條記錄都被插入到了編號為10的數據頁中了。此時我們再來插入一條記錄：
mysql> INSERT INTO index_demo VALUES(4, 4, 'a');
Query OK, 1 row affected (0.00 sec)
mysql>
因為頁10最多只能放3條記錄，所以我們不得不再分配一個新頁：
咦？怎麼分配的頁號是28呀，不應該是11麼？
需要注意的一點是，新分配的數據頁編號可能並不是連續的，也就是說我們使用的這些頁在存儲空間裡可能並不挨著。它們只是通過維護著上一個頁和下一個頁的編號而建立了鍊表關係。另外，頁10中用戶記錄最大的主鍵值是5，而頁28中有一條記錄的主鍵值是4，因為5 > 4，所以這就不符合下一個數據頁的主鍵值必須大於上一個頁中的主鍵值的要求，所以在插入主鍵值為4的記錄的時候需要伴隨著一次記錄移動，也就是把主鍵值為5的記錄移動到頁28中，然後再把主鍵值為4的記錄插入到頁10中，這個過程的示意圖如下：
這個過程表明了在對頁中的記錄進行增刪改操作的過程中，我們必須通過一些諸如記錄移動的操作來始終保證這個狀態一直成立：下一個數據頁的主鍵值必須大於上一個頁中的主鍵值。
由於數據頁的編號可能並不是連續的，所以在向index_demo表中插入許多條記錄後，可能是這樣的效果：
因為這些16KB的頁在物理存儲上並不挨著，所以如果想從這麼多頁中根據主鍵值快速定位某些記錄所在的頁，我們需要給它們做個目錄，每個頁對應一個目錄項，每個目錄項包括下邊兩個部分：
頁的用戶記錄中最小的主鍵值，我們用key來表示。
頁號，我們用page_no表示。
所以我們為上邊幾個頁做好的目錄就像這樣子：
以頁28為例，它對應目錄項2，這個目錄項中包含著該頁的頁號28以及該頁中用戶記錄的最小主鍵值5。我們只需要把幾個目錄項在物理存儲器上連續存儲，比如把他們放到一個數組裡，就可以實現根據主鍵值快速查找某條記錄的功能了。比方說我們想找主鍵值為20的記錄，具體查找過程分兩步：
先從目錄項中根據二分法快速確定出主鍵值為20的記錄在目錄項3中（因為 12 < 20 < 209），它對應的頁是頁9。
再根據前邊說的在頁中查找記錄的方式去頁9中定位具體的記錄。
至此，針對數據頁做的簡易目錄就搞定了。不過忘了說了，這個目錄有一個別名，稱為索引。
InnoDB中的索引方案上邊之所以稱為一個簡易的索引方案，是因為我們假設所有目錄項都可以在物理存儲器上連續存儲，但是這樣做有幾個問題：
InnoDB是使用頁來作為管理存儲空間的基本單位，也就是最多能保證16KB的連續存儲空間，而隨著表中記錄數量的增多，需要非常大的連續的存儲空間才能把所有的目錄項都放下，這對記錄數量非常多的表是不現實的。
我們時常會對記錄進行增刪，假設我們把頁28中的記錄都刪除了，頁28也就沒有存在的必要了，那意味著目錄項2也就沒有存在的必要了，這就需要把目錄項2後的目錄項都向前移動一下，這種牽一髮而動全身的設計不是什麼好主意～
所以，設計InnoDB的大叔們需要一種可以靈活管理所有目錄項的方式。他們靈光乍現，忽然發現這些目錄項其實長得跟我們的用戶記錄差不多，只不過目錄項中的兩個列是主鍵和頁號而已，所以他們復用了之前存儲用戶記錄的數據頁來存儲目錄項，為了和用戶記錄做一下區分，我們把這些用來表示目錄項的記錄稱為目錄項記錄。那InnoDB怎麼區分一條記錄是普通的用戶記錄還是目錄項記錄呢？
別忘了記錄頭信息裡的record_type屬性，它的各個取值代表的意思如下：
0：普通的用戶記錄
1：目錄項記錄
2：最小記錄
3：最大記錄
哈哈，原來這個值為1的record_type是這個意思呀，我們把前邊使用到的目錄項放到數據頁中的樣子就是這樣：
從圖中可以看出來，我們新分配了一個編號為30的頁來專門存儲目錄項記錄。這裡再次強調一遍目錄項記錄和普通的用戶記錄的不同點：
目錄項記錄的record_type值是1，而普通用戶記錄的record_type值是0。
目錄項記錄只有主鍵值和頁的編號兩個列，而普通的用戶記錄的列是用戶自己定義的，可能包含很多列，另外還有InnoDB自己添加的隱藏列。
還記得我們之前在嘮叨記錄頭信息的時候說過一個叫min_rec_mask的屬性麼，只有在存儲目錄項記錄的頁中的主鍵值最小的目錄項記錄的min_rec_mask值為1，其他別的記錄的min_rec_mask值都是0。
除了上述幾點外，這兩者就沒啥差別了，它們用的是一樣的數據頁（頁面類型都是0x45BF，這個屬性在Page Header中，忘了的話可以翻到前邊的文章看），頁的組成結構也是一樣一樣的（就是我們前邊介紹過的7個部分），都會為主鍵值生成Page Directory（頁目錄）以加快在頁內的查詢速度。所以現在根據某個主鍵值去查找記錄的步驟可以大致拆分成下邊兩步，以查找主鍵為20的記錄為例（因為都是從一個頁中通過主鍵查某條記錄，所以都可以使用Page Directory通過二分法而實現快速查找）：
先到存儲目錄項記錄的頁中通過二分法快速定位到對應目錄項，因為12 < 20 < 209，所以定位到對應的記錄所在的頁就是頁9.
從頁9中根據二分法快速定位到主鍵值為20的用戶記錄。
雖然說目錄項記錄中只存儲主鍵值和對應的頁號，比用戶記錄需要的存儲空間小多了，但是不論怎麼說一個頁只有16KB大小，能存放的目錄項記錄也是有限的，那如果表中的數據太多，以至於一個數據頁不足以存放所有的目錄項記錄，該咋辦呢？
當然是再多整一個存儲目錄項記錄的頁嘍～ 為了大家更好的理解如何新分配一個目錄項記錄頁的過程，我們假設一個存儲目錄項記錄的頁最多只能存放4條目錄項記錄（請注意是假設哦，真實情況下可以存放好多條的），所以如果此時我們再向上圖中插入一條主鍵值為320的用戶記錄的話，那就需要一個分配一個新的存儲目錄項記錄的頁嘍：
從圖中可以看出，我們插入了一條主鍵值為320的用戶記錄之後新生成了2個數據頁，以查找主鍵值為20的記錄為例：
因為存儲目錄項記錄的頁不止一個，所以如果我們想根據主鍵值查找一條用戶記錄大致需要3個步驟：
確定目錄項記錄頁
我們現在的存儲目錄項記錄的頁有兩個，即頁30和頁32，又因為頁30表示的目錄項的主鍵值的範圍是[1, 320)，頁32表示的目錄項的主鍵值不小於320，所以主鍵值為20的記錄對應的目錄項記錄在頁30中。
通過目錄項記錄頁確定用戶記錄真實所在的頁。
在一個存儲目錄項記錄中定位一條目錄項記錄的方式說過了，不贅述了～
在真實存儲用戶記錄的頁中定位到具體的記錄。
在一個存儲用戶記錄的頁中定位一條真實的用戶記錄的方式已經說過200遍了，你再不會我就，我就，我就求你到上一篇嘮叨數據頁結構的文章中多看幾遍，求你了～
那麼問題來了，在這個查詢步驟的第1步中我們需要定位存儲目錄項記錄的頁，但是這些頁在存儲空間中也可能不挨著，如果我們表中的數據非常多則會產生很多存儲目錄項記錄的頁，那我們怎麼根據主鍵值快速定位一個存儲目錄項記錄的頁呢？其實也簡單，為這些存儲目錄項記錄的頁再生成一個更高級的目錄，就像是一個多級目錄一樣，大目錄裡嵌套小目錄，小目錄裡才是實際的數據，所以現在各個頁的示意圖就是這樣子：
如圖，我們生成了一個存儲更高級目錄項的頁33，這個頁中的兩條記錄分別代表頁30和頁32，如果用戶記錄的主鍵值在[1, 320)之間，則到頁30中查找更詳細的目錄項記錄，如果主鍵值不小於320的話，就到頁32中查找更詳細的目錄項記錄。不過這張圖好漂亮喔，隨著表中記錄的增加，這個目錄的層級會繼續增加，如果簡化一下，那麼我們可以用下邊這個圖來描述它：
這玩意兒像不像一個倒過來的樹呀！其實這是一種組織數據的形式，或者說是一種數據結構，它的名稱是B+樹。
因為我們把數據頁都存放到B+樹這個數據結構中了，所以我們也把我們的數據頁稱為節點。從圖中可以看出來，我們的實際用戶記錄其實都存放在B+樹的最底層的節點上，這些節點也被稱為葉子節點或葉節點，其餘的節點都是用來存放目錄項的，這些節點統統被稱為內節點或者說非葉節點。其中最上邊的那個節點也稱為根節點。
從圖中可以看出來，一個B+樹的節點其實可以分成好多層，設計InnoDB的大叔們為了討論方便，規定最下邊的那層，也就是存放我們用戶記錄的那層為第0層，之後依次往上加。上邊我們做了一個非常極端的假設，存放用戶記錄的頁最多存放3條記錄，存放目錄項記錄的頁最多存放4條記錄，其實真實環境中一個頁存放的記錄數量是非常大的，假設，假設，假設所有的數據頁，包括存儲真實用戶記錄和目錄項記錄的頁，都可以存放1000條記錄，那麼：
如果B+樹只有1層，也就是只有1個用於存放用戶記錄的節點，最多能存放1000條記錄。
如果B+樹有2層，最多能存放1000×1000=1000000條記錄。
如果B+樹有3層，最多能存放1000×1000×1000=1000000000條記錄。
如果B+樹有4層，最多能存放1000×1000×1000×1000=1000000000000條記錄。哇咔咔～這麼多的記錄！！！
你的表裡能存放1000000000000條記錄麼？所以一般情況下，我們用到的B+樹都不會超過4層，那我們通過主鍵去查找某條記錄最多只需要做4個頁面內的查找，又因為在每個頁面內有所謂的Page Directory（頁目錄），所以在頁面內也可以通過二分法實現快速定位記錄，這不是很diao麼，哈哈！
聚簇索引我們上邊介紹的B+樹本身就是一個目錄，或者說本身就是一個索引。它有兩個特點：
使用記錄主鍵值的大小進行記錄和頁的排序，這包括三個方面的含義：
B+樹的葉子節點存儲的是完整的用戶記錄。
所謂完整的用戶記錄，就是指這個記錄中存儲了所有列的值。
我們把具有這兩種特性的B+樹稱為聚簇索引，所有完整的用戶記錄都存放在這個聚簇索引的葉子節點處。這種聚簇索引並不需要我們在MySQL語句中顯式的去創建，InnoDB存儲引擎會自動的為我們創建聚簇索引。另外有趣的一點是，在InnoDB存儲引擎中，聚簇索引就是數據的存儲方式（所有的用戶記錄都存儲在了葉子節點），也就是所謂的索引即數據。
二級索引大家有木有發現，上邊介紹的聚簇索引只能在搜索條件是主鍵值時才能發揮作用，因為B+樹中的數據都是按照主鍵進行排序的。那如果我們想以別的列作為搜索條件該咋辦呢？難道只能從頭到尾沿著鍊表依次遍歷記錄麼？
不，我們可以多建幾棵B+樹，不同的B+樹中的數據採用不同的排序規則。比方說我們用c2列的大小作為數據頁、頁中記錄的排序規則，再建一棵B+樹，效果如下圖所示：
這個B+樹與上邊介紹的聚簇索引有幾處不同：
使用記錄c2列的大小進行記錄和頁的排序，這包括三個方面的含義：
頁內的記錄是按照c2列的大小順序排成一個單向鍊表。
各個存放用戶記錄的頁也是根據頁中記錄的c2列大小順序排成一個雙向鍊表。
各個存放目錄項的頁也是根據頁中記錄的c2列大小順序排成一個雙向鍊表。
B+樹的葉子節點存儲的並不是完整的用戶記錄，而只是c2列+主鍵這兩個列的值。
目錄項記錄中不再是主鍵+頁號的搭配，而變成了c2列+頁號的搭配。
所以如果我們現在想通過c2列的值查找某些記錄的話就可以使用我們剛剛建好的這個B+樹了，以查找c2列的值為4的記錄為例，查找過程如下：
確定目錄項記錄頁
根據根頁面，也就是頁44，可以快速定位到目錄項記錄所在的頁為頁42（因為2 < 4 < 9）。
通過目錄項記錄頁確定用戶記錄真實所在的頁。
在頁42中可以快速定位到實際存儲用戶記錄的頁，但是由於c2列並沒有唯一性約束，所以c2列值為4的記錄可能分布在多個數據頁中，又因為2 < 4 ≤ 4，所以確定實際存儲用戶記錄的頁在頁34和頁35中。
在真實存儲用戶記錄的頁中定位到具體的記錄。
到頁34和頁35中定位到具體的記錄。
但是這個B+樹的葉子節點中的記錄只存儲了c2和c1（也就是主鍵）兩個列，所以我們必須再根據主鍵值去聚簇索引中再查找一遍完整的用戶記錄。
各位各位，看到了麼？我們根據這個以c2列大小排序的B+樹只能確定我們要查找記錄的主鍵值，所以如果我們想根據c2列的值查找到完整的用戶記錄的話，仍然需要到聚簇索引中再查一遍，這個過程也被稱為回表。也就是根據c2列的值查詢一條完整的用戶記錄需要使用到2棵B+樹！！！
為什麼我們還需要一次回表操作呢？直接把完整的用戶記錄放到葉子節點不就好了麼？
你說的對，如果把完整的用戶記錄放到葉子節點是可以不用回表，但是太佔地方了呀～相當於每建立一棵B+樹都需要把所有的用戶記錄再都拷貝一遍，這就有點太浪費存儲空間了。因為這種按照非主鍵列建立的B+樹需要一次回表操作才可以定位到完整的用戶記錄，所以這種B+樹也被稱為二級索引（英文名secondary index），或者輔助索引。由於我們使用的是c2列的大小作為B+樹的排序規則，所以我們也稱這個B+樹為為c2列建立的索引。
聯合索引我們也可以同時以多個列的大小作為排序規則，也就是同時為多個列建立索引，比方說我們想讓B+樹按照c2和c3列的大小進行排序，這個包含兩層：
先把各個記錄和頁按照c2列進行排序。
在記錄的c2列相同的情況下，採用c3列進行排序
為c2和c3列建立的索引的示意圖如下：
如圖所示，我們需要注意一下幾點：
千萬要注意一點，以c2和c3列的大小為排序規則建立的B+樹稱為聯合索引，它的意思與分別為c2和c3列建立索引的表述是不同的，不同點如下：
至此，我們介紹的都是InnoDB存儲引擎中的索引方案，為了內容的完整性，以及各位可能在面試的時候遇到這類的問題，我們有必要再簡單介紹一下MyISAM存儲引擎中的索引方案。我們知道InnoDB中索引即數據，也就是聚簇索引的那棵B+樹的葉子節點中已經把所有完整的用戶記錄都包含了，而MyISAM的索引方案雖然也使用B+樹，但是卻將索引和數據分開存儲：
將表中的記錄按照插入時間順序的存儲在一塊存儲空間上，我們可以通過行號而快速訪問到一條記錄（因為index_demo表的記錄是定長的，所以可以使用行號來進行快速訪問，對於變長的記錄MyISAM有不同的處理方案，我們這裡就不介紹了），如圖所示：
由於在插入數據的時候並沒有刻意按照主鍵大小排序，所以我們並不能在這些數據上使用二分法進行查找。
MyISAM會單獨為表的主鍵創建一個B+樹索引，只不過在B+樹的葉子節點中存儲的不是完整的用戶記錄，而是主鍵值 + 行號的組合。也就是先通過索引找到對應的行號，再通過行號去找對應的記錄！
這一點和InnoDB是完全不相同的，在InnoDB存儲引擎中，我們只需要根據主鍵值對聚簇索引進行一次查找能找到對應的記錄，而在MyISAM中卻需要進行一次回表操作，意味著MyISAM中建立的索引全部都是二級索引！
如果有需要的話，我們也可以對其它的列分別建立索引或者建立聯合索引，原理和InnoDB中的索引是一樣的，只不過在葉子節點處存儲的是相應的列 + 行號而已。這些索引也全部都是二級索引。
光顧著嘮叨索引的原理了，那我們如何使用MySQL語句去建立這種索引呢？InnoDB和MyISAM會自動為主鍵或者聲明為UNIQUE的列去自動建立B+樹索引，但是如果我們想為其他的列建立索引就需要我們顯式的去指明。
為啥不自動為每個列都建立個索引呢？別忘了，每建立一個索引都會建立一棵B+樹，每插入一條記錄都要維護各個記錄、數據頁的排序關係，這是很費性能和存儲空間的。
我們可以在創建表的時候指定需要建立索引的單個列或者建立聯合索引的多個列：
CREATE TALBE 表名 (
各種列的信息 ··· ,
[KEY|INDEX] 索引名 (需要被索引的單個列或多個列)
)
其中的KEY和INDEX是同義詞，任意選用一個就可以。我們也可以在修改表結構的時候添加索引：
ALTER TABLE 表名 ADD [INDEX|KEY] 索引名 (需要被索引的單個列或多個列);
也可以在修改表結構的時候刪除索引：
ALTER TABLE 表名 DROP [INDEX|KEY] 索引名;
比方說我們想在創建index_demo表的時候就為c2和c3列添加一個聯合索引，可以這麼寫建表語句：
CREATE TABLE index_demo(
c1 INT,
c2 INT,
c3 CHAR(1),
PRIMARY KEY(c1),
INDEX idx_c2_c3 (c2, c3)
);
在這個建表語句中我們創建的索引名是idx_c2_c3，這個名稱可以隨便起，不過我們還是建議以idx_為前綴，後邊跟著需要建立索引的列名，多個列名之間用下劃線_分隔開。
如果我們想刪除這個索引，可以這麼寫：
ALTER TABLE index_demo DROP INDEX idx_c2_c3;
對於InnoDB存儲引擎來說，在單個頁中查找某條記錄分為兩種情況：
以主鍵為搜索條件，可以使用Page Directory通過二分法快速定位相應的用戶記錄。
以其他列為搜索條件，需要按照記錄組成的單鍊表依次遍歷各條記錄。
沒有索引的情況下，不論是以主鍵還是其他列作為搜索條件，只能沿著頁的雙鍊表從左到右依次遍歷各個頁。
InnoDB存儲引擎的索引是一棵B+樹，完整的用戶記錄都存儲在B+樹第0層的葉子節點，其他層次的節點都屬於內節點，內節點裡存儲的是目錄項記錄。InnoDB的索引分為兩大種：
聚簇索引
以主鍵值的大小為頁和記錄的排序規則，在葉子節點處存儲的記錄包含了表中所有的列。
二級索引
以自定義的列的大小為頁和記錄的排序規則，在葉子節點處存儲的記錄內容是列 + 主鍵。
MyISAM存儲引擎的數據和索引分開存儲，這種存儲引擎的索引全部都是二級索引，在葉子節點處存儲的是列 + 頁號。
-END-
近期熱文：
關注我
點擊「閱讀原文」，看本號其他精彩內容