(六)MySQL索引原理篇：深入資料庫底層揭開索引機制的神祕面紗！

---

theme: channing-cyan

引言

本文為掘金社群首發簽約文章，14天內禁止轉載，14天后未獲授權禁止轉載，侵權必究！

   本篇也是MySQL索引機制的終章，在經過《索引初識篇》、《索引應用篇》兩篇後，已經對索引有了很高的掌握度了，但MySQL的索引機制，自始至終對於我們都是一個黑盒般的存在，我們並不清楚建立索引後MySQL會發生什麼，也並不清楚使用索引查詢時會如何檢索......。甚至在前兩篇文章中，對於索引咱們也留下了很多很多的疑惑：

那麼！《索引原理篇》它現在終於來了！但對於索引原理及底層實現，相信大家多多少少都有了解過，畢竟這也是面試過程中出現次數較為頻繁的一個技術點。在本文中就來一窺MySQL索引底層的神祕面紗！

一、MySQL索引為何使用B+樹結構？

   MySQL的索引機制中，有一點可謂是路人皆知，既預設使用B+Tree作為底層的資料結構，但為什麼要選擇B+樹呢？有人會說樹結構是以二分法查詢資料，所以會在很大程度上提升檢索效能，這點確實沒錯，但樹結構有那麼多，MySQL為什麼不選二叉樹、AVL樹、紅黑樹或B樹呢？下面一起先聊一聊這個話題。

對於索引為什麼不支援陣列、連結串列、佇列等結構就不做過多解釋了，因為這些結構中的元素都是按序並排儲存，如果選擇這些結構來實現索引，那走索引依舊等價於走全表，並未帶來查詢時的效率提升，反而帶來了額外的儲存開銷，這是沒有意義的。

1.1、普通SQL的全表掃描過程

   想要真正理解MySQL為何選B+樹結構之前，你必須要先了解一條普通SQL的全表掃描過程，否則你很難真正切身感受出有索引和沒索引的區別。當然，這裡就不再以偽邏輯的形式講解全表掃描了，而是真正的為大家講解MySQL全表掃描的實際過程。以下面這張使用者表為例：

首先假設表中不存在任何索引，此時來執行下述這條SQL： sql SELECT * FROM `zz_user` WHERE `name` = "黑熊"; 因為表中不具備索引，所以這裡會走全表掃描的形式檢索資料，但不管是走全表亦或索引，本質上由於資料都儲存在磁碟中，因此首先都會觸發磁碟IO，所以先來說說磁碟尋道的過程：

如果磁碟不是SSD型別，大致長上面這個樣子，裡面有一個個的盤面和磁針，當發生磁碟IO時，首先會根據給出的磁碟地址，在盤面上尋道。這個尋道過程是怎麼回事呢？就跟小時候VCD、DVD放光碟類似，盤面會開始轉圈圈，在盤面上有一個磁軌的概念，當轉到了對應的地址時，磁軌和磁針會相互吸引，然後以一上一下的方式讀取0、1二進位制資料，最終從磁碟中將目標地址中的資料讀取出來。

磁碟尋道的大致過程如上，具體的細節沒寫出來，重點是大家要感受這個過程即可。

當走全表掃描時，會發生磁碟IO，但是磁碟尋道是需要有一個地址的，這個地址最開始就是本地表資料檔案中的起始地址，也就是從表中的第一行資料開始讀，讀到資料後會載入記憶體，然後MySQL-Server會根據SQL條件對讀到的資料做判斷，如果不符合條件則繼續發生磁碟IO讀取其他資料（如果表比較大，這裡不會以順序IO的形式走全表檢索，而是會觸發隨機的磁碟IO）。

那來看一下，上面給出的使用者表中，「黑熊」這條資料位於表的第五行，那這裡會發生五次磁碟IO嗎？答案是NO，為什麼呢？因為OS、MySQL中都有一個優化措施，叫做區域性性讀取原理。

1.1.1、區域性性原理

區域性性原理的思想比較簡單，比如目前有三塊記憶體頁x、y、z是相連的，CPU此刻在操作x頁中的資料，那按照計算機的特性，一般同一個資料都會放入到物理相連的記憶體地址上儲存，也就是當前在操作x頁的資料，那麼對於y，z這兩頁記憶體的資料也很有可能在接下來的時間內被操作，因此對於y，z這兩頁資料則會提前將其載入到高速緩衝區（L1/L2/L3），這個過程叫做利用區域性性原理“預讀”資料。

但是一次性到底預讀多大的資料放入到高速緩衝區中呢？

這個是由快取行大小決定的，比如因特爾的MESI協議中，快取行的預設大小為64k，也就是說在因特爾的CPU中，一次性會將“當前操作資料”附近的64K資料（16頁資料）提前載入進高速緩衝區。

OK~，上述內容講的是作業系統高速緩衝區的知識，在CPU中利用區域性性原理，提前將資料從記憶體先放入L1/L2/L3三級緩衝區中，主要是為了減小CPU暫存器與記憶體之間的效能差異。

OK~，由於CPU暫存器和記憶體之間的效能差異太大，所以逐個讀資料的形式會導致CPU工作期間的大量時間會處於等待資料狀態，所以利用區域性性原理將資料“預讀”到高速區。而對於MySQL而言，亦是同理，儲存資料的磁碟和記憶體之間的效能差異也是巨大的，因為MySQL也會利用區域性性原理，提前“預讀”資料。

這是什麼意思呢？其實就是指MySQL一次磁碟IO不僅僅只會讀取一條表資料，而是會讀取多條資料，那到底讀多少條資料呢？在InnoDB引擎中，一次預設會讀取16KB資料到記憶體。

1.1.2、全表掃描過程

回到前面分析全表掃描的階段，由於MySQL中會使用區域性性原理的思想，所以對於給出的使用者表資料而言，可能只需發生一次磁碟IO就能將前五條資料全部讀到記憶體，然後會在記憶體中對本次讀取的資料逐條判斷，看一下每條資料的姓名欄位是否為「黑熊」： - 如果發現不符合SQL條件的行資料，則會將當前這條資料放棄，同時在本次SQL執行過程中會排除掉這條資料，不會對其進行二次讀取。 - 如果發現當前的資料符合SQL條件要求，則會將當前資料寫入到結果集中，然後繼續判斷其他資料。

當本次磁碟IO讀取到的所有資料全部篩選完成後，緊接著會看一下表中是否還有其他資料，如果還有則繼續觸發磁碟IO檢索資料，如果沒有則將記憶體中的結果集返回。

有人或許會疑惑，為什麼這裡已經讀到了符合條件的資料，還需要繼續發生磁碟IO呢？因為表中的欄位沒有建立唯一索引或唯一約束，因此MySQL不確定是否還有其他同名的資料，所以需要將整個表全部掃描一遍，才能得到最終結論。

好的，到這裡就將MySQL全表掃描的過程講明白了，緊著來看看全表掃描有什麼問題呢？

其實按目前的情況來看，似乎不會有太大的問題，因此表中資料不多，一次磁碟IO幾乎就能讀完。但思考一下，如果當表的資料量變為百萬級別、千萬級別呢？假設表中一條資料大小為512Bit，一次磁碟IO也只能讀32條，假設表中有320w條資料，一次全表就有可能會觸發10W次磁碟IO，每次都需要在硬體上讓那個盤面轉啊轉，其過程的開銷可想而知.....

因此建立索引的原因就在於此處，為了避免查詢時走全表掃描，因此全表掃描的開銷會隨著資料量增長而越來越大。

1.2、索引為何不選擇二叉樹？

   資料結構與演算法，這門學科從誕生到現在，自始至終都讓人難以理解，但國外有一個比較厲害的程式設計師，為了幫助他人更好的理解資料結構，自己搭建了一個資料結構的動畫演示平臺，裡面提供了非常多豐富的資料結構型別，我們在其中能以動畫的形式觀測資料結構的變化。

迴歸話題本身，全表掃描由於走的是線性查詢，因此資料越多，開銷越大，此時先來看看二叉搜尋樹。

Binary Search Tree二叉搜尋樹是遵守二分搜尋法實現的一種資料結構，咱們先來看看這種資料結構為何不適合用來做索引結構呢？

上圖是我提前構建的二叉樹，其中存在6個節點，按咱們前面給出的案例，「黑熊」這條資料位於表的第五行，那假設以二叉樹作為索引結構，想要定位到第五行資料，需要經過幾次磁碟IO呢？來看動圖演示效果：

從動畫中可以明顯看到，想要查到第五條資料，需要經過五次查詢，由於樹結構在磁碟中儲存的位置也不連續，因此無法利用區域性性原理讀取後續的節點，所以最終需要發生五次磁碟IO才能讀取到資料。 - 二叉樹不適合作為索引結構的原因： - ①如果索引的欄位值是按順序增長的，二叉樹會轉變為連結串列結構。 - ②由於結構轉變成了連結串列結構，因此檢索的過程和全表掃描無異。 - ③由於樹結構在磁碟中，各節點的資料並不連續，因此無法利用區域性性原理。

1.3、索引為何不選擇紅黑樹？

   上面簡單的分析二叉樹後，很明顯的可以看出，二叉樹並不適合作為索引結構，那接下來再看看大名鼎鼎的Red-Black Tree紅黑樹：

同樣提前先構建好了六個節點，相較於之前的二叉樹，紅黑樹則進一步做了優化，它是一種自適應的平衡樹，會根據插入的節點數量以及節點資訊，自動調整樹結構來維持平衡，從樹的高度上來看，明顯比之前的6層減少到了4層，那此時再來看看檢索的過程：

由於樹變矮了，其效果也很明顯，在紅黑樹中只需要經過三次查詢，就能定位到第五個節點，似乎看起來還不錯對嘛？但MySQL為啥不用這顆名聲遠揚的紅黑樹呢？ - 紅黑樹不適合作為索引結構的原因： - ①雖然對比二叉樹來說，樹高有所降低，但資料量一大時，依舊會有很大的高度。 - ②每個節點中只儲存一個數據，節點之間還是不連續的，依舊無法利用區域性性原理。

對於上述兩個缺點羅列的很明白，其本質上的原因就在於：單個節點中只能儲存一個數據，因此一方面樹會隨著資料量增長越來越高，第二方面也無法利用區域性性原理減少磁碟IO。

那是不是把紅黑樹稍微改造一下，讓其單個節點中可儲存多個數據是不是可以了呢？B樹就是這樣乾的，一起來看看。

1.4、索引為何不選擇B-Tree？

   在前面提到過，將紅黑樹稍微改造一下，讓其單節點可容納多個數據，就能在很大程度上改善其效能，事實上B-Tree就是這麼做的，B樹可以理解成紅黑樹的一個變種，如下：

此時給B樹結構也添加了6個節點，此時觀測上述結構，一方面樹僅有2層，同時一個節點中也儲存了多個數據，再來看看B樹的查詢過程：

哦吼吼吼~，完美完美，兩次就查到了資料，同時一個節點中還能儲存多個數據，可充分利用區域性性原理，讓一次磁碟IO讀取多個數據！！但有人可能會問，上面的一個節點也只存兩個資料啊，沒太大的區別似乎。但你要這麼想就錯了，B樹中一個節點可容納的資料個數，可以自己控制的，例如：

在這裡將Max.Degree更改後，B樹單節點的容量也會隨之更改，從上圖中可清晰看到一個節點同時將6個數據全儲存進去了，這也就代表著只需要一次磁碟IO就能檢索出5這個資料，是不是很完美？先別急著下定律，畢竟咱們目前是站在索引設計者的角度來看待問題的，此時雖然看起來很美好了，但想一個問題：

MySQL由於是關係型資料庫，因此經常會碰到範圍查詢的需求，舉例：
SELECT * FROM zz_user WHERE ID BETWEEN 2 AND 5;

比如上述這條SQL語句，需要查詢表中ID在2~5的所有資料，那也就代表著需要查四條資料，在這裡因為2~5在同一個節點中，因此僅觸發一次IO就可拿到資料，但實際業務中往往不會有這麼小的範圍查詢，假設此時是查ID=2~1000之間的資料呢？這麼多資料定然不會在一個節點中，因此這裡又會觸發多次磁碟IO！ - B樹不適合作為索引結構的原因： - 雖然對比之前的紅黑樹更矮，檢索資料更快，也能夠充分利用區域性性原理減少IO次數，但對於大範圍查詢的需求，依舊需要通過多次磁碟IO來檢索資料。

1.5、索引為何要選擇B+Tree？

   上面聊到的B-Tree相對來說已經較為完美了，但最後也談到：它並不適合用於範圍查詢，但這種查詢需求在關係型資料庫中又很常見，那這裡怎麼優化呢？一起來看看B+Tree：

相較於B樹而言，B+樹的結構又出現了新的變化，一方面節點分為了葉節點和葉子節點兩類，這裡先有這兩個概念即可，後續介紹這兩類節點在索引中的作用。B+樹中除開節點分為兩類外，還有一個最大的變化就是：最下面的一排節點之間，都存在一個單向指標，指向下一個節點所在的位置，這也是B+樹對B樹的最大改造點：

前面講過，由於B樹不適合於大範圍查詢操作，因此B+樹中多了個指標，當需要做範圍查詢時，只需要定位第一個節點，然後就可以直接根據各節點之間的指標，獲取到對應範圍之內的所有節點，也就是隻需要發生一次IO，就能夠確定所查範圍之內的所有資料位置。

OK~，到現在為止，B+樹以接近完美的形式解決之前其他資料結構中的所有問題，因此B+Tree正式成為了MySQL預設的索引結構，因此對於MySQL索引為何要選擇B+Tree的原因大家應該也懂了，MySQL的設計者在研發時，也絕對是對比了多種資料結構後，逐步推導其缺陷，然後採用更好的資料結構代替，從而最終推匯出了B+Tree。

OK~，接下來再說一下前面丟擲的一個問題：葉節點和葉子節點在MySQL索引中的作用。

要弄明白這個問題，首先得搞清楚葉節點和葉子節點是什麼？其實很簡單：

B+Tree上面這些節點則被稱為葉節點，在MySQL中不會儲存資料，僅儲存指向葉子節點的指標，這樣做的好處在於能夠讓一個葉節點中儲存更多的元素，從而確保樹的高度不會由於資料增長而變得很高。

同時，B+Tree最下面這排節點則被稱為葉子節點，這些節點中會儲存實際的資料，例如聚簇索引中就直接儲存對應的行資料，非聚簇索引中則儲存指向主鍵/聚簇索引的欄位值。同時每個葉子節點之間都有一根單向指標指向下一個節點，從而使得最下面的一排葉子節點之間又形成了一個單向連結串列結構，方便範圍取值。

1.5.1、B+Tree結構為何會存在葉節點呢？

其實在之前的資料結構中，從來沒有葉節點的這個概念出現，每個節點資訊在整棵樹結構中只會儲存一份，但為什麼B+樹中會用葉節點，同時冗餘一份節點資訊呢？因為你從前面的B+Tree結構中，也能明顯觀測到2、3、4、5節點都會出現了兩次。在這裡如果想要搞明白為什麼要冗餘節點，你得想明白一個問題：

能不能將所有的索引資料、表資料全部放入到一個節點中儲存呢？這樣樹的高度永遠為1呀，是不是隻需要經過一次磁碟IO啊？

其實乍一聽似乎有道理，實則是行不通的，因為一次磁碟IO讀取的資料量是有限制的，如果將所有的資料全放入到一個節點中儲存，那一次磁碟IO只能讀取節點的一部分資料，將整個節點讀完，本質上就和之前走一次全表沒區別了。

理解這個點之後，再來看看丟擲的問題：B+Tree為何會有葉節點冗餘資料呢？

因為B+Tree的每個節點大小會有限制，所以如果將資料儲存在葉節點上，會導致單個樹節點存的索引鍵很少。但如果樹的葉節點不存實際的行資料，就代表單個節點可以存更多的索引鍵，單個節點存的越多也就代表著樹的高度會越小，樹的高度越小就等價於查詢時會發生的磁碟IO次數越少，IO次數越少就相當於資料檢索速度會更快，到這裡相信大家應該能明白為什麼會有葉節點冗餘索引鍵了。

但索引中除開索引鍵外，也必須要存資料，如果不存資料索引就失去了意義，因此B+tree最下面一排的葉子節點，其中就會儲存對應的索引鍵與行資料/聚簇索引欄位值。

一句話來概述，B+Tree的葉節點僅是作為一個“過渡者”的角色，主要是為了提升索引效率的，實際的資料會儲存在最下面的葉子節點中，葉節點中僅有一個指標指向罷了。

1.5.2、千萬級別的表B+Tree會有多高？

搞清楚B+Tree的一些疑惑後，此時來倒推一個問題，MySQL中一張千萬級別的資料表，如果基於自增ID的主鍵欄位建立B+樹索引，那此時樹會有多高呢？有人或許會認為，雖然B+Tree結構很優異，但千萬級別的表至少有1000W條資料，再怎麼樣應該也有幾十、幾百的樹高吧？但實際上答案會讓你大吃一驚。

想要科學的弄懂這個問題，那必須建立在實際的依據上來計算，想要計算出樹高，首先得有三個值：
①索引欄位值的大小。
②MySQL中B+Tree單個節點的大小。
③MySQL中單個指標的大小。

如何計算索引欄位值的大小呢？

這點要依據欄位所使用的資料型別來決定。假設此時表的自增ID，建立表時使用的int型別，int型別在計算機中佔4Bytes，那此時基於ID欄位建立主鍵索引時，B+Tree每個節點的索引鍵大小就為4Bytes。

如何得知MySQL中B+樹單個節點的大小呢？

對於索引單個節點的容量是多少呢？在MySQL中預設使用引擎的一頁大小作為單節點的容量，假設此時表的儲存引擎為InnoDB，就可以通過下述這條命令查詢：
sql SHOW GLOBAL STATUS LIKE "Innodb_page_size"; +------------------+-------+ | Variable_name | Value | +------------------+-------+ | Innodb_page_size | 16384 | +------------------+-------+ 從上述查詢結果來看，InnoDB引擎的一頁大小為16384Bytes，也就是16KB，此時也就代表著B+Tree的每個節點容量為16KB。

MySQL中的指標是多大呢？

一般來說，作業系統的指標為了方便定址，一般都與當前的作業系統位數對應，例如32位的系統，指標就是32bit/4Bytes，64位的作業系統指標則為64bit/8Bytes，但由於64bit的指標定址範圍太大，目前的計算機根本用不上這麼大的定址範圍，因此在MySQL-InnoDB引擎的原始碼中，單個指標被縮小到6Bytes大小。

千萬級別的索引樹高計算

從上述三條可得知：單個索引節點容量為16KB，主鍵欄位值為4B，指標大小為6B，一個完整的索引資訊是由主鍵欄位值+指標組成的，也就是4+6=10B，那此時先來計算一下單個節點中可儲存多少個索引資訊呢？

16KB / 10B ≈ 1638個。

那此時來計算一下，對於一顆高度為2的B+樹，根節點可儲存1638個葉子節點指標，也就代表著B+Tree的第二層有1638個葉子節點，因為葉子節點要儲存實際的行資料，假設表中每行資料為1KB，這也就是代表著一個葉子節點中可儲存16條行資料，那麼一顆高度為2的B+樹可儲存的索引資訊為：1638 * 16 = 26208條資料。

再來算算樹高為3的B+樹可以存多少呢？因為最下面一排才是葉子節點，此時樹高為3，也就代表著中間一排是葉節點，只儲存指標並不儲存資料，而每個節點可容納1638個索引鍵+指標資訊，因此計算過程是：1638 * 1638 * 16 = 42928704條。

是不是很令你驚訝？樹高為3的B+Tree，竟然可以儲存四千多萬條資料，也就代表著千萬級別的表，走索引查詢的情況下，大致只需要發生三次磁碟IO即可獲取資料。

當然，上述的這個資料是基於主鍵為int型別、表的一行資料為1KB來計算的，實際情況中會不一樣，因為主鍵有可能是bigint型別或其他型別，而一行資料也可能不僅僅只有1KB。因此對於一張實際的千萬級別表，它的主鍵索引實際樹高有多少，你結合主鍵的資料型別以及一行資料的大小，也可以計算出來，它同時不會太高。
對實際的千萬表索引樹高感興趣的，我提供一個計算公式：索引鍵大小=索引欄位型別所佔的空間、一行表資料大小=所有表字段的型別+隱藏欄位（20Bytes）所佔大小總和，得到這兩個值之後，再套入前面的例子中既可得知。

看到這裡，對於索引憑啥那麼快？為啥能夠提升查詢效能？相信大家也有了答案，畢竟索引樹高才是個位數，發生的磁碟IO次數也那麼少，檢索資料的速度不快才來了個鬼~

不過B+Tree中的每個索引頁中，還會儲存頁頭（頁號、指標、偽記錄等）、頁目錄、頁尾等資訊，大概一共佔用128KB左右，因此想要真正的計算出來接近實際情況的索引樹高，還需要把這點考慮在內~

1.5.3、MySQL索引底層的真正結構

以為B+Tree就是索引的終點了嘛？實則不然，MySQL的追求可不止於此，雖然B+Tree已經特別特別優秀了，但B+Tree的葉子節點之間是單向指標組成的連結串列結構，這對於倒排序查詢時，顯然並不友好，因為只有單向指標，那麼只能先正序獲取資料後再倒排一次，因此MySQL真正的索引結構還對B+Tree做了變種設計！

啥意思呢？也就是MySQL在設計索引結構時，對於原始的B+Tree又一次做了改造，葉子節點之間除開一根單向的指標之外，又多新增了一根指標，指向前面一個葉子節點，也就是MySQL索引底層的結構，實際是B+Tree的變種，葉子節點之間是互存指標的，所有葉子節點是一個雙向連結串列結構。

這樣做的好處在於：即可以快速按正序進行範圍查詢，而可以快速按倒序進行範圍操作，在某些業務場景下又能進一步提升整體效能！

1.5.4、字首索引為何能提升索引效能？

這個問題是在之前的《索引初識篇》中丟擲的問題，到這裡答案也就呼之欲出了，因為字首索引可以選用一個欄位的前N個字元來建立索引，相較於使用完整欄位值做為索引鍵，字首索引的索引鍵，顯然佔用的空間更少，一個索引鍵越小，代表一個B+Tree節點中可以儲存更多的索引鍵，等價於樹高會越小，也就代表磁碟IO更少，檢索資料時自然效率更高。

二、建立索引時那些不為人知的內幕

   弄明白了索引的底層資料結構後，再一起來聊一聊建立索引後會發生什麼事情呢？一般我們都會以下述方式建立索引：
sql -- ①通過CREATE語句建立 CREATE INDEX indexName ON tableName (columnName(length) [ASC|DESC]); -- ②通過ALTER語句建立 ALTER TABLE tableName ADD INDEX indexName(columnName(length) [ASC|DESC]); -- ③建表時通過DML語句建立 CREATE TABLE tableName( columnName1 INT(8) NOT NULL, columnName2 ...., ....., INDEX [indexName] (columnName(length)) ); 在咱們通過SQL命令建立索引時，MySQL首先會判斷一下當前表的儲存引擎，因為在《索引初識篇》中提到過，索引機制本身是由儲存引擎層提供實現的，不同的引擎實現的索引也不同，因此建立索引時第一步就會先判斷儲存引擎，然後根據不同的儲存引擎建立索引，這裡重點聊一下常用的MyISAM、InnoDB。

2.1、常用儲存引擎的資料儲存

首先為了能夠實際觀察到兩個引擎之間的區別，分別使用MyISAM、InnoDB兩個引擎建立兩張表： ``sql -- 建立一張使用MyISAM引擎的表：zz_myisam_index CREATE TABLEzz_myisam_index(z_m_idint(8) NOT NULL,z_m_name` varchar(255) NULL DEFAULT '' ) ENGINE = MyISAM CHARACTER SET = utf8 COLLATE = utf8_general_ci ROW_FORMAT = Compact;

-- 建立一張使用InnoDB引擎的表：zz_innodb_index CREATE TABLE zz_innodb_index ( z_i_id int(8) NOT NULL, z_i_name varchar(255) NULL DEFAULT '' ) ENGINE = InnoDB CHARACTER SET = utf8 COLLATE = utf8_general_ci ROW_FORMAT = Compact; `` 上述過程中建立了兩張表：zz_myisam_index、zz_innodb_index，分別使用了不同的引擎，而MySQL中對於所有的資料都會放入到磁碟中儲存，因此先來找一下這兩張表的本地位置，預設位於C:\ProgramData\MySQL\MySQL Server 5.x\data`這個目錄中，在這裡儲存著所有已建立的資料庫磁碟檔案，首先從這裡面找到對應的資料庫並進入目錄，如下：

對於這幾個檔案相信大家一定不陌生，畢竟在《MySQL架構篇-檔案系統層》中曾介紹過，此時分別來看看使用不同引擎的兩張表有何不同。

2.1.1、使用MyISAM引擎的表

zz_myisam_index這張表是使用MyISAM引擎的表，在磁碟中有三個檔案： - zz_myisam_index.frm：該檔案中儲存表的結構資訊。 - zz_myisam_index.MYD：該檔案中儲存表的行資料。 - zz_myisam_index.MYI：該檔案中儲存表的索引資料。

也就是說，MyISAM引擎的表資料和索引資料，是分別放在兩個不同的磁碟檔案中儲存的，這也意味著MyISAM引擎並不支援聚簇索引，因為聚簇索引要求表資料和索引資料一起儲存在同一塊空間，而MyISAM的.MYI索引檔案中，儲存的是表資料所在的地址指標。

2.1.2、使用InnoDB引擎的表

zz_innodb_index這張表是使用InnoDB引擎的表，在磁碟中僅有兩個檔案： - zz_innodb_index.frm：該檔案中儲存表的結構資訊。 - zz_innodb_index.ibd：該檔案中儲存表的行資料和索引資料。

因為InnoDB引擎中，表資料和索引資料都一起放在.ibd檔案中，也就代表著索引資料和表資料是處於同一塊空間儲存的，這符合聚簇索引的定義，因此InnoDB支援聚簇索引。

同時也正由於這個原因，所以如果使用InnoDB引擎的表未主動建立聚簇索引，它會自動選擇表中的主鍵欄位，作為聚簇索引的欄位。但如果表中未宣告主鍵欄位，那則會選擇一個非空唯一索引來作為聚簇索引。但如果表中依舊沒有非空的唯一索引，InnoDB則會隱式定義一個主鍵來作為聚簇索引（這個列在上層是不可見的，是一個按序自增的值）。

OK~，搞明白兩種常用引擎的底層儲存區別後，接下來再聊聊手動建立索引後究竟會發生什麼？

2.2、手動建立索引後發生的事情

當手動建立索引後，MySQL會先看一下當前表的儲存引擎是誰，接著會判斷一下表中是否存在資料，如果表中沒有資料，則直接構建一些索引的資訊，例如索引欄位是誰、索引鍵佔多少個位元組、建立的是啥型別索引、索引的名字、索引歸屬哪張表、索引的資料結構.....，然後直接寫入對應的磁碟檔案中，比如MyISAM的表則寫入到.MYI檔案中，InnoDB引擎的表則寫入到.ibd檔案中。

上述這個過程，是表資料為空時，建立索引會幹的工作，還算比較簡單，但當表中有資料時，過程也一樣嗎？NO，會多出很多步驟。

當表中有資料時，首先MySQL-Server會先看一下目前要建立什麼型別的索引，然後基於索引的型別對索引欄位的值，進行相應的處理，比如： - 唯一索引：判斷索引欄位的每個值是否存在重複值，如果有則丟擲錯誤碼和資訊。 - 主鍵索引：判斷主鍵欄位的每個值是否重複、是否有空值，有則丟擲錯誤資訊。 - 全文索引：判斷索引欄位的資料型別是否為文字，對索引欄位的值進行分詞處理。 - 字首索引：對於索引欄位的值進行擷取工作，選用指定範圍的值作為索引鍵。 - 聯合索引：對於組成聯合索引的多個列進行值拼接，組成多列索引鍵。 - ........

根據索引型別做了相應處理後，緊接著會再看一下當前索引的資料結構是什麼？是B+Tree、Hash亦或是其他結構，然後根據資料結構對索引欄位的值進行再次處理，如： - B+Tree：對索引欄位的值進行排序，按照順序組成B+樹結構。 - Hash：對索引欄位的值進行雜湊計算，處理相應的雜湊衝突，方便後續查詢。 - .......

到這一步為止，已經根據索引結構，對索引欄位的值處理好了，此時就會準備將記憶體中處理好的欄位資料，寫入到本地相應的磁碟檔案中，但如果此時為InnoDB引擎，那在寫入前還會做最後一個判斷，也就是判斷當前的索引是否為主鍵/聚簇索引： - 如果當前建立索引的欄位是主鍵欄位，則在寫入時重構.ibd檔案中的資料，將索引鍵和行資料調整到一塊區域中儲存。

當然，如果這裡建立的不是主鍵/聚簇索引，或者目前是MyISAM引擎，則意味著現在需要建立的是非聚簇索引，因此會先會為每個索引鍵（索引欄位值）尋找相應的行資料，找到之後與索引鍵關聯起來，不過InnoDB、MyISAM引擎兩者之間的非聚簇索引也會存在些許差異，所以在這裡也會有一點點不同：
- InnoDB：因為有聚簇索引存在，所以非聚簇索引在與行資料建立關聯時，存放的是主鍵/聚簇索引的欄位值。 - MyISAM：由於表資料在單獨的.MYD檔案中，因此可以直接以指標的形式關聯起來。

也就是說，InnoDB引擎中的非聚簇索引，都是主鍵/聚簇索引的“附庸”，因此每個索引資訊中是以「索引鍵：聚簇欄位值」這種形式關聯的。

但MyISAM引擎中由於表資料和索引資料都是分開儲存的，所以MyISAM的每個非聚簇索引都是獨立的，因此每個索引資訊則是以「索引鍵：行資料的地址指標」這種形式關聯。

由於MyISAM引擎的非聚簇索引，關聯的是行資料的指標，而InnoDB引擎關聯的是聚簇索引的索引鍵，所以InnoDB的非聚簇索引在查詢時需要回表，再查一次聚簇索引才能得到資料。而MyISAM每個非聚簇索引都能直接獲取到行資料的地址，可以直接根據指標獲取資料，從整體而言，MyISAM檢索資料的效率會比InnoDB快上不少。

到這裡，索引鍵和行資料關聯好之後，就會開始根據引擎的不同，將記憶體中的索引資訊分別寫入到不同的磁碟檔案中。寫完完成後，B+Tree的根節點會放到記憶體中維護，以便於後續索引查詢時再次從磁碟讀取根節點資訊。

到這裡為止，大家也應該明白了為什麼建立表之後，立馬建索引會很快，但當表中有不少資料時建立索引會很慢的原因，就是因為表中有資料時，建立索引要做一系列判斷、處理工作。

OK~，最後再放上一個聚簇索引和非聚簇索引的結構區別：

在上圖中給出了一張使用者表，然後基於ID欄位建立主鍵/聚簇索引，基於name欄位建立普通/非聚簇索引，最終索引結構如圖中所示。 - 在InnoDB聚簇索引的示意圖中，由於不方便畫出每行資料，就用row_data代替行資料。 - 在InnoDB非聚簇索引中，每個索引資訊中儲存聚簇索引的ID值。 - MyISAM非聚簇索引中，每個索引資訊中則直接儲存行資料的指標。

當然，這裡也是畫出的偽結構，因為不可能按照MySQL單節點16KB的尺寸1:1還原，畢竟畫不下這麼大（實際MySQL對於上述這些資料，一個節點就全放下了）。

索引鍵的大小會隨著值長度變化嗎？

這個問題很有趣，比如現在基於一個int型別的欄位建立了一個索引，但目前的欄位值是1，按理來說這個值只佔1bits對不對？那在索引鍵中，或資料庫中佔多少呢？答案是4Bytes/32bits，這是因為一個int型別在作業系統中就會佔用32bit空間，不會根據實際值而減少佔用空間。

但大家也都知道，資料庫中還有不少文字型別，例如varchar型別，它是固定的長度嗎？並不是，它是一個變長型別，而非一個定長型別，也就是一個varchar欄位值，佔用的空間會隨著實際所儲存的資料而變化。

所以對於一個索引鍵的大小是否會發生變化，這要取決於你是基於什麼欄位型別建立的索引，如果是定長型別就不會變化，但如果是變長型別就會隨之發生改變。

三、索引內部查詢與維護的過程

   建立索引時會發生的內部過程，上一段落已經闡述明白了，接著再來說說查詢SQL執行時，如果選中了索引，索引內部的檢索過程是什麼樣的呢？也包括當寫型別的SQL更改表中資料後，MySQL又會如何維護索引的內部結構呢？

當然，在此之前，如若對於SQL執行前會發生的工作還不瞭解的，可參考《SQL執行篇》。

3.1、聚簇索引查詢資料的過程

在《SQL執行篇》中聊到過，當查詢SQL來到MySQL後，經過一系列處理後，最終會來到優化器，此時會由優化器來為SQL語句選擇出一個合適的索引，當然，你也可以手動強制指定索引。那當SQL命中索引時，索引內部是如何查詢對應的行資料的？

工作執行緒執行查詢SQL時，首先會先看一下當前索引的結構，如果是Hash索引就很簡單了，直接對索引欄位的值進行雜湊計算，然後直接根據雜湊值，從索引中找到相應的索引資訊，最後獲取資料即可。

但如果索引結構是預設的B+Tree呢？內部又會發生什麼工作？

如果當前SQL使用的是主鍵/聚簇索引，比如： sql SELECT * FROM `zz_user` WHERE `ID` = 12; 此時首先會根據條件欄位，去記憶體中找到聚簇索引的根節點，然後根據節點中記錄的地址去找次級的葉節點，最後再根據葉節點中的指標地址，找到最下面的葉子節點，從而獲取其中的行資料，動畫過程如下：

B+Tree結構的索引似乎查詢過程也並不複雜對不對？但有一個細節點需要注意，B+Tree的單個節點可儲存多個數據，也就是當磁碟IO發生後，MySQL一次讀取的資料中有多個索引資訊，此時MySQL會如果查詢單個節點中的索引資訊呢？全部判斷一次嘛？

其實並不會全部判斷一次，因為B+Tree是一種有序的資料結構，小的會放左邊，大的會放右邊，單個節點中的索引資訊，同樣遵循這個原理。既然單個節點中的資料也是有序的，所以MySQL同樣會採用二分查詢法去檢索資料。對於單個節點中的索引資訊，先從索引中間開始查詢，然後判斷一下當前SQL中ID=12這個條件，是大於還是小於最中間的索引鍵，小於則去節點左邊取中間的索引鍵繼續判斷，大於則去右邊.....，以此類推直至定位到單節點中對應索引鍵為止。

OK，如果是範圍取值，比如取ID>=2的所有資料，則會先定位到ID=2的索引鍵，然後通過葉子節點之後的指標，直接將2之後的資料全部取出。

聚簇索引中，定位到了索引鍵，即代表著取到了資料，畢竟索引和行資料是一起儲存的。

3.2、非聚簇索引查詢資料的過程

相較於聚簇索引而言，非聚簇索引前面的步驟都是相同的，僅是最後一步有些許不同罷了，非聚簇索引經過一系列查詢步驟後，最終會取到一個聚簇索引的欄位值，然後再做一次回表查詢，也就是再去聚簇索引中查一次才能取到資料。

如果是MyISAM引擎，則直接根據索引樹中記錄的指標地址，直接觸發磁碟IO再次讀取資料即可。

3.3、寫SQL執行時索引的維護過程

前面分析了查詢SQL執行時，索引查詢資料的過程，那當出現增、刪、改SQL時呢？索引會怎麼維護呢？其實這裡也要分索引型別，如果是Hash結構的索引，直接增刪改對應的索引鍵即可，但B+Tree結構的索引，因為要內部節點是有序的，所以需要維護有序性。

也就是代表著，插入、更改、刪除資料時，都會對B+Tree索引造成影響。

但先說清一個誤區，表中不同的索引在本地有不同的索引記錄，比如ID、Name欄位分別建立了兩個索引，那麼就會有兩顆不同的索引樹寫入到本地磁碟檔案中。

3.3.1、插入資料時索引的變化

B+Tree索引是有序的，對於這點在前面已經反覆提到了，但如果索引欄位是數值型別，例如int、bigint、long等，本身就能區分大小順序，此時可以直接做排序工作。但如果是基於字串或其他型別的欄位建立索引呢？又該如何排序呀？其實對於這個問題也並不難回答，大家還記得在建庫建表時，乾的一件事情嘛？

在建立庫表時，咱們通常都會指定一個排序規則，而這個規則就是MySQL對非數值型別欄位的排序規則，比如字串型別的欄位，MySQL就會基於該規則對值先做計算處理，然後得到一個數值用於排序。

當然，具體排序處理的過程暫且不去糾結，重點只需搞清楚一點：資料庫中任何欄位都能排序即可。

OK~，那此時像資料庫中插入一條資料時，還是以之前的使用者表為例，比如： sql INSERT INTO `zz_user` VALUES(6,"上海市黃浦區xx街道666號","棕熊","男",30); 同樣假設使用者表上有兩個索引，一是基於自增ID建立的主鍵索引，第二個則是基於姓名欄位建立的普通索引。當表中插入這條資料後，索引又會發生什麼變化呢？咱們分開聊聊。

主鍵/聚簇索引的變化

因為主鍵索引欄位，也就是ID欄位是順序遞增的，因此只需要在本地索引檔案的B+Tree結構中，按照樹結構找到最後的位置，將當前插入的ID:6作為索引鍵，以當前插入的行資料作為索引值，然後插入到最後的節點中即可。如下：

按序遞增的索引維護，就是這麼簡單~

普通/非聚簇索引的變化

因為姓名欄位本身的資料型別是字串，與數值型欄位天生的有序不同，字串型別是無序的，因此首先需要根據已經配置好的排序規則，先對插入的name：棕熊這個值進行計算，然後根據計算出的值，決定當前資料在B+Tree中的索引位置，計算好之後再執行插入工作，過程如下：

相較於主鍵欄位的順序ID，插入字串型別的name值會複雜一些，因為從這裡可以明顯看到，插入的“棕熊”資料經過計算後，它並不排最後面，而是排中間，所以要將這個值插入到對應的位置，此時樹的節點就會發生裂變，後續的所有葉子節點都需要往後移動，這個開銷是較大的。

同時，在插入索引資訊時，會以“棕熊”作為索引鍵，以ID：6作為索引值，然後一同插入，也就是要與行資料建立關聯（MyISAM引擎則是行資料的地址指標）。

3.3.2、刪除資料時索引的變化

sql DELETE FROM `zz_user` WHERE ID = 5; 例如上述這條刪除語句，當執行後則會先根據ID在索引樹中查詢索引資訊，然後先刪除非聚簇索引上的索引資訊，緊接著再去聚簇索引上刪除主鍵索引資訊和行資料。

過程大致是相同的，就不再製作動圖演示其過程了，重點要記住的是：先刪非聚簇索引資訊，再刪聚簇索引的資訊，因為聚簇索引上存放著行資料，如果先把聚簇索引刪了，就無法找到非聚簇索引上的資訊了。

3.3.3、更改資料時索引的變化

sql UPDATE `zz_user` SET name = "狗熊" WHERE ID = 6; 對於上述這條修改語句，索引維護的過程相信大家自己也能推測出來，畢竟修改的本質就是先刪再插入，首先在聚簇索引上查到ID=6這條資料，獲取原本的name欄位值：“棕熊”，然後以該值去非聚簇索引上找到對應的索引資訊，然後將這個索引資訊刪除掉，緊接著再插入一個“狗熊”的索引資訊。

當非聚簇索引更新完成後，緊接著會去更新聚簇索引，聚簇索引就不會刪資料了，因為聚簇索引上儲存著行資料。

首先會在聚簇索引上根據ID=6找到對應的行資料，然後將行資料中的name欄位更新為“狗熊”。

至此，對於寫SQL執行後，索引的維護過程就做了簡單分析，實際上也並不難。

PS：實際索引更新資料時，具體的過程也會複雜一些，會牽扯到鎖機制，也包括會判斷修改的新值與原值的大小，如果大小相同則直接在原空間做修改（直接插入覆蓋），如果不同才會先刪再改。

3.4、主鍵為何推薦使用自增整數ID？

在《索引應用篇-主鍵的陷阱》中，我曾推薦大家使用自增的整數ID作為主鍵，而並不是使用隨機的UUID這類字串等型別，這是為何呢？因為觀察前面name索引欄位的插入過程，能夠很明顯的觀察到一個現象，字串是無序的，當使用字串作為主鍵欄位時，在插入資料的時候會頻繁破壞原有的樹結構，造成樹分裂以及後續節點的挪動，一兩個條資料插入倒還沒關係，但是每一條插入的資料都有可能導致樹的結構調整一次，這個過程的開銷可想而知.....

但是自增的整數ID就不會有這個問題，因為插入的ID本身就是按序遞增的，因此插入的每一條新資料，都會直接放到B+Tree最後的節點中儲存。

同時，除開上述原因外，還有一個原因就是UUID比整數自增ID長，UUID至少佔位32位元組，但int型別只佔4位元組，儲存一個UUID的空間，可以存8個自增整數ID。也就代表著單個節點中，能儲存的自增ID會比UUID多很多，單個節點儲存的索引鍵越多.....（後面這一排就不講了，前面複述過兩次了，大家應該也懂哈~）

四、索引原理篇總結

   到目前而言，對於MySQL的索引底層實現，大多數內容就全面講明白了，從最開始的全表掃描過程，到磁碟IO實現、區域性性原理、索引為什麼預設是B+Tree結構、建立索引後發生的一系列事情、寫型別的SQL對索引的影響.....等一系列內容進行了深入剖析。

看完本章後，對於之前兩章中丟擲的一些疑惑，你稍加思考後也能徹底明悟，最後再簡單說說聚簇索引和非聚簇索引的區別。

聚簇索引和非聚簇索引的根本區別： - 聚簇索引中，表資料和索引資料是按照相同順序儲存的，非聚簇索引則不是。 - 聚簇索引在一張表中是唯一的，只能有一個，非聚簇索引則可以存在多個。 - 聚簇索引在邏輯+物理上都是連續的，非聚簇索引則僅是邏輯上的連續。 - 聚簇索引中找到了索引鍵就找到了行資料，但非聚簇索引還需要做一次回表查詢。

InnoDB-非聚簇索引與MyISAM-非聚簇索引的區別： - InnoDB中的非聚簇索引是以聚簇索引的索引鍵，與具體的行資料建立關聯關係的。 - MyISAM中的非聚簇索引是以行資料的地址指標，與具體的行資料建立關聯關係的。

一般來說，由於MyISAM引擎中的索引可以根據指標直接獲取資料，不需要做二次回表查詢，因此從整體查詢效率來看，會比InnoDB要快上不少。

其實也不僅僅跟索引有關係，如果考慮的更加深入來說，其實跟鎖的粒度以及事務也有關係，但對於具體的原因，在後續的《MySQL鎖篇》、《MySQL事務篇》、《MySQL引擎篇》講完後，大家自然就理解啦~