凡是經歷過幾場面試的同伴，應該都清楚，資料庫索引這個知識點在面試中出現的頻率高得驚人。除了對準備面試來說非常重要之外，善用索引可以明顯提升SQL的性能，是一個性價比較高的SQL優化手段。
索引概述
索引是一種用於快速查詢和檢索數據的數據結構，其本質可視為一種已排序的數據結構。索引的作用就像是書的目錄。舉個例子：我們在查字典時，如果沒有目錄，那麼我們只能一頁一頁地找需要查找的字，速度非常慢。如果有目錄，我們只需要先在目錄中查找字的位置，然後直接翻到那一頁就可以了。索引底層數據結構存在許多種類型，常見的索引結構包括：B樹、B+樹和哈希、紅黑樹。在MySQL中，無論是InnoDB還是MyISAM，都使用B+樹作為索引結構。
索引的優缺點
優點：使用索引可以極大地加快數據的檢索速度（大幅減少檢索的數據量），這也是創建索引的主要原因之壹。通過創建唯壹性索引，可以確保數據庫表中每壹行數據的唯壹性。
缺點：創建索引和維護索引需要耗費大量時間。當對表中的數據進行增刪改時，如果數據有索引，索引也需要動態修改，會降低SQL執行效率。索引需要使用物理文件存儲，也會占用壹定空間。
然而，使用索引壹定能提高查詢性能嗎？大多數情況下，索引查詢通常比全表掃描要快。但如果數據庫的數據量不大，使用索引也不壹定能夠帶來很大提升。
底層索引的資料結構選擇
哈希表
哈希表是鍵值對的集合，透過鍵（key）即可快速取出對應的值（value），因此哈希表可以快速檢索資料（接近 O（1））。為何能夠透過 key 快速取出 value 呢？原因在於哈希算法（也叫散列算法）。通過哈希算法，我們可以快速找到 key 對應的 index，找到了 index 也就找到了對應的 value。
hash = hashfunc(key) index = hash % array_size
然而！哈希算法存在哈希冲突的問題，也就是說多個不同的 key 最後得到相同的 index。通常情況下，我們常用的解決方法是鏈地址法。鏈地址法是將哈希冲突的資料存放在鏈表中。就像 JDK1.8 之前的 HashMap 就是透過鏈地址法來解決哈希冲突的。不過，JDK1.8 以後的 HashMap 為了減少鏈表過長時搜索時間過長引入了紅黑樹。
為了減少 Hash 冲突的發生，一個良好的哈希函數應該「均勻地」將數據分佈在整個可能的哈希值集合中。MySQL 的 InnoDB 存儲引擎不直接支持常規的哈希索引，但是，在 InnoDB 存儲引擎中存在一種特殊的「自適應哈希索引」（Adaptive Hash Index），自適應哈希索引並不是傳統意義上的純哈希索引，而是結合了 B+Tree 和哈希索引的特點，以便更好地適應實際應用中的數據訪問模式和性能需求。自適應哈希索引的每個哈希桶實際上是一個小型的 B+Tree 結構。這個 B+Tree 結構可以存儲多個鍵值對，而不僅僅是一個鍵。這有助於減少哈希冲突鏈的長度，提高了索引的效率。關於 Adaptive Hash Index 的詳細介紹，可以查看 MySQL 各種「Buffer」之 Adaptive Hash Index 的這篇文章。既然哈希表這麼快，為什麼 MySQL 沒有使用其作為索引的資料結構呢？主要是因為 Hash 索引不支持順序和範圍查詢。假如我們要對表中的數據進行排序或者進行範圍查詢，那 Hash 索引可就不行了。並且，每次 IO 只能取一個。
想像一下:
SELECT * FROM tb1 WHERE id < 500;
在這種範圍查詢中，優勢非常明顯，只需直接遍歷比 500 小的葉子節點就足夠了。而 Hash 索引是根據 hash 算法來定位的，難道還要對 1 – 499 的數據，每個都進行一次 hash 計算才能定位嗎？這就是 Hash 最大的缺點。
二元搜尋樹(BST)
二元搜尋樹（Binary Search Tree）是一種基於二元樹的資料結構，它具有以下特點：左子樹所有節點的值均小於根節點的值。右子樹所有節點的值均大於根節點的值。左右子樹也分別為二元搜尋樹。當二元搜尋樹是平衡的時候，也就是樹的每個節點的左右子樹深度相差不超過 1 的時候，查詢的時間複雜度為 O(log2(N))，具有相當高的效率。然而，當二元搜尋樹不平衡時，例如在最壞情況下（有序插入節點），樹會退化成線性鏈表（也被稱為斜樹），導致查詢效率急劇下降，時間複雜度退化為 O（N）。
換句話說，二元搜尋樹的效能非常依賴於它的平衡程度，這導致它不適合作為 MySQL 底層索引的資料結構。為了解決這個問題，並提高查詢效率，人們發明了多種在二元搜尋樹基礎上的改進型資料結構，如平衡二元樹、B-Tree、B+Tree 等。
AVL 樹
AVL 樹是計算機科學中最早被發明的自平衡二元搜尋樹，它的名稱來自於發明者 G.M. Adelson-Velsky 和 E.M. Landis 的名字縮寫。AVL 樹的特點是保證任何節點的左右子樹高度之差不超過 1，因此也被稱為高度平衡二元樹，它的查找、插入和刪除在平均和最壞情況下的時間複雜度都是 O(logn)。
AVL樹透過旋轉操作來維持平衡，壹共有四種旋轉操作：LL旋轉、RR旋轉、LR旋轉和RL旋轉。LL旋轉和RR旋轉分別用於處理左左和右右失衡，而LR旋轉和RL旋轉則用於處理左右和右左失衡。因為AVL樹需要頻繁進行旋轉操作以保持平衡，所以會增加相當大的計算成本，進而降低了資料庫寫操作的性能。此外，在使用AVL樹時，每個樹節點僅存儲壹個數據，因此每次進行磁碟IO時只能讀取壹個節點的數據，如果需要查詢的數據分佈在多個節點上，就需要進行多次磁碟IO。磁碟IO是壹項耗時的操作，在設計資料庫索引時，我們需要優先考慮如何最大限度地減少磁碟IO操作的次數。實際應用中，AVL樹的使用並不多見。
紅黑樹是一種自平衡的二叉查找樹，通過在插入和刪除節點時進行顏色變換和旋轉操作來保持樹的平衡狀態。紅黑樹具有以下特點：每個節點要麽是紅色，要麽是黑色；根節點是黑色的；每個葉子節點都是黑色的空節點（NIL 節點）；如果壹個節點是紅色的，則它的子節點必須是黑色的（反之不壹定）；從任意節點到其葉子節點或空子節點的每條路徑上，必須包含相同數量的黑色節點（即具有相同的黑色高度）。
B 樹和 B+樹
全稱多路平衡查找樹，是壹種常見的索引結構。B 樹和 B+樹中的 B 意味著平衡。現今大多數數據庫系統和文件系統都采用 B-Tree 或其變種 B+Tree 作為索引結構。B 樹和 B+樹有何不同之處？在 B 樹中，每個節點都同時存儲鍵(key)和數據(data)，而在 B+樹中，只有葉子節點存儲鍵和數據，內部節點僅存儲鍵。此外，在 B 樹中，葉子節點相互獨立；而在 B+樹中，葉子節點通過引用鏈相互連接。在進行範圍查詢時，B 樹需要在中間節點進行二分查找，而 B+樹則可以直接從根節點到葉子節點進行查詢，然後順序遍歷葉子節點即可。綜上所述，相較於 B 樹，B+樹具有更少的 IO 操作、更穩定的查詢效率和更適用於範圍查詢的優勢。在 MySQL 中，MyISAM 引擎和 InnoDB 引擎都使用 B+Tree 作為索引結構，但它們的實現方式略有不同。
在 MyISAM 引擎中，B+Tree 葉節點的 data 域存儲的是數據記錄的地址。在進行索引檢索時，首先按照 B+Tree 搜索算法搜索索引，如果指定的 Key 存在，則取出其 data 域的值，然後以 data 域的值為地址讀取相應的數據記錄。這種索引方式被稱為“非聚簇索引（非聚集索引）”。而在 InnoDB 引擎中，數據文件本身就是索引文件。與 MyISAM 不同，索引文件和數據文件是分離的，表數據文件本身按照 B+Tree 組織成壹個索引結構，樹的葉節點 data 域保存了完整的數據記錄。這個索引的 key 是數據表的主鍵，因此 InnoDB 表數據文件本身就是主索引，這被稱為“聚簇索引（聚集索引）”。而其他的索引被視為輔助索引，輔助索引的 data 域存儲相應記錄主鍵的值而不是地址。在根據主索引搜索時，只需直接找到 key 所在的節點即可取出數據；而在根據輔助索引查找時，則需要先取出主鍵的值，再在主索引中進行壹次查找。因此，在設計表時，不建議使用過長的字段作為主鍵，也不建議使用非單調的字段作為主鍵，否則會導致主索引頻繁分裂。
索引分類
按照資料結構的維度劃分：
- BTree 索引：MySQL 中默認和最常用的索引類型。只有葉子節點存儲 value，非葉子節點只有指針和 key。MyISAM 和 InnoDB 使用的 BTree 索引都是採用 B+Tree 實現的，但兩者的實現方式不同。
- 哈希索引：類似鍵值對的形式，一次即可定位。
- RTree 索引：一般不常用，僅支持 geometry 數據類型，優勢在於範圍查找，效率較低，通常使用搜索引擎如 ElasticSearch 代替。
- 全文索引：對文本的內容進行分詞，進行搜索。目前只有
CHAR、VARCHAR，TEXT列上可以創建全文索引。一般不常用，效率較低，通常使用搜索引擎如 ElasticSearch 代替。
按照底層存儲方式角度劃分：
- 聚簇索引（聚集索引）：索引結構和數據一起存放的索引，InnoDB 中的主鍵索引就屬於聚簇索引。
- 非聚簇索引（非聚集索引）：索引結構和數據分開存放的索引，二級索引(輔助索引)就屬於非聚簇索引。MySQL 的 MyISAM 引擎，不管主鍵還是非主鍵，使用的都是非聚簇索引。
按照應用的維度劃分：
- 主鍵索引：加速查詢 + 列值唯一（不可以有 NULL）+ 表中只有一個。
- 普通索引：僅加速查詢。
- 唯一索引：加速查詢 + 列值唯一（可以有 NULL）。
- 覆蓋索引：一個索引包含（或者說覆蓋）所有需要查詢的字段的值。
- 聯合索引：多列值組成一個索引，專門用於組合搜索，其效率大於索引合併。
- 全文索引：對文本的內容進行分詞，進行搜索。目前只有
CHAR、VARCHAR，TEXT列上可以創建全文索引。一般不常用，效率較低，通常使用搜索引擎如 ElasticSearch 代替。
MySQL 8.x 中實現的索引新特性：
- 隱藏索引：也稱為不可見索引，不會被優化器使用，但是仍然需要維護，通常會用於軟刪除和灰度發布的場景中使用。主鍵不能設置為隱藏（包括顯式設置或隱式設置）。
- 降序索引：之前的版本就支持通過 desc 來指定索引為降序，但實際上創建的仍然是常規的升序索引。直到 MySQL 8.x 版本才開始真正支持降序索引。另外，在 MySQL 8.x 版本中，不再對 GROUP BY 語句進行隱式排序。
- 函數索引：從 MySQL 8.0.13 版本開始支持在索引中使用函數或者表達式的值，也就是在索引中可以包含函數或者表達式
主鍵索引(Primary Key)
主键索引是用于数据表的主键列。
每张数据表只能有一个主键，且主键值不能为 null 且不能重複。
在 MySQL 的 InnoDB 表中，若未明確指定表的主键，InnoDB 會先檢查表中是否存在唯一索引且不允許存在 null 值的欄位，若有，則選擇該欄位為預設的主鍵，否則 InnoDB 將自動創建一個 6Byte 的自增主鍵。
次級索引
次級索引（Secondary Index）的葉子節點存儲的資料是主鍵的值，也就是說，通過次級索引可以定位主鍵的位置，次級索引又稱為輔助索引/非主鍵索引。
唯一索引、普通索引、前綴索引等索引都屬於次級索引。
PS: 不懂的同學可以暫存疑，慢慢往下看，後面會有答案的，也可以自行搜索。
- 唯一索引(Unique Key): 唯一索引也是一種約束。唯一索引的屬性列不能出現重複的資料，但允許資料為 NULL，一張表允許建立多個唯一索引。建立唯一索引的目的大部分時候都是為了該屬性列的資料的唯一性，而不是為了查詢效率。
- 普通索引(Index): 普通索引的唯一作用就是為了快速查詢資料，一張表允許建立多個普通索引，並允許資料重複和 NULL。
- 前綴索引(Prefix): 前綴索引只適用於字串類型的資料。前綴索引是對文本的前幾個字元建立索引，相比普通索引建立的資料更小，因為只取前幾個字元。
- 全文索引(Full Text): 全文索引主要是為了檢索大文本資料中的關鍵字的信息，是目前搜索引擎資料庫使用的一種技術。Mysql5.6 之前只有 MYISAM 引擎支持全文索引，5.6 之後 InnoDB 也支持了全文索引。
評論0