窺探 MySQL 索引

MySQL 索引

1. 什麼是數據庫索引

在關係數據庫中，如果有上萬甚至上億條記錄，在查找記錄的時候，想要獲得非常快的速度，就需要使用索引。

索引是關係數據庫中對某一列或多個列的值進行預排序的數據結構，在 MySQL 中也被稱爲 Key。通過使用索引，可以讓數據庫系統不必掃描整個表，而是直接定位到符合條件的記錄，這樣就大大加快了查詢速度。

注意事項：有序性是因爲一切二分法查找法都要求數據已經是排好順序的。如果把索引看做 key（雖然 key 數據也是來自於表單中一行記錄的某些字段值），那麼 value 在 MyISAM 中就是記錄的在存儲文件中的地址，而在 InnoDB 中 value 直接就是對應的一行數據。

比如我們將一本書中每一章的章節名作爲搜索條件，那麼書本最開始的目錄就是索引。我們通過目錄能夠非常快地找到對應章節，而不必一頁頁翻書來查看具體是否有某個章節，具體章節的內容從哪一頁開始。

索引的本質實際上還是存儲在磁盤上的數據結構，它可以有的存儲結構：

其中 MySQL 的 InnoDB 支持 B+Tree 以及 Hash 表，下面會具體分析各個數據結構的區別。

如果我們事先對某個列字段建立好了索引，那麼 MySQL 在依靠列字段進行搜索的時候就會優先去索引中搜尋，而不必依靠在數據表中的逐行搜尋。

注意事項：在一次查詢中，MySQL 只能使用一個索引。特別注意下面會提到的聯合索引，聯合索引也是一個索引。

比如上表左側爲數據庫中的多行數據，右側爲索引（數據結構爲二叉搜索樹類型）：

2. 如何創建數據庫索引

例如，對於students表：

YOCY3d

如果要經常根據 score 列進行查詢，就可以對score列創建索引：

ALTER TABLE students
ADD INDEX idx_score (score);

使用 ADD INDEX idx_score (score) 就創建了一個名稱爲 idx_score，使用列 score 的索引。索引名稱是任意的，索引如果有多列，可以在括號裏依次寫上，例如：

ALTER TABLE students
ADD INDEX idx_name_score (name, score);

索引的效率取決於索引列的值是否散列，即該列的值如果越互不相同，那麼索引效率越高。反過來，如果記錄的列存在大量相同的值，例如 gender 列，大約一半的記錄值是 M，另一半是 F，因此，對該列創建索引就沒有意義。

可以對一張表創建多個索引。

優缺點：

對於主鍵，關係數據庫會自動對其創建主鍵索引。使用主鍵索引的效率是最高的，因爲主鍵會保證絕對唯一，唯一性帶來的索引的充分散列。

2.1 索引的查看和創建語法

desc tableName;#顯示錶的結構
show index from tableName \G #查看錶的索引情況

desc tableName; 命令輸出的表中的 Key 欄：

例如下面兩圖：

索引的創建可以歸納爲如下：

常用以下兩種方式：

  1. CREATE [UNIQUE|FULLTEXT] INDEX [indexName] ON tableName(columnname(length))
  2. ALTER TABLE tableName ADD [UNIQUE|FULLTEXT] INDEX [indexName] (colummnname(length))
  3. 也可以在創建表的同時建索引，這裏就不列出了，下面幾個小節會具體說明；

2.2 創建主鍵索引

主鍵索引的定義：InnoDB 中的表單數據本身就要創建爲一棵 B+ 樹，而這棵排序節點用到的索引就被稱爲主鍵索引。

只要有主鍵，那麼主鍵索引根據的就是主鍵，我們在創建表和後續修改時都能夠通過指定主鍵來確定主鍵索引，如下：

  1. 創建表同時設置主鍵

    create table teacher(
-> id int(10) auto_increment,
-> name varchar(20),
-> age int(10),
-> phone varchar(11),
-> primary key (id));//主鍵設置

  2. 單獨設置主鍵

    alter table teacher add primary key (id);

在 InnoDB 中根據主鍵索引來查詢是最快的，因爲其他索引都是輔助索引，它們的 data 實際上爲主鍵號，換句話說，除了主鍵索引，其餘索引都要多走一遍 B+ 樹。

輔助索引是我們外加的索引，對於 InnoDB 的每一張表都能夠創建至多 16 個索引，但是主鍵索引是唯一的，其他索引都是主鍵索引，比如唯一索引、普通索引。

2.3 創建唯一索引

唯一索引的創建方式：

# 創建表同時建唯一索引
create table teacher(
    -> id int(10) auto_increment,
    -> name varchar(20),
    -> age int(10),
    -> phone varchar(11),
    -> primary key (id),
    -> unique index idx_phone(phone(11)));#唯一索引
# 單獨建唯一索引
create unique index idx_phone on teacher(phone(11));
# 刪除唯一索引
drop index idexName on tableName;
# 修改建唯一索引
alter table teacher add unique idx_phone (phone(11));

2.4 創建普通索引

創建普通索引的方式如下：

# 創建表同時建普通索引
create table teacher(
    -> id int(10) auto_increment,
    -> name varchar(20),
    -> age int(10),
    -> phone varchar(11),
    -> primary key (id),
    -> index idx_phone (phone(11)));
# 單獨建普通索引
create index idx_phone on teacher(phone(11));
# 修改普通索引
alter table teacher add index idx_phone (phone(11));

2.5 創建聯合索引

創建聯合索引的方式如下：

# 創建表同時建組合索引
create table teacher(
    -> id int(10) auto_increment,
    -> name varchar(20),
    -> phone varchar(11),
    -> primary key (id),
    -> index idx_name_phone (name(20),phone(11)));
# 單獨建組合索引
create index idx_name_phone on teacher (name(20),phone(11));
# 修改組合索引
alter table teacher add index idx_name_phone (name(20),phone(11));

2.6 創建全文索引

# 創建表同時建全文索引
create table teacher(
    -> id int(10) auto_increment,
    -> name varchar(20),
    -> age int(10),
    -> phone varchar(11),
    -> primary key (id),
    -> fulltext index idx_phone(phone(11)));
# 單獨建全文索引
create fulltext index idx_phone on teacher(phone(11));
# 修改全文索引
alter table teacher add fulltext index idx_phone (phone(11));

3. 索引的優點和缺點

索引有很多種類型，可以爲不同的場景提供更好的性能。在 MySQL 中，索引是在存儲引擎層而不是服務器層實現的。所以，並沒有統一的索引標準：不同存儲引擎的索引的工作方式並不一樣，也不是所有的存儲引擎都支持所有類型的索引。即使多個存儲引擎支持同一種類型的索引，其底層的實現也可能不同。

  1. 索引大大減少了服務器需要掃描的數據量。
  2. 索引可以幫助服務器避免排序和臨時表。
  3. 索引可以將隨機 I/O 變爲順序 I/O。

固態硬盤驅動器和傳統的硬盤驅動器有着完全不同的性能特性。然而即使是固態硬盤，索引的原則依然成立，只是那些需要儘量避免的糟糕索引對於固態硬盤的影響沒有傳統硬盤那麼糟糕。

索引速度快的原因是什麼？

不同類型的索引有着不同的數據結構，但是提高查詢速度的思想是一致的：利用數據結構的有序性避免進行全表掃描來獲取需要的數據。

用好索引能夠大大提高查詢效率，那麼代價是什麼呢？

  1. 創建索引和維護索引要耗費時間，這種時間隨着數據量的增加而增加；
  2. 索引需要佔物理空間，除了數據表佔數據空間之外，每一個索引還要佔一定的物理空間，如果要建立聚簇索引，那麼需要的空間就會更大；
  3. 當對錶中的數據進行增加、刪除和修改的時候，索引也要動態的維護，降低了數據的維護速度；

4. 索引的數據結構選型

數據結構圖來源於（舊金山大學）：https://www.cs.usfca.edu/~galles/visualization/Algorithms.html

出於減少磁盤 I/O 次數的目的，我們對於一個上千萬的行的數據要求一個樹的深度不能夠很深，或者說應當是常數位深度。

對於各種數據結構，我們在這先有一個統一的設定：每一個索引節點都有對數據庫表中對應行的一個地址指針，找到索引的節點就可以通過這個地址指針去數據庫中馬上定位到具體某行數據。

4.1 二叉搜索（查找）樹 - Binary Search Tree

Binary Search Tree - 二叉查找樹，也稱爲二叉搜索樹、有序二叉樹或排序二叉樹，是指一棵空樹或者具有下列性質的二叉樹： 若任意節點的左子樹不空，則左子樹上所有節點的值均小於它的根節點的值； 若任意節點的右子樹不空，則右子樹上所有節點的值均大於或等於它的根節點的值； 任意節點的左、右子樹也分別爲二叉查找樹。

那麼二叉搜索樹適合來做索引的內部數據結構嗎？

我們通常會拿自增的整型鍵值作爲索引，那麼如果使用二叉搜索樹，數據結構如下：

可見，此時二叉搜索樹由於其極度的單邊增長趨勢，相當於單向鏈表。而在單向鏈表上進行遍歷搜索和原本在表中按行搜索沒有任何區別，因爲從遍歷次數上來看還是需要遍歷相同的次數，而且在刪除、插入時還要維護索引。

因此使用二叉搜索樹來作爲索引沒有優勢只有額外的消耗，因此二叉搜索樹不適合作爲索引內部的數據結構。

4.2 紅黑樹 - Red/Black Tree

紅黑樹是一種自平衡二叉查找樹。我們可以將紅黑樹看做爲二叉搜索樹的改進版本，其在樹的結構失衡非常嚴重的時候會通過旋轉來解決問題。

最終的數據結構如下圖所示：

我們可以發現，在自增整數作爲索引的背景下紅黑樹的表現比二叉搜索樹好非常多，原本第 6 行數據要在表上查找 6 次，現在僅僅需要查找 3 次，效率高了不少。

這就是二叉樹變平衡了的優勢。

但是如果數據庫中有 2 千萬條數據，那麼紅黑樹需要多少層呢？

樹的層級有 25 層，這可是一顆相當高的一棵樹，這會極大影響搜索效率。

4.3 哈希索引

哈希索引 (hash index) 基於哈希表實現，只有精確匹配索引所有列的查詢纔有效生。對於每一行數據，存儲引擎都會對所有的索引列計算一個哈希碼(hash code)，哈希碼是一個較小的值，並且不同鍵值的行計算出來的哈希碼也不一樣。哈希索引將所有的哈希碼存儲在索引中，同時在哈希表中保存指向每個數據行的指針。

在 MySQL 中，只有 Memory 引擎顯式支持哈希索引。這也是 Memory 引擎表的默認索引類型，Memory 引擎同時也支持 B-Tree 索引。值得一提的是，Memory 引擎是支持非唯一哈希索引的，這在數據庫世界裏面是比較與衆不同的。如果多個列的哈希值相同，索引會以鏈表的方式存放多個記錄指針到同一個哈希條目中。

下面來看一個例子。假設有如下表：

CREATE TABLE testhash(
	fname VARCHAR(50) NOT NULL,
  lname VARCHAR(50) NOT NULL,
  KEY USING HASH(fname)
) ENGINE = MEMORY;

然後再填入相關數據後，表格有如下數據：

mysql> select * from testhash;
+-------+-------+
| fname | lname |
+-------+-------+
| a     | l     |
| b     | s     |
| p     | z     |
| v     | t     |
+-------+-------+

假設索引使用假想的哈希函數 f()，它返回下面的值 (都是示例數據，非真實數據) :

則哈希索引的數據結構如下：

owb2Uv

注意每個槽的編號是順序的，但是數據行不是。

下面使用 hash 索引字段進行查詢，有：

mysql> SELECT lname FROM testhash WHERE fname = 'p';
+-------+
| lname |
+-------+
| z     |
+-------+
1 row in set (0.00 sec)

其分爲如下的步驟：

因爲索引自身只需存儲對應的哈希值，所以索引的結構十分緊湊，這也讓哈希索引查找的速度非常快。然而，哈希索引也有它的限制：

注意事項：基於 Hash 索引的表還是能夠支持範圍查找，只不過其通過遍歷實現，不能利用索引進行查詢優化。

4.4 B 樹 - B-tree

B 樹能夠將樹的高度限制在很大範圍內的高度是一個常數級別，即使數據量有千萬級別，使樹的高度在很大的範圍內不隨着數據量的增多而增多。

那麼什麼是 B Tree?

B 樹和平衡二叉樹稍有不同的是 B 樹屬於多叉樹又名平衡多路查找樹（查找路徑不只兩個），數據庫索引技術裏大量使用者 B 樹和 B+ 樹的數據結構，讓我們來看看他有什麼特點：

最後我們用一個圖和一個實際的例子來理解 B 樹（這裏爲了理解方便我就直接用實際字母的大小來排列 C>B>A）

其有兩個方向的大小關係：

  • 同一個節點上的索引，從左到右依次遞增。
  • 左子節點上所有的索引 < 父節點索引≤右子節點上所有的索引

如上圖我要從上圖中找到 E 字母，查找流程如下：

  1. 獲取根節點的關鍵字進行比較，當前根節點關鍵字爲 M，E<M（26 個字母順序），所以往找到指向左邊的子節點（二分法規則，左小右大，左邊放小於當前節點值的子節點、右邊放大於當前節點值的子節點）；

  2. 拿到關鍵字 D 和 G，D<E<G 所以直接找到 D 和 G 中間的節點；

  3. 拿到 E 和 F，因爲 E=E 所以直接返回關鍵字和指針信息（如果樹結構裏面沒有包含所要查找的節點則返回 null）；

那麼 B-tree 如何確保平衡的呢？

我們定義一個 5 階樹（平衡 5 路查找樹;），現在我們要把 3、8、31、11、23、29、50、28 這些數字構建出一個 5 階樹出來;

遵循規則：

  1. 節點拆分規則：當前是要組成一個 5 路查找樹，那麼此時 m=5，關鍵字數必須 <=5-1（這裏關鍵字數>4 就要進行節點拆分）；
  2. 排序規則：滿足節點本身比左邊節點大，比右邊節點小的排序規則;

先插入 3、8、31、11：

再插入 23、29：

再插入 50、28：

B 樹的特點：

B 樹相對於平衡二叉樹的不同是，每個節點包含的關鍵字增多了，特別是在 B 樹應用到數據庫中的時候，數據庫充分利用了磁盤塊的原理（磁盤數據存儲是採用塊的形式存儲的，每個塊的大小爲 4K，每次 I/O 進行數據讀取時，同一個磁盤塊的數據可以一次性讀取出來）把節點大小限制和充分使用在磁盤快大小範圍；把樹的節點關鍵字增多後樹的層級比原來的二叉樹少了，減少數據查找的次數和複雜度；

4.5 B+Tree

4.5.1 B+Tree 概述

B+ 樹是 B 樹的一個升級版，相對於 B 樹來說 B+ 樹更充分的利用了節點的空間，讓查詢速度更加穩定，其速度完全接近於二分法查找。爲什麼說 B+ 樹查找的效率要比 B 樹更高、更穩定；我們先看看兩者的區別：

  1. B+ 樹的非葉子節點不保存關鍵字記錄的指針，只進行數據索引 (冗餘，因爲葉子節點上有着完整的索引結構)，這樣使得 B+ 樹每個非葉子節點所能保存的索引值大大增加；

    如果樹中每一個節點的數據大小一定，那麼 B + 樹的一個非葉子節點能夠比 B 樹的一個非葉子節點存儲更多數量的索引。

  2. B+ 樹葉子節點保存了父節點的所有關鍵字記錄的指針，所有數據地址必須要到葉子節點才能獲取到。所以每次數據查詢的次數都一樣；

  3. B+ 樹葉子節點的關鍵字從小到大有序排列，左邊結尾數據都會保存右邊節點開始數據的指針。

    這個特性在範圍查找（區間訪問）時非常有用。

  4. 非葉子節點的子節點數 = 關鍵字數（來源百度百科）（根據各種資料 這裏有兩種算法的實現方式，另一種爲非葉節點的關鍵字數 = 子節點數 - 1（來源維基百科)，雖然他們數據排列結構不一樣，但其原理還是一樣的 Mysql 的 B + 樹是用第一種方式實現）;

關於節點大小的討論

在 MySQL 中，B+ 樹的每一個非葉子節點默認佔據 16 KB 大小的數據，如果我們索引值使用 BigInt 類型，其佔據 8 B 的內存大小。另一方面，由於每一個非葉子節點其存儲方式是以一對：“索引值 + 下一個節點地址” 來存儲的，而寫一個節點地址通常是由 6 B 數據大小來存儲的，因此對於 MySQL 中以 BigInt 作爲數據類型的索引，一個非葉子節點可以存儲 16KB/(6B+8B) = 1170 個索引。而最後的葉子節點中每一個索引大概佔據 1 KB，即可以存放 16 個節點。

這裏有假設這裏的存儲引擎是 InnoDB。

因此對於一個高度爲 3 的 B+ 樹，如上圖所示：

因此，雖然索引有冗餘，但是存儲的總索引數量爲 1170 * 1170*16 = 21902400，已經 2 千萬 + 的數據了。

B+ 樹的特點：

  1. B + 樹的層級更少：相較於 B 樹 B + 每個非葉子節點存儲的關鍵字數更多，樹的層級更少所以查詢數據更快；
  2. B + 樹查詢速度更穩定：B + 所有關鍵字數據地址都存在葉子節點上，即每一個索引實際上距離根節點距離相同，所以每次查找的次數都相同所以查詢速度要比 B 樹更穩定;
  3. B + 樹天然具備排序功能：B + 樹所有的葉子節點數據構成了一個有序鏈表，在查詢大小區間的數據時候更方便，數據緊密性很高，緩存的命中率也會比 B 樹高。
  4. B + 樹全節點遍歷更快：B+ 樹遍歷整棵樹只需要遍歷所有的葉子節點即可，，而不需要像 B 樹一樣需要對每一層進行遍歷，這有利於數據庫做全表掃描。
  5. B+ 樹的範圍查找非常方便，這是因爲 B+ 樹的葉子節點之間依靠單向指針相連。比如查找範圍爲 10<index<16 的節點，我們僅僅需要先找到索引爲 10 的節點在哪個葉子子節點上，特別需要指出的是，即使比如 14 節點在另一個葉子節點上，也能通過葉子節點之間的指針快速找到索引。

B 樹相對於 B + 樹的優點是：如果經常訪問的數據離根節點很近，而 B 樹的非葉子節點本身存有關鍵字其數據的地址，所以這種數據檢索的時候會要比 B + 樹快。

4.5.2 數據庫的磁盤目錄文件。

對於一個 MySQL 應用程序，其在磁盤上安裝時會有其安裝目錄，在安裝目錄下有一個 data 目錄專門用於存放數據庫文件夾，如下：

那麼每一個數據庫中又有很多表，每一個表不再對應文件夾，而是數據庫目錄下的一組文件，如下：

也可以用如下表示：

|--- mysql
    |--- data
        |--- 數據庫
            |--- 表名.frm
            |--- 表名.myd
            |--- 表名.myi
            |--- 表名.log

test 數據庫下的兩張表分別對應 MySQL_HOME/data/test/ 路徑下的一組文件：

其中

  • *.frm 文件 (framework) 描述了一個表的各行的定義：名稱、類型、是否非空、自增性等等，這個文件在 MySQL 中與具體的存儲引擎無關。
  • *.MYD 文件 (MyISAM Data) 存儲了 MyISAM 存儲引擎的表單數據；
  • *.MYI 文件 (MyISAM Index) 存儲了 MyISAM 存儲引擎的索引數據；
  • *.ibd 文件 (InnodB Data) 存儲了 InnoDB 存儲引擎的表單數據以及索引數據；
  • *.log 文件存儲了日誌數據；

我們在這裏可以發現，MyISAM 和 InnoDB 對應的文件數量和類型是有區別的：

在 MySQL 中，索引屬於存儲引擎級別的概念，不同存儲引擎對索引的實現方式是不同的，本文主要討論 MyISAM 和 InnoDB 兩個存儲引擎的索引實現方式。

不管哪一個存儲引擎，都是描述一個表。雖然一個數據庫通常有其默認的存儲引擎設置。

4.5.3 MyISAM 中的 B+Tree

MyISAM 引擎使用 B+Tree 作爲索引結構，葉節點的 data 域存放的是數據記錄的地址。下圖是 MyISAM 索引的原理圖：

從上圖也可以看出，表單存儲文件和索引存儲是分開獨立存儲的。

這裏設表一共有三列，假設我們以 Col1 爲主鍵，則圖 8 是一個 MyISAM 表的主索引（Primary key）示意。可以看出 MyISAM 的索引文件僅僅保存數據記錄的地址。在 MyISAM 中，主索引和輔助索引（Secondary key）在結構上沒有任何區別，只是主索引要求 key 是唯一的，而輔助索引的 key 可以重複。如果我們在 Col2 上建立一個輔助索引，則此索引的結構如下圖所示：

同樣也是一棵 B+Tree，data 域保存數據記錄的地址。因此，MyISAM 中索引檢索的算法爲首先按照 B+Tree 搜索算法搜索索引，如果指定的 Key 存在，則取出其 data 域的值，然後以 data 域的值爲地址，讀取相應數據記錄。

MyISAM 的索引方式也叫做 “非聚集” 的，之所以這麼稱呼是爲了與 InnoDB 的聚集索引區分。

4.5.4 InnoDB 中的 B+Tree

雖然 InnoDB 也使用 B+Tree 作爲索引結構，但具體實現方式卻與 MyISAM 截然不同。

第一個重大區別是 InnoDB 的數據文件本身就是索引文件。從上文知道，MyISAM 索引文件和數據文件是分離的，索引文件僅保存數據記錄的地址。而在 InnoDB 中，表數據文件本身就是按 B+Tree 組織的一個索引結構，這棵樹的葉節點 data 域保存了完整的數據記錄。這個索引的 key 是數據表的主鍵，因此 InnoDB 表數據文件本身就是主索引。

上圖是 InnoDB 主索引（同時也是數據文件）的示意圖，可以看到葉節點包含了完整的數據記錄。這種索引叫做聚集索引。因爲 InnoDB 的數據文件本身要按主鍵聚集，所以 InnoDB 要求表必須有主鍵（MyISAM 可以沒有），如果沒有顯式指定，則 MySQL 系統會自動選擇一個可以唯一標識數據記錄的列作爲主鍵，如果不存在這種列，則 MySQL 自動爲 InnoDB 表生成一個隱含字段作爲主鍵，這個字段長度爲 6 個字節，類型爲長整形。

4.6 非數據結構出發的索引分類

4.6.1 輔助索引

第二個與 MyISAM 索引的不同是 InnoDB 的輔助索引 data 域存儲相應記錄主鍵的值而不是地址。換句話說，InnoDB 的所有輔助索引都引用主鍵作爲 data 域。例如，下圖爲定義在 Col3 上的一個輔助索引：

這裏以英文字符的 ASCII 碼作爲比較準則。聚集索引這種實現方式使得按主鍵的搜索十分高效，但是輔助索引搜索需要檢索兩遍索引：首先檢索輔助索引獲得主鍵，然後用主鍵到主索引中檢索獲得記錄。

4.6.2 聯合（複合）索引

在上文中，我們都是假設索引只引用了單個的列，實際上，MySQL 中的索引可以以一定順序引用多個列，這種索引叫做聯合索引，一般的，一個聯合索引是一個有序元組 <a1, a2, …, an>，其中各個元素均爲數據表的一列，實際上要嚴格定義索引需要用到關係代數，但是這裏我不想討論太多關係代數的話題，因爲那樣會顯得很枯燥，所以這裏就不再做嚴格定義。另外，單列索引可以看成聯合索引元素數爲 1 的特例。

那麼聯合索引到底長什麼樣子？

假設：表 T1 有字段 a,b,c,d,e，其中 a 是主鍵，除 e 爲 varchar 其餘爲 int 類型，並創建了一個聯合索引 idx_t1_bcd(b,c,d)，然後 b、c、d 三列作爲聯合索引。

Tip：基於 InnoDB 存儲引擎。

聯合索引長下面的樣子：

聯合索引：聯合索引的所有索引列都出現在索引數上，並依次比較三列的大小。

聯合索引的查詢工作方式

當我們的 SQL 語言可以應用到索引的時候，比如

select * from T1 where b = 12 and c = 14 and d = 3;

也就是 T1 表中 a 列爲 4 的這條記錄。存儲引擎首先從根節點（一般常駐內存）開始查找，第一個索引的第一個索引列爲 1，12 大於 1，第二個索引的第一個索引列爲 56，12 小於 56，於是從這倆索引的中間讀到下一個節點的磁盤文件地址，從磁盤上 Load 這個節點，通常伴隨一次磁盤 I/O，然後在內存裏去查找。當 Load 葉子節點的第二個節點時又是一次磁盤 I/O，比較第一個元素，b= 12，c=14，d=3 完全符合，於是找到該索引下的 data 元素即 ID 值，再從主鍵索引樹上找到最終數據。

當然遺漏了從主鍵索引上查找的步驟，但是和上述過程完全是類似的，只不過主鍵索引是唯一的，而不像聯合索引那般有多個匹配條件。

其他細節補充：

4.6.3 聚簇索引

聚簇索引並不是一種單獨的索引類型，而是一種數據存儲方式。具體的細節依賴於其實現方式，但 InnoDB 的聚簇索引實際上在同一個結構中保存了 B-Tree 索引和數據行。

當表有聚簇索引時，它的數據行實際上存放在索引的葉子頁 (leaf page) 中。術語 “聚簇” 表示數據行和相鄰的鍵值緊湊地存儲在一起。因爲無法同時把數據行存放在兩個不同的地方，所以一個表只能有一個聚簇索引 (不過，覆蓋索引可以模擬多個聚簇索引的情況）。

聚集的數據有一些重要的優點：

聚簇索引的缺點：

在 MyISAM 中二級索引葉子節點存儲數據行的地址，而 InnoDB 中存儲的是主鍵值（不是主鍵地址）。InnoDB 的策略好處是：當出現行移動或者數據頁分裂時二級索引的維護工作，不需要維護變動的指針；壞處是：使用主鍵值當作指針會讓二級索引佔用更多的空間。特它們的區別可以用下圖表示：

另一方面，InnoDB 主鍵索引葉子節點的數據由如下元素組成：

4.6.4 覆蓋索引

我們通常關注於將 WHERE 子句後面的列字段用索引來提升性能，實際上我們還可以將 SELECT 子句後面的列字段作爲索引來提升查詢性能。索引確實是一種查找數據的高效方式，但是 MySQL 也可以使用索引來直接獲取列的數據，這樣就不再需要讀取數據行。** 如果索引的葉子節點中已經包含要查詢的數據，那麼還有什麼必要再回表查詢呢?** 如果一個索引包含 (或者說覆蓋) 所有需要查詢的字段的值，我們就稱之爲“覆蓋索引”。

覆蓋索引，誰覆蓋了誰？

索引覆蓋了索要查詢的字段。

覆蓋索引是非常有用的工具，能夠極大地提高性能。考慮一下如果查詢只需要掃描索引而無須回表，會帶來多少好處：

不是所有類型的索引都可以成爲覆蓋索引。覆蓋索引必須要存儲索引列的值，而哈希索引、空間索引和全文索引等都不存儲索引列的值，所以 MySQL 只能使用 B-Tree 索引做覆蓋索引。另外，不同的存儲引擎實現覆蓋索引的方式也不同，而且不是所有的引擎都支持覆蓋索引。

4.6.5 重複索引和冗餘索引

MySQL 允許在相同列上創建多個索引，無論是有意的還是無意的。MySQL 需要單獨維護重複的索引，並且優化器在優化查詢的時候也需要逐個地進行考慮，這會影響性能。

重複索引

重複索引是指在相同的列上按照相同的順序創建的相同類型的索引。應該避免這樣創建重複索引，發現以後也應該立即移除。

有時會在不經意間創建了重複索引，例如下面的代碼：

CREATE TABLE test(
	ID INT NOT NULL PRIMARY KEY,
  A INT NOT NULL,
  B INT NOT NULL,
  UNIQUE(ID),
  INDEX(ID)
)ENGINE = InnoDB;

一個經驗不足的用戶可能是想創建一個主鍵，先加上唯一限制，然後再加上索引以供查詢使用。事實上，MySQL 的唯一限制和主鍵限制都是通過索引實現的，因此，上面的寫法實際上在相同的列上創建了三個重複的索引。通常並沒有理由這樣做，除非是在同一列上創建不同類型的索引來滿足不同的查詢需求。

冗餘索引

冗餘索引和重複索引有一些不同。如果創建了索引 (A, B)，再創建索引 (A) 就是冗餘索引，因爲這只是前一個索引的前綴索引。因此索引 (A, B) 也可以當作索引 (A) 來使用 (這種冗餘只是對 B-Tree 索引來說的)。但是如果再創建索引 (B, A)，則不是冗餘索引，索引 (B) 也不是，因爲 B 不是索引 (A,B) 的最左前綴列。另外，其他不同類型的索引(例如哈希索引或者全文索引) 也不會是 B-Tree 索引的冗餘索引，而無論覆蓋的索引列是什麼。

冗餘索引通常發生在爲表添加新索引的時候。例如，有人可能會增加一個新的索引 (AB) 而不是擴展已有的索引 (A)。還有一種情況是將一個索引擴展爲 (A, ID)，其中 ID 是主鍵，對於 InnoDB 來說主鍵列已經包含在二級索引中了，所以這也是冗餘的。

大多數情況下都不需要冗餘索引，應該儘量擴展已有的索引而不是創建新索引。但也有時候出於性能方面的考慮需要冗餘索引，因爲擴展已有的索引會導致其變得太大，從而影響其他使用該索引的查詢的性能。

5. 正確使用索引進行查詢

5.1 前綴索引和索引選擇性

有時候需要索引很長的字符列，這會讓索引變得大且慢。一個策略是前面提到過的模擬哈希索引，這是因爲哈希運算總是能將輸入值轉換爲一個統一長度的值。但是 Hash 索引有其固有的缺陷，應用領域非常窄。

通常可以索引開始的部分字符，這樣可以大大節約索引空間，從而提高索引效率，但這樣也會降低索引的選擇性。

  • 基數 cardinality：不重複的索引值數量；
  • 記錄總數 #T
  • 索引的選擇性：cardinality/#T，範圍從1/#T 到 1 之間。

唯一索引的選擇性是 1，這是最好的索引選擇性，性能也是最好的。

索引的選擇性越高則查詢效率越高，因爲選擇性高的索引可以讓 MySQL 在查找時過濾掉更多的行。

前綴的長度和基於索引的查詢性能呈現一個拋物線的關係，過短和過長都不合適。一般情況下某個列前綴的選擇性也是足夠高的，足以滿足查詢性能。對於 BLOB、TEXT 或者很長的 VARCHAR 類型的列，必須使用前綴索引，因爲 MySQL 不允許索引這些列的完整長度。

總之，標準是：前綴的 “基數” 應該接近於完整列的“基數”。

我們可以通過如下手段來進行表關於某一個字段選擇性的計算。

比如我們現在有個 Employee 表，其中有個 FirstName 字段，是 varchar(50) 的，我們查詢該字段的索引選擇性：

SELECT 1.0*COUNT(DISTINCT FirstName)/count(*)
FROM Employee

假設得到的結果爲：得到結果 0.7500，然後我們希望對 FirstName 建立前綴索引，希望前綴索引的選擇性能夠儘量貼近於對整個字段建立索引時的選擇性。我們先看看 3 個字符，如何：

SELECT 1.0*COUNT(DISTINCT LEFT(FirstName,3)/count(*)
FROM Employee

得到的結果是 0.58784，好像差距有點大，我們再試一試 4 個字符呢：

SELECT 1.0*COUNT(DISTINCT LEFT(FirstName,4)/count(*)
FROM Employee

得到 0.68919，已經提升了很多，再試一試 5 個字符，得到的結果是 0.72297，這個結果與 0.75 已經很接近了，所以我們這裏認爲前綴長度 5 是一個合適的取值。所以我們可以爲 FirstName 建立前綴索引：

alter table test.Employee add key(FirstName(5))

注意事項：建立前綴索引後查詢語句並不需要更改，如果我們要查詢所有 FirstName 爲 Devin 的 Employee，那麼 SQL 仍然寫成：

SELECT *
FROM Employee e
WHERE e.FirstName='Devin';

前綴索引是一種能使索引更小、更快的有效辦法，但另一方面也有其缺點：MySQL 無法使用前綴索引做 ORDER BY 和 GROUP BY，也無法使用前綴索引做覆蓋掃描。

後綴索引 (suffix index) 也有其用途( 例如，找到某個域名的所有電子郵件地址)。MySQL 原生並不支持反向索引，但是可以把字符串反轉後存儲，並基於此建立前綴索引。可以通過觸發器來維護這種索引。

5.2 複合索引的順序與最左前綴匹配原則

最左前綴匹配原則指的是 MySQL 會一直向右匹配直到遇到範圍查詢 (>、<、between、like) 就停止匹配，比如 a = 1 and b = 2 and c > 3 and d = 4 如果建立 (a,b,c,d) 順序的索引，d 是用不到索引的，如果建立 (a,b,d,c) 的索引則都可以用到，a,b,d 的順序可以任意調整。

因爲 MySQL 有查詢優化器，這裏的順序指的是創建索引的順序，和查詢語句中的順序沒有關係。

正確的順序依賴於使用該索引的查詢，並且同時需要考慮如何更好地滿足排序和分組的需要。

這幾基於 B-tree 數據結構進行討論索引順序，對於其他索引可能不具有相關性質，比如 Hash 索引本身就不會按照索引字段進行排序。

在一個多列 B-Tree 索引中，索引列的順序意味着索引首先按照最左列進行排序，其次是第二列，等等。所以，索引可以按照升序或者降序進行掃描，以滿足精確符合列順序的 ORDER BY、GROUP BY 和 DISTINCT 等子句的查詢需求。

在基於 B-Tree 索引數據結構背景強調索引的聲明順序的原因是聯合索引的查詢機制。比如建立了一個 (name,age,sex) 的聯合索引：

注意：在查詢語句中的順序是無關緊要的，比如 WHERE filed1 = 'xx',filed2 = 'mm',filed3 = 'nn' 與WHERE filed3 = 'xx',filed1 = 'mm',filed2 = 'nn' 是沒有任何區別的。

對於如何選擇索引的列順序有一個經驗法則：將選擇性最高的列放到索引最前列。這個建議有用嗎？在某些場景可能有幫助，但通常不如避免隨機 I/O 和排序那麼重要，考慮問題需要更全面 (場景不同則選擇不同，沒有一個放之四海皆準的法則。這裏只是說明，這個經驗法則可能沒有你想象的重要)。

當不需要考慮排序和分組時，將選擇性最高的列放在前面通常是很好的。這時候索引的作用只是用於優化 WHERE 條件的查找。在這種情況下，這樣設計的索引確實能夠最快地過濾出需要的行，對於在 WHERE 子句中只使用了索引部分前綴列的查詢來說選擇性也更高。然而，性能不只是依賴於所有索引列的選擇性 (整體基數)，也和查詢條件的具體值有關，也就是和值的分佈有關。這和前面介紹的選擇前綴的長度需要考慮的地方一樣。可能需要根據那些運行頻率最高的查詢來調整索引列的順序，讓這種情況下索引的選擇性最高。

5.3 索引排序

相信你聽說過這樣的建議：如果有 order by 的需求，給需要排序的字段加上索引，就可以避免數據庫排序操作。

爲了便於說明，我創建一個簡單的表，這個表裏，除了主鍵索引 id 外，還有一個聯合索引 ab。你可以在文稿中看到這個表的定義。

CREATE TABLE t(
	id int(11) NOT NULL,
  a int(11) NOT NULL,
  b int(11) NOT NULL,
  c int(11) NOT NULL,
  PRIMARY KEY(`id`),
  KEY `ab` (`a`,`b`)
) ENGINE = InnoDB;

單字段排序

一個簡單的需求是將這個表的數據，按照 a 的大小倒序返回。你的 SQL 語句可以這麼寫：

SELECT * FROM t WHERE a >0 ORDER BY a DESC;

原文中沒有 WHERE 子句，我額外添加上的，因爲否則在我們 MySQL 版本上會導致不使用索引，最終導致使用 file sort。

我們來看看這個聯合索引 ab 的結構。

可以看到，在這個索引上，數據存儲順序是：

因此上面這個語句的執行流程就是：

  1. 從索引 ab 上，取最右的一個記錄，取出主鍵值 ID_Z；
  2. 根據 ID_Z 到主鍵索引上取整行記錄，作爲結果集的第一行；
  3. 在索引 ab 上取上一個記錄的左邊相鄰的記錄；
  4. 每次取到主鍵 id 值，再到主鍵索引上取到整行記錄，添加到結果集的下一行；
  5. 重複步驟 3、4，直到遍歷完整個索引。

可以看到，這個流程中並不涉及到排序操作。我們也可以用 explain 語句來驗證這個結論。

上圖是這個語句的 explain 的結果，可以看到，Extra 字段中沒有 Using filesort 字樣，說明這個語句執行過程中，不需要用到排序。

組合字段排序

有了上面的分析，我們再來看看下面這個語句：

SELECT * FROM t WHERE a >1 AND b >1 ORDER BY a desc,b desc;

這個語句的意思是，按照 a 值倒序，當 a 的值相同時按照 b 值倒序。

倒序不需要排序，正序呢？正序的語句是這麼寫的：

SELECT * FROM t WHERE a >1 AND b >1 ORDER BY a,b;

顯然，這個語句也是不需要排序的，執行流程上，只需要先取 ab 索引樹最左邊的節點，然後向右遍歷即可。

到這裏我們可以小結一下：

  1. InnoDB 索引樹以任意一個葉節點爲起始點，可以向左或向右遍歷；

  2. 如果語句需要的 order by 順序剛好可以利用索引樹的單向遍歷，就可以避免排序操作。

Descending Indexes

單向遍歷的要求是聯合索引的同時是升序或者降序。

接下來我們來看一種不滿足” 單向遍歷 “的場景。

SELECT * FROM t WHERE a >1 AND b >1 ORDER BY a,b desc;

這個語句要求查詢結果中的記錄排序順序是：按照 a 值正序，對於相同的 a 值，按照 b 值倒序。

由於不滿足單向遍歷的要求，因此只能選擇使用排序操作，如下所示：

extra 字段中 Using filesort 表示使用了排序。

你一定想到了，如果可以讓 InnoDB 在構建索引 ab 的時候，相同的 a 裏面，b 能夠從大到小排序，就又可以滿足單向遍歷的要求了。

如下所示，我們創建一個新表：

CREATE TABLE t2(
  id int(11) NOT NULL,
  a int(11) NOT NULL,
  b int(11) NOT NULL,
  c int(11) NOT NULL,
  PRIMARY KEY(`id`),
  KEY `ab` (`a`,`b` desc)
) ENGINE = InnoDB;

我們將索引 ab 的定義做了修改，在字段 b 後面加上 desc，表示對於相同的 a 值，字段 b 按照倒序存儲。

這個表對應的索引 ab 的結構圖如下：

接着我們再次執行 explain，如下：

Descending Indexes 可以避免這種情況下的排序操作，語句的執行性能自然就提升了。

使用 File sort 和 Index 的不同情況

ORDER BY 主要滿足以下情況，會使用 Index 方式排序：

ORDER BY 語句使用索引最左前列；

比如 (a,b) 聯合索引下，ORDER BY a 、ORDER BY a,b 都是符合要求的，但是如果 ORDER BY b 或者 ORDER BY b,a 這種情況都是不符合要求的。

以下情況，會使用 FileSort 方式的排序：

不全，主要有這兩，總之都可以通過 explain 來檢查語句是否有使用了效率較低的 file sort。

5.4 索引的失效場景

索引一旦失效，就要做全表掃描，效率會有所降低。

6. 索引和鎖

索引可以讓查詢鎖定更少的行。如果你的查詢從不訪問那些不需要的行，那麼就會鎖定更少的行，從兩個方面來看這對性能都有好處。

InnoDB 只有在訪問行的時候纔會對其加鎖，而索引能夠減少 InnoDB 訪問的行數，從而減少鎖的數量。

但這隻有當 InnoDB 在存儲引擎層能夠過濾掉所有不需要的行時纔有效。

在服務器端再進行過濾是無效的。

如果索引無法過濾掉無效的行，那麼在 InnoDB 檢索到數據並返回給服務器層以後，MySQL 服務器才能應用 WHERE 子句。這時已經無法避免鎖定行了：InnoDB 已經鎖住了這些行，到適當的時候才釋放。在 MySQL 5.1 和更新的版本中，InnoDB 可以在服務器端過濾掉行後就釋放鎖，但是在早期的 MySQL 版本中，InnoDB 只有在事務提交後才能釋放鎖。

下面這個例子說明了即使使用索引，InnoDB 還是會鎖住一些不需要的數據 ，但是即使是這樣，索引還是限定了會被鎖定的行數，如果不能使用索引查找和鎖定行的話問題可能會更糟糕，MySQL 會做全表掃描並鎖住所有的行，而不管是不是需要。

下面是一個例子：

SET AUTOCOMMIT =0;
BEGIN;
SELECT actor_id FROM sakila.actor where actor_id < 5
AND actor_id <> 1 FOR UPDATE;

FOR UPDATE 是在數據庫中上鎖用的，用於爲數據庫中的行上一個排它鎖；當一個事務的操作未完成時候 ，其他事務可以讀取但是不能寫入或更新。

這條查詢僅僅會返回 2~4 之間的行，但是實際上獲取了 1~4 之間的行的排他鎖。

InnoDB 會鎖住第 1 行，這是因爲 MySQL 爲該查詢選擇的執行計劃是索引範圍掃描：

換句話說，底層存儲引擎的操作是 “從索引的開頭開始獲取滿足條件 actor_ id< 5 的記錄”，服務器並沒有告訴 InnoDB 可以過濾第 1 行的 WHERE 條件。注意到 EXPLAIN 的 Extra 列出現了 **“Using where”，這表示 MySQL 服務器將存儲引擎返回行以後再應用 WHERE 過濾條件 **。

7. 減少索引和數據碎片

B-Tree 索引可能會碎片化，這會降低查詢的效率。碎片化的索引可能會以很差或者無序的方式存儲在磁盤上。

根據設計，B-Tree 需要隨機磁盤訪問才能定位到葉子頁，所以隨機訪問是不可避免的。然而，如果葉子頁在物理分佈上是順序且緊密的，那麼查詢的性能就會更好。否則，對於範圍查詢、索引覆蓋掃描等操作來說，速度可能會降低很多倍；對於索引覆蓋掃描這一點更加明顯。

表的數據存儲也可能碎片化。然而，數據存儲的碎片化比索引更加複雜。有三種類型的數據碎片。

對於 MyISAM 表，這三類碎片化都可能發生。但 InnoDB 不會出現短小的行碎片；InnoDB 會移動短小的行並重寫到一個片段中。

可以通過執行 0PTIMIZE TABLE 或者導出再導入的方式來重新整理數據。這對多數存儲引擎都是有效的。對於一些存儲引擎如 MyISAM，可以通過排序算法重建索引的方式來消除碎片。老版本的 InnoDB 沒有什麼消除碎片化的方法。不過最新版本 InnoDB 新增了 “在線” 添加和刪除索引的功能，可以通過先刪除，然後再重新創建索引的方式來消除索引的碎片化。

引用：

本文由 Readfog 進行 AMP 轉碼，版權歸原作者所有。
來源：https://spongecaptain.cool/post/mysql/mysqlindexsummary/

猜你喜歡