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

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

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

• B+樹索引結(jié)構(gòu)的推導(dǎo)過程

  1. 數(shù)據(jù)行結(jié)構(gòu)--單向鏈表史汗；
  2. 數(shù)據(jù)頁結(jié)構(gòu)--通過頁目錄使用二分法快速找到目標(biāo)行琼掠；
  3. 目錄項--多個數(shù)據(jù)頁時如何定位到目標(biāo)行所在的數(shù)據(jù)頁；
  4. B+樹索引--目錄項太多停撞，大目錄嵌套小目錄瓷蛙，就形成了B+樹

• 聚簇索引

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

• 二級索引結(jié)構(gòu)和特點

• MyISAM 索引結(jié)構(gòu)和特點

B+樹索引結(jié)構(gòu)的推導(dǎo)過程

1. 數(shù)據(jù)行結(jié)構(gòu)

InnoDB行--單向鏈表

2. 數(shù)據(jù)頁結(jié)構(gòu)

一個數(shù)據(jù)頁默認(rèn)16KB，可以存放很多行數(shù)據(jù)道宅，那如何在一個數(shù)據(jù)頁中快速找到一行數(shù)據(jù)呢食听？在數(shù)據(jù)頁中有個叫“頁目錄”的結(jié)構(gòu)：

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

3. 目錄項

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

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

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

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

4. B+樹索引

如上圖幢尚，如果一張表的行數(shù)很多玛臂，勢必就會有很多數(shù)據(jù)頁压怠，那么就可能出現(xiàn)一個頁存不下所有“目錄項紀(jì)錄”的情況芥映，所以可能會有很多個“目錄項數(shù)據(jù)頁”溅话，那又怎么快速知道應(yīng)該在哪個“目錄項數(shù)據(jù)頁”上查找目標(biāo)數(shù)據(jù)在哪個“數(shù)據(jù)頁”上呢崇败？

這就是 B+樹索引結(jié)構(gòu)：

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

5. 時間復(fù)雜度

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

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

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

假設(shè)每行數(shù)據(jù)大約1K水醋，innodb 數(shù)據(jù)頁大小默認(rèn)為16K旗笔，也就是大約每個葉子結(jié)點可以存放16條用戶記錄，即 m=16拄踪；
主鍵ID一般為bigint 類型蝇恶，占 8 字節(jié)，指針大小在 InnoDB 源碼中設(shè)置為 6 字節(jié)惶桐，這樣一共 14 字節(jié)撮弧，所以每個非葉子結(jié)點大約可以存放 16384/14=1170 條目錄項紀(jì)錄潘懊，即n=1170；
要想控制樹高為3贿衍，則表的總行數(shù)應(yīng)該是：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è)務(wù)含義，本身不會被更新弟蚀，所以記錄基本不會挪動在數(shù)據(jù)頁中的位置蚤霞。

二級索引

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

MyISAM

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

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