索引

數據庫中的數據是以記錄為單位的，如果一條一條進行查找，幾十萬數據就已經到了查找的瓶頸，如果上百萬數據的話，查找就會非常的浪費時間。

索引的價值在于提高海量數據的檢索速度，只要執行了正確的創建索引的操作，查詢速度就可能提高成百上千倍。當一張表創建索引后，在數據庫底層就會為表中的數據記錄構建特定的數據結構，后續在查詢表中數據時就能通過查詢該數據結構快速定位到目標數據。

索引雖然提高了數據的查詢速度，但在一定程度上也會降低數據增刪改的效率，因為這時在對表中的數據進行增刪改操作時，除了需要進行對應的增刪改操作之外，可能還需要對底層建立的數據結構進行調整維護。

索引分類：主鍵索引、唯一索引、普通索引、組合索引、以及全文索引（elasticsearch）；

主鍵索引

主鍵索引指是一個非空唯一索引，一個表只有一個主鍵索引，在 innodb 中，主鍵索引的 B+ 樹包含表數據信息。

PRIMARY KEY(key1, key2)

唯一索引

UNIQUE(key)

唯一索引是某一列不會出現相同的值，但是可以是 NULL 值；

普通索引

普通索引是指某一列允許出現相同的索引內容，也可以為NULL 值；

INDEX(key)
-- OR
KEY(key[,...])

組合索引

組合索引所指的就是對表上的多個列進行索引。

INDEX idx(key1,key2[,...]);
UNIQUE(key1,key2[,...]);
PRIMARY KEY(key1,key2[,...]);

全文索引

將存儲在數據庫當中的整本書和整篇文章中的任意內容信息查找出來的技術，關鍵詞 FULLTEXT，在短字符串中用 LIKE % ，在全文索引中用 match 和 against 。

主鍵選擇

InnoDB 中的表是索引組織表，每張表有且僅有一個主鍵，主鍵的選擇就會存在以下幾種情況：

• 如果顯示的設置 PRIMARY KEY ，則該設置的 KEY 為該表的主鍵；
• 如果沒有顯示的設置，則從非空唯一索引中進行選擇，會出現以下兩種情況：
  情況一：只有一個非空唯一索引，就會選擇該索引作為主鍵索引；
  情況二：存在多個非空唯一索引，選擇聲明的第一個為主鍵；
• 沒有非空唯一索引，則自動生成一個 6 字節的 _rowid 作為主鍵。

約束

為了實現數據的完整性，對于 innodb，提供了以下幾種約束，primary key，unique key，foreign key，default，not null。

• primary key：非空唯一約束；
• unique key：唯一約束；
• foreign key：外鍵約束；
• default：默認值約束;
• not null：非空約束。

這兒需要特別介紹一下外鍵約束，他其實就是將幾張表給聯系起來，就像下面這樣：

create table parent (
id int not null,
primary key(id)
) engine=innodb;
create table child (
id int,
parent_id int,
foreign key(parent_id) references parent(id) ON DELETE CASCADE ON UPDATE
CASCADE
) engine=innodb;
-- 被引用的表為父表，引用的表稱為子表；
-- 外鍵定義時，可以設置行為 ON DELETE 和 ON UPDATE，行為發生時的操作可選擇：
-- CASCADE 子表做同樣的行為
-- SET NULL 更新子表相應字段為 NULL
-- NO ACTION 父類做相應行為報錯
-- RESTRICT 同 NO ACTION
INSERT INTO parent VALUES (1);
INSERT INTO parent VALUES (2);
INSERT INTO child VALUES (10, 1);
INSERT INTO child VALUES (20, 2);

child 表跟 parent 就通過外鍵約束聯系在一起，如果我們刪除 child 表中的某一行數據，那么對應的 parent 表中的某個數據也會被刪除掉，這就是外鍵約束。

約束是數據庫為我們提供的一種安全的方式，索引和約束的不同點就在于創建主鍵索引或者唯一索引的時候同時創建了相應的約束，但是約束時邏輯上的概念，索引是一個數據結構既包含邏輯的概念也包含物理的存儲方式。

索引實現

B+樹

Innodb 中的索引的數據結構是一顆 B+ 樹結構，首先我們來介紹一下 B+ 樹：

B+樹

B+ 樹是一顆多路平衡搜索樹，他的結構通過中序遍歷也是有序地，B+ 樹通常是用來減少磁盤訪問次數，組織磁盤數據，以頁為單位，物理磁盤頁一般為 4K，innodb 默認頁大小為 16K，對頁的訪問是一次磁盤 IO，緩存中會緩存常訪問的頁。

下面就是一顆 B+ 樹索引的結構，注意，每一個索引都對應著一顆 B+ 樹：

B+ 樹索引結構存在一個特征，非葉子節點只存儲索引信息，葉子節點存儲具體數據信息，葉子節點之間互相連接，結點的大小是 16 KB，映射的連續的磁盤頁，方便范圍查詢。

B+ 樹方便范圍查詢的點就在于我不需要每次查詢都從根節點進行遍歷，而是一次查詢就可以去搞定，從而來減少磁盤的 IO 次數的，就像下圖一樣，一次 IO 就能搞定：

為什么B+ 樹映射的連續的磁盤頁？

因為映射連續的磁盤頁就是以順序 IO 的形式對磁道進行訪問，如果當次IO給出的扇區地址與上次IO結束的扇區地址是連續的，那磁頭就能很快的開始這次IO操作，這樣的多個IO操作就會加快對應的訪問效率。

因此 B+ 樹索引的優點就可以總結為以下幾點：

聚集索引

按照主鍵構造的 B+ 樹，葉子節點中存放數據頁，數據也是索引的一部分。

比如說我們當前需要查找 id 大于并且小于 40 的所有學生，就會使用如下方式進行查詢：

輔助索引

葉子節點不包含行記錄的全部數據，輔助索引的葉子節點中，除了用來排序的 key 還包含一個bookmark ，該書簽存儲了聚集索引的 key。

比如說我們需要查找 teacher_id = 33 的老師的所有信息，就會采用如下的查找方式：

因為在輔助索引的葉子結點中存儲了一個聚集索引的書簽，當我們找到對應的節點以后，此時就需要進行一個回表查詢，又重新回到聚集索引當中，查找對應的信息，然后再進行返回數據，相對于聚集索引來說他多出來一步回表查詢的操作。

索引存儲

innodb 由段、區、頁組成；段分為數據段、索引段、回滾段等，區大小為 1 MB（一個區由 64 個連續頁構成），頁的默認值為 16k，頁為邏輯頁，磁盤物理頁大小一般為 4K 或者 8K，為了保證區中的頁連續，存儲引擎一般一次從磁盤中申請 4~5 個區。

innodb 體系結構

對于 MySQL 來說，光實現以上的策略是不夠的，因為每一次訪問 B+ 樹的結點都會觸發一次 IO ，采用上面的策略了，還是會有多次磁盤 IO，所以在 MySQL 中還設計了一個 bufferpool 緩存表和索引數據；采用 LRU 算法（原理如下圖）讓 Buffer pool 只緩存比較熱的數據 。

正常情況下我們刷盤操作是要經過 page cache 的，但是 page cache 屬于內核態，我們無法去定制我們自己的一個刷盤策略，所以就需要在用戶態設計一個 Buffer pool ，然后制定我們的刷盤策略，通過 Direct IO 的方式，直接將數據刷入到磁盤當中。

我們再來看一張圖示結構：
從上圖就可以看出，在我們的內存結構當中是存在一個 Buffer pool 的，這個 Buffer pool 就是用來緩存對應的熱點數據的，也就是說，我們對于寫數據并不是直接對磁盤空間進行操作的，而是先將其寫進用戶態的 Buffer pool 中，然后最終通過 Direct IO 的方式，將數據直接刷入到磁盤中。

我們來看一下 Buffer pool 的結構：

Buffer pool 中使用的是 LRU （最近未被使用）的淘汰策略，通過上圖我們可以看出來，在 MySQL 中數據的插入的方式是選擇中間的位置進行插入的，原因就在于，我們并不認為最新被插入的數據就是熱點數據，所以并不會選擇在開頭位置進行插入，只有當我們多次對該數據進行訪問以后，他就會被挪到前面的位置，而一個數據如果長時間不被訪問到，就會被移動到后面的位置，最終通過 LRU 策略把這些數據輸入到磁盤當中。

Buffer pool 中緩存的是聚集索引也就是表和索引的數據，對于輔助索引的數據，是存在 Change buffer 中的，當我們需要讀取非唯一索引的數據時， Change buffer 當中的數據就會異步的 Merge 到 Buffer pool 當中去，同時他也會定期的同步到索引頁當中去。

如下圖所示，free list 組織 buffer pool 中未使用的緩存頁；flush list 組織 buffer pool 中臟頁，也就是待刷盤的頁；lru list 組織 buffer pool 中冷熱數據，當 buffer pool 沒有空閑頁，將從 lru list 中最久未使用的數據進行淘汰。

Redlog

Buffer pool 是存在于內存當中的，如果服務器突然宕機了，此時 Buffer pool 當中的數據就沒有了，我們當然不能讓這些數據都丟失，我們會將這些數據寫入到 Redlog 中去，如果出現宕機，我們就會保證 MySQL 在重啟以后將這些數據從 Redlog 中再重新讀取回來。

我們可以看見，內存中是存在一個 Log Buffer 的，它采用的就是正常將數據刷入到 page cache 中，然后再將 page cache 中的數據刷入 Redlog 當中，Redlog 當中的數據也是一頁一頁連續進行存儲的，這也方便我們在讀取 Redlog 中數據的時候提高對應的效率。

整體總結下來就是 MySQL 的索引采用的 B+ 樹的結構，保證數據訪問的一個高效，然后又通過在內存中的 Buffer pool 結構，減少磁盤 IO 的操作。

最左匹配原則

對于組合索引，從左到右依次匹配，遇到 > ，< ，between ，like 就停止匹配。

如何理解上面這句話，我們來看一張表結構：

上面這張表中普通索引設置為組合索引，其中主鍵索引為 id，普通索引為name，cid，最左匹配規則就是我們在查詢的過程中首先會以 name 來進行比較，如果 name 一樣我們才會去使用 cid。

比如下面這兩句查詢語句：

這一個查詢語句 where 后面使用的是 name，此時就會踩到我們的索引結構，那么他首先會去輔助索引中進行查詢，然后回表查詢到聚集索引當中。

再看這一個查詢語句，因為我們設置的最左索引為 name，此時條件為 cid了，那么就不滿足最左匹配的原則，就不會踩到對應的索引，也就意味著此時會去聚集索引中進行全表查詢，全表查詢的速度是最慢的。

我們再看下面這句查詢語句，我們可以看見當前他也是踩了索引的，因為這兒會進行優化，總是執行最左匹配的條件的，name 就為我們的最左匹配規則。

其中 type 表示的顯示訪問類型，采用怎么樣的方式來訪問數據，效率從好到壞依次為：
system > const > eq_ref > ref > fulltext > ref_or_null > index_merge > unique_subquery >index_subquery > range > index > ALL

覆蓋索引

從輔助索引中就能找到數據，而不需通過聚集索引查找，利用輔助索引樹高度一般低于聚集索引樹，會進行較少磁盤 IO。

覆蓋索引并不表示索引，他表示的是一種選擇策略。

通過下面這張表就可以看出來，第二句查詢語句走的策略就是覆蓋索引，因為輔助索引 B+ 樹結構中除了包含普通索引信息之外還包含主鍵索引，我們此時需要查詢的 3 個信息均可以在輔助索引中找到，就不需要進行回表查詢。

索引下推

索引下推是為了減少回表次數，提升查詢效率，在 MySQL 5.6 的版本開始推出的。

MySQL 架構分為 server 層和存儲引擎層，沒有索引下推機制之前，server 層向存儲引擎層請求數據，在 server 層根據索引條件判斷進行數據過濾；有索引下推機制之后，將部分索引條件判斷下推到存儲引擎中過濾數據，這樣就可以減少回表次數，最終由存儲引擎將數據匯總返回給 server 層。

索引失效

首先我們創建一張下面這樣的表，然后在插入一些數據：

• select ... where A and B 若 A 和 B 中有一個不包含索引，則索引失效；
  
• 索引字段參與運算，則索引失效；例如： from_unixtime(idx) = '2021-04-30'，需要改成 idx = unix_timestamp("2021-04-30")就不會索引失效
  
• 索引字段發生隱式轉換，則索引失效；例如：將列隱式轉換為某個類型，實際等價于在索引列上作用了隱式轉換函數；
  
• LIKE 模糊查詢，通配符 % 開頭，則索引失效；例如： select * from user where name like ‘%Mark’;
  
• 在索引字段上使用 NOT <> != 索引失效，如果判斷 id <> 0 則修改為 idx > 0 or idx < 0 ；
• 組合索引中，沒使用第一列索引，索引失效。

索引原則

索引原則這塊兒涉及到數據類型，可以去看一下之前的一篇文章MySQL數據類型，索引設計的原則包含以下幾個方面：

• 查詢頻次較高且數據量大的表建立索引，索引選擇使用頻次較高，過濾效果好的列或者組合；
• 使用短索引，這樣可以讓節點包含的信息多，進行較少磁盤 IO 操作；比如： smallint ， tinyint等；
• 對于很長的動態字符串，考慮使用前綴索引：
• 對于組合索引，考慮最左側匹配原則、覆蓋索引；
• 盡量選擇區分度高的列作為索引，該列的值相同的越少越好；
• 盡量擴展索引，在現有索引的基礎上，添加復合索引，最多 6 個索引；
• 不要 select * ， 盡量只列出需要的列字段，方便使用覆蓋索引；
• 索引列，列盡量設置為非空；
• 可選：開啟自適應 hash 索引或者調整 change buffer。