1、概述
MySQL中，當我們發現某個sql的執行時間很長時，最先想到的就是給表加索引，加了索引之后，查詢性能就會有顯著的提升。
為了知其所以然，那么只有去了解MySQL的底層儲存結構和索引的查詢算法，只有這樣才能寫出性能更好的sql和知道如何去優化一個慢SQL。
下文會簡單的介紹MySQL的底層數據結構與算法。
2、數據結構與算法演進
任何一個好的產品，都是不斷的優化才能到今天這么成熟和好用。MySQL也是一樣，它也考慮過存儲結構的優化過程。
后文都以磁盤中存儲了8條表數據，并且磁盤位置索引以index代指、磁盤存放的表數據以value代指為例：
(index, value)
(1, '{id: 1, name: xm}') // 磁盤索引1的位置，存儲了一條表數據{id: 1, name: xm}
(2, '{id: 2, name: df}')
(3, '{id: 3, name: tr}')
(4, '{id: 4, name: ui}')
(5, '{id: 5, name: ue}')
(6, '{id: 6, name: gh}')
(7, '{id: 7, name: re}')
(8, '{id: 8, name: uu}')
數據說明
如果我要讀取id為3的數據，按照順序全量遍歷的流程：
1、先把磁盤索引index為1的磁盤數據加載到內存，然后發現id不等于3
2、然后把磁盤索引index為2的磁盤數據加載到內存，然后發現id不等于3
3、最后把磁盤索引index為3的磁盤數據加載到內存，才發現這個id等于3，然后返回
以上總共進行了3次磁盤IO。(一次磁盤IO比內存IO耗時多很多)
2.1、二叉樹
為了方便檢索，大家很容易想到的就是先排好序之后，然后進行二分查找，這樣效率相比于全量遍歷每次就減少一半的范圍，即查詢復雜度就降為了O(logN)。
2.1.1、存儲結構示例
當我們表id以1、3、2、4、8、6、7、5的順序存入，就會變成下面這樣：
插入id=1：作為根節點，磁盤索引1，name=xm
插入id=3：比1大，放在1的右子樹，磁盤索引3，name=tr
插入id=2：比1大，比3小，放在3的左子樹，磁盤索引2，name=df
插入id=4：比1、3都大，放在3的右子樹，磁盤索引4，name=ui
插入id=8：比1、3、4都大，放在4的右子樹，磁盤索引8，name=uu
插入id=6：比1、3、4大，比8小，放在8的左子樹，磁盤索引6，name=gh
插入id=7：比1、3、4、6大，比8小，放在6的右子樹，磁盤索引7，name=re
插入id=5：比1、3、4大，比6、8小，放在6的左子樹，磁盤索引5，name=ueindex=1(id:1, name:xm)\index=3(id:3, name:tr)/ \index=2(id:2, name:df) index=4(id:4, name:ui)\index=8(id:8, name:uu)/index=6(id:6, name:gh)/ \index=5(id:5, name:ue) index=7(id:7, name:re)
如果要檢索id為8的數據，那么僅需要檢索4次即可。如果是從頭開始遍歷那么就會查找8次，這樣分析下來，使用二叉樹比使用全量順序遍歷節省了很多時間。
但是這只是常規的情況，如果插入是這樣順序插入：
插入id=1：作為根節點，磁盤索引1，name=xm
插入id=2：比1大，放在1的右子樹，磁盤索引2，name=df
插入id=3：比1、2都大，放在2的右子樹，磁盤索引3，name=tr
插入id=4：比1、2、3都大，放在3的右子樹，磁盤索引4，name=ui
插入id=5：比前面所有節點都大，放在4的右子樹，磁盤索引5，name=ue
插入id=6：比前面所有節點都大，放在5的右子樹，磁盤索引6，name=gh
插入id=7：比前面所有節點都大，放在6的右子樹，磁盤索引7，name=re
插入id=8：比前面所有節點都大，放在7的右子樹，磁盤索引8，name=uuindex=1(id:1, name:xm)\index=2(id:2, name:df)\index=3(id:3, name:tr)\index=4(id:4, name:ui)\index=5(id:5, name:ue)\index=6(id:6, name:gh)\index=7(id:7, name:re)\index=8(id:8, name:uu)
這樣的話，會導致查詢id為8的記錄時，依舊要查詢8次，也就跟全量遍歷沒區別了。可以試想一下，單表如果使用自增ID的話，那么查詢一次的耗時將每次都是最長路徑。因此MySQL沒有選擇此數據結構。
2.2、紅黑樹(二叉平衡樹)
普通的二叉樹會有單邊子樹無限增長導致成為單鏈表的缺陷，紅黑樹就是為了解決這個問題的，它檢測到左右子樹的層級相差時會左右自動平衡。
2.2.1、存儲結構示例
以上面的1~8順序插入為例：
│ 步驟1: 插入id=1
│ index=1(id:1, name:xm) [BLACK]
│ - 插入第一個節點，直接作為根節點，根節點必須是黑色
│
│ 步驟2: 插入id=2
│ index=1(id:1, name:xm) [BLACK]
│ \
│ index=2(id:2, name:df) [RED]
│ - 2 > 1，插入到1的右子樹，新節點初始為紅色
│
│ 步驟3: 插入id=3
│ index=1(id:1, name:xm) [BLACK]
│ \
│ index=2(id:2, name:df) [RED]
│ \
│ index=3(id:3, name:tr) [RED]
│ - 違反性質：連續兩個紅色節點(2和3)
│ - 修復操作：左旋轉1節點，重新著色
│
│ 修復后：
│ index=2(id:2, name:df) [BLACK]
│ / \
│ index=1(id:1, name:xm) index=3(id:3, name:tr)
│ [RED] [RED]
│
│ 步驟4-8: 繼續插入id=4,5,6,7,8
│ 經過多次旋轉和重新著色操作后，最終達到平衡狀態：
│
│ index=4(id:4, name:ui) [BLACK]
│ / \
│ index=2(id:2, name:df) index=6(id:6, name:gh)
│ [BLACK] [BLACK]
│ / \ / \
│ index=1 index=3 index=5 index=7
│ (id:1,xm) (id:3,tr) (id:5,ue) (id:7,re)
│ [RED] [RED] [RED] [RED]
│ \
│ index=8(id:8,uu)
│ [BLACK]
│
│ 關鍵修復操作類型：
│ 1. 左旋轉：當右子樹過高時，將右子節點提升為新的根節點
│ 2. 右旋轉：當左子樹過高時，將左子節點提升為新的根節點
│ 3. 重新著色：調整節點顏色以滿足紅黑樹性質
│ 4. 復合操作：結合旋轉和重新著色來維護平衡 index=4(id:4, name:ui) [BLACK]/ \index=2(id:2, name:df) index=6(id:6, name:gh)[BLACK] [BLACK] / \ / \
index=1 index=3 index=5 index=7
(id:1,xm) (id:3,tr) (id:5,ue) (id:7,re)
[RED] [RED] [RED] [RED]\index=8(id:8,uu)[BLACK]
這樣每次在插入時平衡后，就能穩定查詢復雜度在O(logN)。
但是這里列舉的只是8條數據，如果實際存儲了上百萬條數據，樹的層級就會非常高了，依舊捉襟見肘，因此MySQL依舊沒有使用這個存儲結構。
2.3、B樹
既然節點越多，二叉樹的高度就越高。那么有沒有一種辦法可以讓樹的高度降下來呢？
B樹就是解決這個問題的：
- 內存IO肯定比磁盤IO快幾個數量級，那么在一個樹的節點中放更多的磁盤索引就可以把節點個數縮減下來
- B樹就是這么干的， 一個節點中存儲不止一個（id， 磁盤索引index）數據，這樣數據的高度就降下來了
- 到底一個節點存了多少個（id, 磁盤索引）呢？這就跟計算機的數據頁概念有關，計算機把數據從磁盤加載到內存，是按數據頁為單位批量加載的
- 一個頁16KB數據，如果按照一個普通二叉樹節點14B（bigint 8 + 磁盤地址 6）來算大約可以存儲1170個普通節點!
2.3.1、存儲結構示例
僅按照一個節點存儲3個：
│ 根節點 │
│ [index=2(id:2,df) | index=4(id:4,ui) | index=6(id:6,gh)] │
│ / | | \ │
│ [index=1] [index=3] [index=5] [index=7|index=8] │
│ (id:1,xm) (id:3,tr) (id:5,ue) (id:7,re|id:8,uu)
可以看到，在一個節點存三個索引的情況下，僅需要2層就存下了8個數據。 當查詢id為8 的數據時，僅需要花費磁盤IO2次。
但是這依舊不是MySQL如今的存儲數據結構：
- B樹的節點中存儲了磁盤索引+id數據，好像只需要在非葉子節點存儲id數據，葉子節點存儲磁盤索引就可以了，這樣可以讓一個B樹節點存儲更多的內容。
- sql語句中還有范圍查找，這個B樹結構貌似也不能很好的支持。
2.4、B+樹（B樹升級版）
MySQL如今就是采用的這個數據結構
1、為了讓B樹一個節點存儲的更多，直接將非葉子節點僅存儲索引id，然后葉子節點存儲索引id+磁盤索引index
2、為了支持范圍查找，直接讓葉子節點支持前后的磁盤索引指針，這樣就能方便的向前或向后查找。
2.4.1、存儲結構示例
僅按照一個節點存儲3個：
│ 內部節點
│ [id=3 | id=6]
│ / | \
│ 葉子節點1 葉子節點2 葉子節點3
│ [id=1|id=2] [id=3|id=4|id=5] [id=6|id=7|id=8]
│ (index=1,name:xm| (index=3,name:tr| (index=6,name:gh|
│ index=2,name:df) index=4,name:ui| index=7,name:re|
│ index=5,name:ue) index=8,name:uu)
│
│ 葉子節點鏈式指針連接：
│ ┌─────────────┐ next ┌─────────────┐ next ┌─────────────┐
│ │ 葉子節點1 │ ────────→ │ 葉子節點2 │ ────────→ │ 葉子節點3 │
│ │ [id=1|id=2] │ ←──────── │[id=3|id=4|id=5]│ ←──────── │[id=6|id=7|id=8]│
│ └─────────────┘ prev └─────────────┘ prev └─────────────┘
│
特別說明
1、葉子節點中，除了了放索引id之外，不一定放的就是表數據本身（index=xx,name:xx），這個跟存儲引擎有關。
2、如果是InnoDB存儲引擎（聚簇索引）: 葉子節點中索引和表數據是直接放在一起的，也就是本示例。
3、如果是MyISAM存儲引擎（非聚簇索引）：葉子節點中僅放索引 和 磁盤索引index（磁盤地址）。
4、按照常用的InnoDB存儲引擎來算，一個表數據1KB占用，那么樹的高度為3時，可以存儲上千萬級別數據（1170 x 1170 x 16）
5、另外值得一提的是，一般來說MySQL會把根節點常駐內存(InnoDB的Buffer Pool)，高版本的MySQL會把非葉子節點常駐內存，實際查詢會比想象的更快。
│ 1. **InnoDB Buffer Pool 緩存機制**：
│
│ ┌─────────────────┐
│ │ Buffer Pool │ ← MySQL內存緩存區域
│ │ (默認128MB) │
│ └─────────────────┘
│ │
│ ├─ 索引頁緩存 (Index Pages)
│ ├─ 數據頁緩存 (Data Pages)
│ └─ 日志緩存等其他
│
│ 2. **B+樹節點緩存優先級**：
│
│ 優先級從高到低：
│ ┌────────────────────────────────────────────────────────────┐
│ │ 1. 根節點 (Root Node) - 幾乎100%常駐內存 │
│ │ 2. 第一層非葉子節點 - 高頻訪問，優先緩存 │
│ │ 3. 第二層非葉子節點 - 根據訪問頻率緩存 │
│ │ 4. 葉子節點 (Leaf Nodes) - 根據LRU算法緩存 │
│ └────────────────────────────────────────────────────────────┘
│
│ 3. **實際查詢性能分析**：
│
│ 假設一個4層B+樹索引：
│ ┌─────────────────┐
│ │ 根節點 │ ← 內存中 (0次磁盤I/O)
│ │ [緩存100%] │
│ └─────────────────┘
│ │
│ ┌─────────────────┐
│ │ 第1層非葉子節點 │ ← 內存中 (0次磁盤I/O)
│ │ [緩存90%+] │
│ └─────────────────┘
│ │
│ ┌─────────────────┐
│ │ 第2層非葉子節點 │ ← 可能在內存 (0-1次磁盤I/O)
│ │ [緩存60%+] │
│ └─────────────────┘
│ │
│ ┌─────────────────┐
│ │ 葉子節點 │ ← 可能需要磁盤讀取 (0-1次磁盤I/O)
│ │ [緩存視情況] │
│ └─────────────────┘
│
│ 4. **MySQL版本演進的優化**：
│
│ MySQL 5.1及以前：
│ - 主要緩存熱點數據頁
│ - 根節點通常在內存，但不保證
│
│ MySQL 5.5-5.7：
│ - InnoDB成為默認引擎
│ - 改進Buffer Pool算法
│ - 更智能的索引頁預加載
│
│ MySQL 8.0+：
│ - 自適應哈希索引 (Adaptive Hash Index)
│ - 更大默認Buffer Pool
│ - 智能預讀算法
│ - 壓縮頁緩存
│
│ 5. **實際性能提升效果**：
│
│ 理論磁盤I/O次數：4次 (4層樹)
│ 實際磁盤I/O次數：1-2次 (緩存優化后)
│ 性能提升：50-75%
│
│ 查詢時間對比：
│ - 無緩存：4次磁盤I/O ≈ 40ms (假設10ms/次)
│ - 有緩存：1次磁盤I/O ≈ 10ms
│
│ 6. **相關配置參數**：
│
│ innodb_buffer_pool_size - Buffer Pool大小
│ innodb_old_blocks_pct - LRU算法參數
│ innodb_read_ahead_threshold - 預讀閾值
│ innodb_adaptive_hash_index - 自適應哈希索引
│
│ 7. **驗證方法**：
│
│ SHOW ENGINE INNODB STATUS; -- 查看Buffer Pool命中率
│ SELECT * FROM INFORMATION_SCHEMA.INNODB_BUFFER_PAGE; -- 查看緩存頁面
3、拓展
3.1、MySQL表實際存儲文件
1、如果是InnoDB存儲引擎（聚簇索引），僅會存儲在表名.frm（存儲表結構）、表名.idb（存儲索引 + 表數據）中。
2、如果是MyISA存儲引擎（非聚簇索引），會存儲在表名.frm（存儲表結構）、表名.MYD（存儲表數據）、表名.MYI（存儲表索引）中。
由上可知，存儲引擎是以表為載體的。（一個庫里面可以存在不同存儲引擎的表）
特別說明
1、InnoDB的主鍵索引才是聚簇索引，因為非主鍵索引查詢全量記錄時，都需要回表到主鍵索引二次查詢，因此非主鍵索引也就不算聚簇索引了。
3.2、MySQL表隱藏列
從上面了解到，表數據存儲，肯定是要設定一個索引的。如果在建表是如果不設置主鍵和索引會發現什么？
1、首先MySQL自己會逐列去檢索是否每行是唯一的，如果是，則直接內部定為主鍵索引并維護。
2、如果找不到唯一的列，MySQL就會自己加個隱藏列，也就是列編號來維護主鍵索引。
由上可知，在建表時，建議制定主鍵列，避免MySQL額外維護主鍵的開銷。當然，推薦使用整型自增的列作為主鍵更好（整型比字符串占用的空間更小 且方便比對 且方便范圍查詢 且更易于讓索引維護有序性）。
3.3、Hash索引的優與劣
1、優點：僅需要進行一次Hash算法就可以定位到hash槽，比遍歷B樹的層級快。
2、缺點：1> 有Hash碰撞的情況，那是hash槽對應的鏈表是單鏈表，復雜度不穩定。 2> hash很難支持范圍查找。
由上可知，在表存儲場景下，弊大于利。
3.4、二級索引存儲內容
InnoDB存儲引擎：
1、子節點僅會存儲主鍵索引（一般就是ID）。 – 因此二級索引需要拿到全量表字段數據時需要回表查詢
2、這樣做的原因：1> 維護主鍵與二級索引直接的一致性。 2> 節省磁盤空間。
MyISA存儲引擎：
1、主鍵與二級索引的子節點都是存儲的磁盤索引（磁盤地址）。
上面2個之所以有差異，是因為它們本身的設計就不一樣。InnoDB的全數據都是存在主鍵葉子節點的，因此只能回表。 但是MyISA的主鍵索引是直接存磁盤索引（磁盤地址）的，因此其二級索引頁指向磁盤索引。
3.5、二級索引之聯合索引的結構
1、聯合索引和主鍵索引的差別：
- 主鍵索引的字段僅有一個（一般是id）
- 聯合索引的字段不止一個（例如：age, name2個及以上字段同時作為索引）
2、聯合索引的比較規則：跟字符串比較類似，先比較age，如果age一樣，再比較name。
3、結構示例：
│ 內部節點
│ [(age=22,name=tr) | (age=28,name=gh)]
│ / | \
│ 葉子節點1 葉子節點2 葉子節點3
│ [(age=18,name=xm)| [(age=22,name=tr)| [(age=28,name=gh)|
│ (age=20,name=df)] (age=22,name=ui)| (age=30,name=re)|
│ (age=25,name=ue)] (age=32,name=uu)]
│ ↓ ↓ ↓
│ [id=1|id=2] [id=3|id=4|id=5] [id=6|id=7|id=8]
由上可知，“最左前綴匹配”索引優化的由來。
暑期實訓優秀作品（2）：智慧城市西安與一帶一路)
)
