一. 前言
1. 說明
我們平時所說的：聚集索引(主鍵索引)，次要索引，覆寫索引，複合索引，字首索引，唯一索引在MySQL5.7和 8.0版本預設都是使用B+Tree索引，除此之外還有 Hash索引。至于MySQL5.7之前版本，這裡就不過多探究了。
學習各種資料結構圖解網站：https://www.cs.usfca.edu/~galles/visualization/Algorithms.html (推薦)
2. 有索引和沒索引的差別
下圖，左邊表格是沒有索引，右邊是二叉樹索引，以col2為索引列.
PS: 在右邊二叉樹的結構中，每個節點都是 key-value 鍵值對的形式。key：col2所在行在磁盤檔案中的位址指針（比如 34 所在行，通過key中存儲 0x07 這個指針就能找到是第1行），value：就是col2的值。
分析下面SQL語句
select * from t where col2 = 89；
(1). 左邊沒有索引，搜尋col2=89需要從上往下搜尋， 6次 才能找到，也就是 6次回表操作（6次IO）。
(2). 右邊是二叉樹索引，搜尋col2=89搜尋 2次 就可以找到，也就是 2次回表操作（2次IO），性能提升明顯。
二. 二叉樹、紅黑樹、Hash
1. 二叉樹
(1). 二叉樹的特點
左子節點值 < 節點值；右子節點值 > 節點值；當資料量非常大時，要查找的資料又非常靠後，和沒有索引相比，那麼二叉樹結構的查詢優勢将非常明顯。
(2). 存在的問題
如下圖，可以看出，二叉樹出現單邊增長時，二叉樹變成了“鍊”，這樣查找一個數的時候，速度并沒有得到很大的優化。
2. 紅黑樹
(1). 特點
A. 節點是紅色或者黑色
B. 根節點是黑色
C. 每個葉子的節點都是黑色的空節點（NULL）
D. 每個紅色節點的兩個子節點都是黑色的。
E. 從任意節點到其每個葉子的所有路徑都包含相同的黑色節點。
(2). 存在的問題
紅黑樹雖然和二叉樹相比，一定程度上緩解了單邊過長的問題，但是它依舊存儲高度問題。
假設現在資料量有100萬，那麼紅黑樹的高度大概為 100,0000 = 2^n， n大概為 20。那麼，至少要20次的磁盤IO，這樣，性能将很受影響。如果資料量更大，IO次數更多，性能損耗更大。是以紅黑樹依舊不是最佳方案。
(3). 思考：針對上面的紅黑樹結構，我們能否優化一下呢？
上述紅黑樹預設一個節點就存了一個 (索引+磁盤位址)，我們設想一個節點存多個 （索引+磁盤位址），這樣就可以降低紅黑樹的高度了。 實際上我們設想的這種結構就是 B-Tree。
3. Hash
(1). 原理
A. 事先将索引通過 hash算法後得到的hash值(即磁盤檔案指針）存到hash表中。
B. 在進行查詢時，将索引通過hash算法，得到hash值，與hash表中的hash值比對。通過磁盤檔案指針，隻要一次磁盤IO就能找到要的值。
例如：
在第一個表中，要查找col=6的值。hash(6) 得到值，比對hash表，就能得到89。性能非常高。
(2). 存在的問題
但是hash表索引存在問題，如果要查詢 帶範圍的條件時，hash索引就歇菜了。
select *from t where col1>=6;
更多C++背景開發技術點知識内容包括C/C++，Linux，Nginx，ZeroMQ，MySQL，Redis，MongoDB，ZK，流媒體，音視訊開發，Linux核心，TCP/IP，協程，DPDK多個進階知識點。
C/C++背景開發架構師免費學習位址：C/C++Linux鏈嶅姟鍣ㄥ紑鍙�/鍚庡彴鏋舵瀯甯堛€愰浂澹版暀鑲層€�-瀛︿範瑙嗛鏁欑▼-鑵捐璇懼爞
【文章福利】另外還整理一些C++背景開發架構師 相關學習資料，面試題，教學視訊，以及學習路線圖，免費分享有需要的可以點選 「連結」 免費領取
三. B-Tree 和 B+Tree
1. B-Tree
(1). 特點
B-Tree索引能很好解決紅黑樹中遺留的高度問題，B-Tree 是一種平衡的多路查找（又稱排序）樹，在檔案系統中和資料庫系統有所應用，主要用作檔案的索引，其中的B就表示平衡（Balance）。
為了描述B-Tree，首先定義一條資料記錄為一個二進制組 [key, data]，key為記錄的鍵值key，對于不同資料記錄，key是互不相同的；data為資料記錄除以key外的資料 （這裡指的是聚集索引）。那麼B-Tree是滿足下列條件的資料結構：
A. d 為大于1的一個正整數，稱為BTree的度；
B. h為一個正整數，稱為BTree的高度；
C. key和指針互相間隔，節點兩端是指針；
D. 葉子節點具有相同的深度，葉子節點的指針為空，節點中資料索引(下圖中的key)從左往右遞增排列。
說明：下面的圖都是以主鍵索引為例來畫圖，至于非主鍵索引(非聚集索引)，無非就是data裡存的内容不同，詳細對比見後面章節。
圖1：
圖2：
(2). 分析
模拟下查找key為29的data的過程：
A、根據根結點指針讀取檔案目錄的根磁盤塊1。【磁盤IO操作第1次】
B、磁盤塊1存儲17，35和三個指針資料。我們發現17<29<35，是以我們找到指針p2。
C、根據p2指針，我們定位并讀取磁盤塊3。【磁盤IO操作2次】
D、磁盤塊3存儲26，30和三個指針資料。我們發現26<29<30，是以我們找到指針p2。
E、根據p2指針，我們定位并讀取磁盤塊8。【磁盤IO操作3次】
F、磁盤塊8中存儲28，29。我們找到29，擷取29所對應的資料data。
(3). 存在問題
A. 比如，下面查詢語句，那麼不但需要葉子節點>20的值，也需要非葉子節點在右邊節點的值。即下圖畫圈的兩部分， B-Tree似乎在範圍查找沒有更簡便的方法，為了解決這一問題。我們可以用B+Tree。
select *from t where col1 > 20;
B. 深度問題
從圖上可以看到，每個節點中不僅包含資料的key值，還有data值。而每一個節點的存儲空間是有限的(mysql預設設定一個節點的大小為16K)，如果data中存放的資料較大時，将會導緻每個節點（即一個頁）能存儲的key的數量（索引的數量）很小，是以當資料量很多，且每行資料量很大的時候，同樣會導緻B-Tree的深度較大，增大查詢時的磁盤I/O次數，進而影響查詢效率。是以引入B+Tree
2. B+Tree
(1). 特點
B+Tree是在B-Tree基礎上的一種優化，使其更适合實作外存儲索引結構。在B+Tree中，所有資料記錄節點都是按照鍵值大小順序存放在同一層的葉子節點上，而非葉子節點上隻存儲key值資訊，這樣可以大大加大每個節點存儲的key值數量，降低B+Tree的高度。
A. 非葉子節點不存儲data，隻存儲索引，可以存放更多索引。
B. 葉子節點不存儲指針。
C. 順序通路指針，提高區間通路性能。
D. 非葉子節點中的索引最終還是會在葉子節點上存儲一份，也就是葉子節點會包含非葉子節點上的所有索引。
E. 一個父節點，它的左側子節點都小于父節點的值，右側的子節點都大于等于父節點的值。
F. 每一層節點從左往右都是遞增排列，無論是數值型還是字元型。
注：MySQL索引預設的存儲結構使用的就是B+Tree。
圖1：
圖2：
剖析：如上圖，在葉子節點上注意是MySQL已經有成雙向箭頭（原生B+Tree是單向的），而且從左到右是遞增順序的，是以很好的解決了 > 和 < 這類查找問題。
(2). 分析
假如：以一個高度為3的B+Tree為例，B+Tree的表都存滿了，能存儲多少資料？
首先，檢視MySQL預設一個節點頁的大小：
SHOW GLOBAL STATUS like 'Innodb_page_size';
如下圖：大小為16K。
然後，假設主鍵Id為bigint類型，那麼長度就是8B，指針在Innodb源碼中大小為6B，是以一共就是14B，再假設最後一層，存放的資料data為1k 大小（能存很多内容了），那麼
A. 第一層最大節點數為： 16k / (8B + 6B) = 1170 (個)；
B. 第二層最大節點數也應為：1170個；
C. 第三層最大節點數為：16k / 1k = 16 (個)。
則，一張B+Tree的表最多存放 1170 * 1170 * 16 = 21902400 ≈ 2千萬。是以，通過分析，我們可以得出，B+Tree結構的表可以容納千萬資料量的查詢。而且一般來說，MySQL會把 B+Tree 根節點放在記憶體中，那隻需要兩次磁盤IO（第二層1次，第三層1次）就行。
(3). 擴充
資料庫中的B+Tree索引可以分為聚集索引（clustered index，也叫主鍵索引）和輔助索引（secondary index，也叫非聚集索引）。
上面的B+Tree示例圖在資料庫中的實作對應的是聚集索引，聚集索引的B+Tree中的葉子節點存放的是整張表的行記錄資料(除主鍵以外的所有資料)，輔助索引與聚集索引的差別在于輔助索引的葉子節點并不包含行記錄的全部資料，而是存儲相應行資料的對應的聚集索引鍵，即主鍵。當通過輔助索引來查詢資料時，InnoDB存儲引擎會周遊輔助索引找到主鍵，然後再通過主鍵在聚集索引中找到完整的行記錄資料。
四. 深究索引在B+Tree上的存儲
說明：下面的介紹均是指InnoDB存儲引擎B+Tree
1. 聚集索引
聚集索引也叫主鍵索引，葉子節點中的data存儲的是該主鍵對應整行資料，通常B+Tree的高度為3，也就是有三層節點，MySQL會把B+Tree第一層也就是根節點放在記憶體中，我們根據主鍵索引查資料，隻需要兩次磁盤IO（第二層1次，第三次1次）即可。尋址過程類似上面B-Tree那個尋址步驟。
2. 非聚集索引
非聚集索引也叫輔助索引，葉子節點中的data存儲的該索引對應的該行資料的主鍵值，是以非聚集索引的尋址過程分兩種情況：
(1). 非聚集索引已經索引覆寫了，那麼隻需要周遊這非聚集索引這一個B+Tree即可，按照上面的分析，需要兩次磁盤IO即可（mysql會把根節點放到記憶體中）。
(2). 非聚集索引不能索引覆寫，那麼先需要在非聚集索引這個B+Tree上兩次IO找到該行資料對應的主鍵值，然後拿着主鍵去 聚集索引的B+Tree上找對應的其它資料。相比第一種情況IO次數要多，是以我們通常喜歡索引覆寫。
下圖表示非聚集索引不能索引覆寫的情況：
右側的輔助索引先拿到主鍵值5，然後去左側的主鍵索引中尋址，最後可以得到整行内容。
3. 聯合索引
假設有一張表T1，有id、x1、x2、x3、x4字段，id上有主鍵索引，給x1、x2、x3添加聯合索引，如下圖：
剖析：
(1). 上圖聯合索引的key中存儲x1-x2-x3三個值，存儲順序從左往右依次遞增，
先比較x1，如：10002<10004，
如果x1相同，在比較x2，如 Assistant < Engineer
如果x2相同，再比較x3，如 1997-08-03 < 2001-09-03
(2). 如果查找x1 x2 x3，在非聚集索引這個B+Tree直接就可以從key中拿到，如果還要查找x4，則需要拿到data中存儲的主鍵值，然後再去聚集索引中查找。（這就是為什麼首選覆寫索引的原因）
4. 靈魂拷問
(1). 為什麼InnoDB表必須有主鍵，并且推薦使用整型的自增主鍵？
A. 為什麼要有主鍵？
mysql底層就是用B+Tree維護的，而B+Tree的結構就決定了必須有主鍵才能建構B+Tree樹這個結構。每個表在磁盤上，是單獨的一個檔案。索引和資料都在其中，檔案是按照主鍵索引組織的一個B+TREE結構。假如沒有定義主鍵，MySQL會在挑選能唯一辨別的字段作為索引；假如找不到，會生成一個預設的隐藏列作為主鍵列。
B. 為什麼用整型主鍵？
假如使用類似 UUID 的字元串作為主鍵，那麼在查找時，需要比較兩個主鍵是否相同，這是一個相比整型比較 非常耗時的過程。需要一個字元，一個字元的比較，自然比較慢。
C. 為什麼用自增主鍵？
① 後面的主鍵索引總是大于前面的主鍵索引，在做範圍查詢時，非常友善找到需要的資料。
② 在添加的過程中，因為是自增的，每次添加都是在後面插入，樹分裂的機會小；而UUID大小不确定，分裂機會大，需要重新平衡樹結構，性能損耗大。
(2). 為什麼非主鍵索引結構葉子節點存儲的是主鍵值，而不是全部資料？
① 節省空間：指向主鍵的節點，不用再存儲一份相同的資料；（否則的話，如果建立多個非主鍵索引，每個上面都存儲的完整資料，非常占用空間）
② 資料一緻性：如果修改索引15 的資料，那隻要修改主鍵的 data，而如果非主鍵的data也存一份的話，那得修改兩份，這樣就涉及到事務一緻性的問題，耗時，性能低。
(3). 為什麼希望使用覆寫索引？
如果非聚集索引中能索引覆寫，那麼我們隻需要周遊非聚集索引這個B+Tree從其中的Key裡拿到索引值就可，隻需要周遊一棵樹。 如果不能索引覆寫，需要先周遊非聚集索引，然後拿到data中存儲的主鍵值，再去聚集索引中周遊查找資料，相比索引覆寫的話，IO次數更多，性能相對低。
五. MyISAM和InnoDB的索引結構對比
1. MyISAM下索引結構
MyISAM索引檔案和資料檔案是分開的(非聚集)，存儲引擎在磁盤中檔案有三個，
一個是 .frm 檔案(資料表定義)，
一個是 .MYI(索引)，
一個是 .MYD(實際資料，存儲的是一整行的資料，包括索引值)。
MY檔案是B+Tree為底層組織的檔案。
剖析： 比如查找 49，那麼在 .MYI 中找到 49對應的磁盤指針 0x49，根據 0x49 去 .MYD找到實際的資料内容data。
注：在MyISAM存儲引擎中，無論是主鍵索引還是非主鍵索引，B+Tree中葉子結點中的data存儲的都是該行資料對應的磁盤指針，根據指針再去拿資料。
2. InnoDB索引結構
InnoDB存儲引擎它的表資料檔案本身就是按 B+Tree 組織的一個索引檔案。不同于MyISAM存儲引擎是，資料不分離。
一個frm檔案存儲資料表定義，一個ibd檔案存放的索引和實際資料。
如下圖一，為聚集索引，找到49的索引之後，資料就在該節點，不必像MyISAM存儲引擎那樣，需要根據磁盤指針到另一個檔案中取資料。性能比MyISAM高。
原文連結：第二節：MySQL索引的底層資料結構原理剖析(二叉樹、 紅黑樹、Hash、B-Tree、B+Tree)