文章目錄
一、索引的本質
二、索引的資料結構
1. Hash表
2. 二叉樹
3. 紅黑樹
4. B-Tree
5. B+Tree(B-Tree變種)
三、存儲引擎的實作
1. MyISAM存儲引擎實作
2. InnoDB存儲引擎實作
一、索引的本質
索引是幫助MySQL高效擷取資料的排好序的一種資料結構。
二、索引的資料結構
這塊隻是一筆帶過,想要深入了解的小夥伴——點我跳轉(關于數算)。
1. Hash表
不支援範圍查找很少使用
2. 二叉樹
左邊子節點資料小于父節點資料,右邊子節點資料大于父節點資料,遞增資料會導緻連結清單
3. 紅黑樹
二叉平衡樹,高度不可控,數量為大樹越高
4. B-Tree
- 葉節點具有相同的深度,葉節點的指針為空
- 所有索引元素不重複
- 葉節點的資料索引從左至右遞增排列
5. B+Tree(B-Tree變種)
- 非葉子節點不存儲data,隻存儲索引(備援索引),可以放更多的索引
- 葉子節點包含所有索引字段
- 葉子節點有雙向指針連結(首尾子節點還通過指針連接配接),提高區間通路的性能,範圍查找
三、存儲引擎的實作
1. MyISAM存儲引擎實作
- MyISAM索引檔案和資料檔案是分離的(非聚集)
- frm檔案:存儲這張表的表結構
- MYD檔案:存儲這張表的所有資料行
- MYI檔案:存儲這張表的索引字段
2. InnoDB存儲引擎實作
- frm檔案:存儲這張表的表結構
- ibd檔案:存儲這張表的所有資料行和索引字段
- 表資料ibd檔案本身就是按照B+Tree組織的一個索引結構檔案
- 聚集索引-葉節點包含了完整的資料記錄
為什麼Innodb表必須包含主鍵,且推薦使用整型的自增主鍵?
- 顯式設定主鍵的話,會作為聚集索引。沒有會預設建立一列主鍵rowId聚集索引
- 自增主鍵會按照插入資料順序排列,自動有序
為什麼非主鍵索引結構葉子節點存儲的都是主鍵值?
- 節省存儲空間: 通過非主鍵索引擷取到主鍵值,然後再去主鍵索引的B+樹資料結構中找到對應的行資料。
- 一緻性:如果非主鍵索引結構葉子節點也儲存一份data資料,修改資料是,需要修改非主鍵索引和主鍵索引,需要資料同步,會存在一緻性問題。