看了很多關于MySQL B+樹索引的文檔，但一直有些問題沒搞明白：

• B+樹索引在磁盤上是怎么存儲的？
• 內(nèi)節(jié)點、葉子節(jié)點的物理結構又是什么樣子的？

直到看到一份資料《MySQL 是怎樣運行的：從根兒上理解 MySQL》，基本解決了我的現(xiàn)有疑惑。但好的資料就是看著看著又能讓你思考更多問題，有新的疑惑，再去解決新的疑惑讓自己不斷提升。下面我將把從這個資料學習到的B+樹索引結構的知識按自己的邏輯整理后分享給大家，以此角度來給大家安利這份學習資料，大綱如下：

• B+樹索引結構的推導過程

  1. 數(shù)據(jù)行結構--單向鏈表；
  2. 數(shù)據(jù)頁結構--通過頁目錄使用二分法快速找到目標行；
  3. 目錄項--多個數(shù)據(jù)頁時如何定位到目標行所在的數(shù)據(jù)頁；
  4. B+樹索引--目錄項太多，大目錄嵌套小目錄，就形成了B+樹

• 聚簇索引

  1. 特點；
  2. 主鍵的選擇以及原因。

• 二級索引結構和特點

• MyISAM 索引結構和特點

B+樹索引結構的推導過程

1. 數(shù)據(jù)行結構

InnoDB行--單向鏈表

2. 數(shù)據(jù)頁結構

一個數(shù)據(jù)頁默認16KB，可以存放很多行數(shù)據(jù)，那如何在一個數(shù)據(jù)頁中快速找到一行數(shù)據(jù)呢？在數(shù)據(jù)頁中有個叫“頁目錄”的結構：

• 把數(shù)據(jù)頁里的數(shù)據(jù)行按規(guī)則分成 n 個組；
• 每個組中主鍵最大的那一行數(shù)據(jù)的地址偏移量存到“頁目錄”的“槽”中。

3. 目錄項

如果一張表的數(shù)據(jù)存在很多個數(shù)據(jù)頁里，如何找到目標行數(shù)據(jù)在哪一個數(shù)據(jù)頁中呢？

但是對目錄使用二分法查找的前提是：這個目錄的內(nèi)容（目錄項）是連續(xù)存放在某個地方的。但實際上 IoonDB 的存儲的最小單位是頁，默認只有 16K，所以這個方法在實現(xiàn)上不可行。

由于目錄中的內(nèi)容“目錄項”跟真實的用戶記錄類似：

• 每個數(shù)據(jù)頁中最小的主鍵值；
• 頁號，也叫 page_no。

4. B+樹索引

如上圖，如果一張表的行數(shù)很多，勢必就會有很多數(shù)據(jù)頁，那么就可能出現(xiàn)一個頁存不下所有“目錄項紀錄”的情況，所以可能會有很多個“目錄項數(shù)據(jù)頁”，那又怎么快速知道應該在哪個“目錄項數(shù)據(jù)頁”上查找目標數(shù)據(jù)在哪個“數(shù)據(jù)頁”上呢？

這就是 B+樹索引結構：

• 實際用戶記錄其實都存放在B+樹的最底層的節(jié)點上，這些節(jié)點也被稱為葉子節(jié)點或葉節(jié)點；
• 其余用來存放目錄項的節(jié)點稱為非葉子節(jié)點或者內(nèi)節(jié)點；
• 其中 B+樹最上邊的那個節(jié)點也稱為根節(jié)點。

5. 時間復雜度

索引樹的高度決定了查找數(shù)據(jù)的速度，而索引樹的高度 h 取決于：

• 每個葉子節(jié)點（即數(shù)據(jù)頁）中能存放多少條“用戶記錄”，m；
• 每個內(nèi)節(jié)點或非葉子節(jié)點能存放多少條“目錄項記錄”，n；
• 表的總行數(shù) X。

m*n^(h-1)=X ，則 ??1=log????/?? ，這就是常說的B+樹索引查找的時間復雜度為O(log n) 的由來。（一個頁面最少存儲2條記錄的設計，就是為了讓索引的效果更好）

假設每行數(shù)據(jù)大約1K，innodb 數(shù)據(jù)頁大小默認為16K，也就是大約每個葉子結點可以存放16條用戶記錄，即 m=16；
主鍵ID一般為bigint 類型，占 8 字節(jié)，指針大小在 InnoDB 源碼中設置為 6 字節(jié)，這樣一共 14 字節(jié)，所以每個非葉子結點大約可以存放 16384/14=1170 條目錄項紀錄，即n=1170；
要想控制樹高為3，則表的總行數(shù)應該是：16*1170^(3-1)=21902400

所以InnoDB表行數(shù)一般建議在 2000 萬行以內(nèi)，這樣查詢效率較高。

聚簇索引

1. 特點

其實聚簇索引的特點屬于老生常談了，但按例還是得介紹一下。
在 InnoDB 中聚簇索引（主鍵）就是數(shù)據(jù)的存儲方式（所有的用戶記錄都存儲在了葉子節(jié)點），也就是所謂的索引即數(shù)據(jù)，數(shù)據(jù)即索引。

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

  1. 頁內(nèi)的記錄是按照主鍵的大小順序排成一個單向鏈表；
  2. 各個存放用戶記錄的頁也是根據(jù)頁中用戶記錄的主鍵大小順序排成一個雙向鏈表；
  3. 存放目錄項記錄的頁分為不同的層次，在同一層次中的頁也是根據(jù)頁中目錄項記錄的主鍵大小順序排成一個雙向鏈表。

• B+樹的葉子節(jié)點存儲的是完整的用戶記錄。
  所謂完整的用戶記錄，就是指這個記錄中存儲了所有列的值（包括隱藏列）。

2. 主鍵的選擇

聚簇索引是底層的說法，而主鍵是運維層面的說法（因為有語法 primary key(id)），通常主鍵的選擇是：id int auto_increment，為什么呢？

• int 或者 bigint 類型占用字節(jié)少節(jié)省空間，因為二級索引的葉子節(jié)點、非葉子節(jié)點上都要保存主鍵鍵值；
• 索引是有序的，auto_increment 自增屬性會保證按順序插入數(shù)據(jù)，不會造成數(shù)據(jù)頁的分裂（因為數(shù)據(jù)頁中數(shù)據(jù)行是按照主鍵的順序組成的單向鏈表，數(shù)據(jù)一旦變化，是需要維護這種順序的），減少性能開銷；
• id 字段沒有業(yè)務含義，本身不會被更新，所以記錄基本不會挪動在數(shù)據(jù)頁中的位置。

二級索引

注意這里畫的內(nèi)節(jié)點只包含索引列的值和頁號，但實際上還應包含主鍵值，原文中后面是有單獨一章“內(nèi)節(jié)點中目錄項記錄的唯一性”，說明存主鍵值是為了解決有二級索引允許重復值，但在B+樹索引結構中需要唯一性，這樣插入數(shù)據(jù)才能按序插入到準確位置。

MyISAM

MyISAM 存儲引擎與 InnoDB 是不一樣的，數(shù)據(jù)和索引分開存放：

• 將表中的記錄按照記錄的插入順序單獨存儲在一個文件中，稱之為數(shù)據(jù)文件。這個文件并不劃分為若干個數(shù)據(jù)頁，有多少記錄就往這個文件中塞多少記錄就成了。我們可以通過行號而快速訪問到一條記錄；
• 使用MyISAM存儲引擎的表會把索引信息另外存儲到一個稱為索引文件的另一個文件中。
  MyISAM表的主鍵索引，葉子節(jié)點中存儲的不是完整的用戶記錄，而是主鍵值 + 行號的組合。也就是先通過索引找到對應的行號，再通過行號去找對應的記錄；
  二級索引類似，葉子節(jié)點存儲的是對應字段的值 + 行號。