Index 索引

by Aaron • 10/22/2022, 8:51:42 AM

Table of Content

• 什麼是索引
  • 優缺點
  • B+tree
  • 為何不用紅黑樹
• 索引分類
  • 根據索引字段分類
  • 根據是否在主鍵上進行索引
  • 根據物理儲存分類
  • 其他
• 索引缺點
• 優化索引
• 索引如何失效
• 使用場景

什麼是索引

幫助 storage engine 快速獲取資料的資料結構 在MySQL 多使用 B+tree

優缺點

優點：

1. 減少硬碟 IO 次數, 增加搜尋資料的速度
2. 唯一索引可以確保數據的唯一性
3. group by 和 sort by 可以大幅度增加效率, 降低 CPU 的消耗

• 缺點：
  1. 需要多花空間去儲存 index 的資料結構
  2. 建立和維護該 index 需要花費額外的時間，資料增加時, 消耗的時間也會增加, 降低更改資料的速度

B+tree

find 8
step1:  1<= 8 < 18
step2:  6 <= 8 < 12
steps:  6, "8" 10
finish

              "1",        18,         36
             /          |
           /            |
         /              |
   1, "6", 12         18, 24, 30
  /    |    \         /    |   \
1      6    12       18   24      ..........
3     "8"    15      20   26
5     10    17       22   28

為何不用紅黑樹

• B+Tree 的查找次數較少: 平衡樹的複雜度約等於樹高 log_d^N, 而紅黑樹的 d = 2, B+ Tree 的 d 則比 2 大很多

索引分類

根據索引 attribute 數量分類

• 單個 attribute： 單直索引

  EX: ALTER TABLE member ADD INDEX email_index (email);

• 多個 attribute： 複合索引

  EX: ALTER TABLE member ADD INDEX email_tel_index (email, tel);

根據是否在主鍵上進行索引

• 在主鍵上進行索引： 主鍵索引

  1. 根據主鍵進行索引，若沒有設定主鍵，MySQL 會自動生成一個隱藏的字段作為主鍵索引
  2. 每張表都有主鍵索引
  3. B+tree 的葉節點儲存完整資料

• 在非主鍵上進行索引： 輔助索引（二級索引）

  1. 根據非主鍵進行索引
  2. B+tree 的葉節點儲存主鍵
  3. 查詢時分兩步驟 1. 根據輔助索引找到主鍵值，在進行主鍵索引找到完整資料（稱作回表）
  4. 若在輔助索引時就拿到查詢的所有資料則不需要回表

根據物理儲存分類

• B+tree 的葉節點儲存完整資料： 聚簇索引
• B+tree 的葉節點儲存主鍵： 非聚簇索引

其他

• 唯一索引
  1. 值唯一，可以 null
  2. 建立、update、insert 時會檢查值是否唯一

優化索引

1. 覆蓋索引優化： 在二級索引就能獲取資料，不需要回表
2. 自增：在 insert 時不需要搬移資料，而且能減少 B+tree 空間空洞
3. NOT NULL： null 在儲存時需要額外紀錄 null index
4. 選擇性較大的索引列放在左邊 (選擇性：不重複的索引值和記錄總數的比值)

索引如何失效

B+tree 會排序索引，所以如果 where condition 無法取得連續範圍資料則會失效

1. 對索引左或左右模糊

   // ex:
   SELECT * FROM user WHERE name like "%ron";
   SELECT * FROM user WHERE name like "%ro%";
   

2. 對索引使用函數

   //ex:
   SELECT * FROM user WHERE length(name) = 6;
   
   // MySQL 8.0 後可以使用函式索引
   ALTER TABLE user ADD KEY index_name_langth ((length(name)));
   

3. 對索引進行計算

   //ex:
   SELECT * FROM user WHERE id + 1 = 6;
   

4. 對索引進行隱式類型轉換

   //ex:
   SELECT * FROM user WHERE name = 123;
   
   // MySQL 的資料類型轉換規則是將string轉成number在進行比較
   

5. 複合索引非最左匹配

   // ex:
   // index (a, b,c)
   WHERE a = 6 and b = 6 and c = 6
   WHERE a = 6 and b = 6
   WHERE a = 6 
   // 以上都可以
   
   WHERE b = 6 and c = 6
   WHERE b = 6
   // 以上都會進行全表搜
   

6. ＯＲ

   WHERE condition1 OR condition2
   
   因為需 condition1 和 condition2 都成立 所以
   如果 condition2 是沒有索引的話則失效
   

使用場景

• 對於小的表，大部分情況下全表掃描比建立索引更有效率。
• 對於太大的表，建立和維護索引的代價會成長的太大。(可能需要考慮分區分表)