InnoDB索引

1、索引的建立 / 數據的存儲

? 一條條數據存儲到頁中后，各個數據頁組成了一個雙向鏈表，而每個數據頁中的記錄會按照主鍵值從小到大的順序組成一個單向鏈表。此時，如果我想根據主鍵值查詢一條記錄，只能從第一個數據頁開始一個頁一個頁地去查詢，這種全表搜索方式的效率想想也不會很高，因此 MySQL 選擇為每一個存儲了用戶數據的數據頁建立目錄，通過目錄確定目標數據在哪個頁，然后再在目標頁中根據 Page Directory (頁目錄) + 二分法查詢目標數據。這種方式的前提條件就是下一個數據頁中用戶記錄的主鍵值必須大于上一個頁中用戶記錄的主鍵值，即保證數據的有序性，保證二分法的可用。我們稱數據頁中存儲的該種數據為目錄項記錄，稱存儲的用戶自定義內容為用戶項記錄，以此來區分。

? 存儲目錄項記錄、用戶項記錄用的都是數據頁(頁面類型一致)，都會為主鍵值生成 Page Directory（頁目錄），從而在按照主鍵值進行查找時可以使用二分法來加快查詢速度。只不過前者存儲的列只有主鍵值(頁中最小主鍵值)和頁號，而后者不僅存有用戶自定義內容，還有 InnoDB 隱藏列；前者記錄頭信息的 record_type = 1(代表目錄項記錄)，后者 record_type = 0(代表普通記錄)。因為在這些目錄頁中只存儲了主鍵值和頁號，所以能夠記錄很多數據，但隨著數據的增多，加上頁面大小默認為 16KB，遲早會出現一張表不足以記錄所有的目錄項記錄，那就只能再新增一頁，這些頁也存有上一個和下一個頁的頁號，以此也構成一個雙向鏈表。

? 由此可見，隨著數據的增多，目錄項記錄數據頁也將變成一個雙向鏈表，那我們再根據主鍵查詢時，又回到了原始問題，即需要一頁一頁遍歷這個雙向鏈表來找到目錄項記錄頁。為了解決這個問題，只能再為創建一個更高的目錄，這樣的話，就形成了一個多級目錄，層層嵌套，最終的小目錄(葉子節點)存儲的才是真實數據。

? 在InnoDB存儲引擎中，聚簇索引就是數據的存儲方式（所有的用戶記錄都存儲在了葉子節點），也就是所謂的索引即數據，數據即索引。

? 以上過程是從葉子節點到根節點構建B+樹的角度來描述聚簇索引的構建過程，但是實際上B+樹的構建過程是這樣的：

每當為某個表創建一個B+樹索引（聚簇索引不是人為創建的，默認就有）的時候，都會為這個索引創建一個根節點頁面。最開始表中沒有數據的時候，每個B+樹索引對應的根節點中既沒有用戶記錄，也沒有目錄項記錄。
隨后向表中插入用戶記錄時，先把用戶記錄存儲到這個根節點中。
當根節點中的可用空間用完時繼續插入記錄，此時會將根節點中的所有記錄復制到一個新分配的頁，比如頁a中，然后對這個新頁進行頁分裂的操作，得到另一個新頁，比如頁b。這時新插入的記錄根據鍵值（也就是聚簇索引中的主鍵值，二級索引中對應的索引列的值）的大小就會被分配到頁a或者頁b中，而根節點便升級為存儲目錄項記錄的頁。
當頁b存儲空間用完時，則重復第三步進行頁分裂，創建頁c用于存儲新記錄，并將根節點指向頁c。

? 一個B+樹索引的根節點自誕生之日起，便不會再移動。這樣只要我們對某個表建立一個索引，那么它的根節點的頁號便會被記錄到某個地方，然后凡是InnoDB存儲引擎需要用到這個索引的時候，都會從那個固定的地方取出根節點的頁號，從而來訪問這個索引，也就是常說的聚簇索引的頂層常駐內存。

2、重點概念：

2.1 頁分裂：

? 假設此時聚簇索引只有一個葉子節點，且存儲空間（16KB）已滿，此時想向表中插入一條記錄，這條記錄的主鍵id在已有主鍵的范圍內，也就是說這條記錄的主鍵并不是最大的，所以需要新增一個數據頁，將舊數據頁中的最大記錄移到新頁中，將新增記錄按主鍵大小順序插入到舊頁中，這個過程就被稱為頁分裂。

2.2 聚簇索引

使用記錄主鍵值的大小進行記錄和頁的排序，這包括三個方面的含義：
- 頁內的記錄是按照主鍵的大小順序排成一個單向鏈表。
- 各個存放用戶記錄的頁也是根據頁中用戶記錄的主鍵大小順序排成一個雙向鏈表。
- 存放目錄項記錄的頁分為不同的層次，在同一層次中的頁也是根據頁中目錄項記錄的主鍵大小順序排成一個雙向鏈表。
B+樹的葉子節點存儲的是完整的用戶記錄。
- 所謂完整的用戶記錄，就是指這個記錄中存儲了所有列的值（包括隱藏列）。
目錄項記錄中是主鍵+頁號

2.3 非聚簇索引

使用記錄c2列的大小進行記錄和頁的排序，這包括三個方面的含義：
- 頁內的記錄是按照c2列的大小順序排成一個單向鏈表。
- 各個存放用戶記錄的頁也是根據頁中記錄的c2列大小順序排成一個雙向鏈表。
- 存放目錄項記錄的頁分為不同的層次，在同一層次中的頁也是根據頁中目錄項記錄的c2列大小順序排成一個雙向鏈表。
B+樹的葉子節點存儲的并不是完整的用戶記錄，而只是c2列+主鍵這兩個列的值。
目錄項記錄中不再是主鍵+頁號的搭配，而變成了c2列+頁號的搭配。

2.4 回表：

? 聚簇索引中葉子節點的value部分存儲的是行數據，而非聚簇索引中葉子節點的value部分存儲的是主鍵值。當查詢中使用到了索引 k，就需要先搜索k索引樹找到對應的主鍵值，再根據主鍵值搜索主鍵索引樹，這樣才能獲取到所要查詢的值，這個過程就被稱為回表。

2.5 覆蓋索引：

? 如果執行的語句是select ID from T where k between 3 and 5，這時只需要查ID的值，而ID的值已經在k索引樹上了，因此可以直接提供查詢結果，不需要回表。也就是說，在這個查詢里面，索引k已經“覆蓋了”我們的查詢需求，我們稱為覆蓋索引。

? 由于覆蓋索引可以減少樹的搜索次數（減少回表的次數），顯著提升查詢性能，所以使用覆蓋索引是一個常用的性能優化手段。

2.6 索引下推

3、使用

3.1 使用場景

1、用于條件匹配

如果想要借助聯合索引優化查詢時，必須遵循“最左匹配原則”。

全值匹配
匹配左邊的列
匹配列前綴
匹配范圍值
精確匹配某一列并范圍匹配另外一列

2、用于排序

3、用于分組

3.2 創建索引注意事項

1、只為用于搜索、排序或分組的列創建索引：

? ? 對于經常出現在查詢列表，但不參與 or 很少參與條件篩選的字段無需創建索引。

2、為列的基數大的列創建索引：

? ? 為字段構建索引樹的時，需要對字段進行排序，以基數為 1 的字段舉例，此時字段值都相同，給它排序沒有任何意義（排不排序結果一樣），不能提升查詢效率，反而在增刪改的時候還要對索引樹進行維護，因此最好為基數大的列創建索引，為基數太小列的建立索引效果可能不好。

3、索引列的類型盡量小：

數據類型越小，在查詢時進行的比較操作越快（CPU層次）
數據類型越小，索引占用的存儲空間就越少，在一個數據頁內就可以放下更多的記錄，從而減少磁盤I/O帶來的性能損耗，也就意味著可以把更多的數據頁緩存在內存中，從而加快讀寫效率。

4、可以只對字符串值的前綴建立索引：

? ? 當對長度很長的字符串建立索引時，其索引結構的存儲將會花費較大的空間，其次在進行字符串比較時也會花費較多的時間，此時我們可以做一個居中的選擇，只為字符串的前幾位字符建立索引。

5、只有索引列在比較表達式中單獨出現才可以適用索引：

? ? 索引列加入運算 or 使用函數會造成索引失效。

6、為了盡可能少的讓聚簇索引發生頁面分裂和記錄移位的情況，建議讓主鍵擁有AUTO_INCREMENT屬性：

? ? 一般我們新增記錄時不會指定主鍵是多少，而是采用自增的形式。因為如果指定主鍵進行插入的話，很有可能沒按主鍵從小到大的順序插入，但是為了保證快速查詢，MySQL會對不按大小順序插入的數據進行移位、頁分裂，造成不必要的性能損耗。

7、定位并刪除表中的重復和冗余索引：

? ? 避免出現重復、冗余的索引，以避免對其進行的維護成本。

8、盡量使用覆蓋索引進行查詢，避免回表帶來的性能損耗

4、面試常問

4.1 MySQL索引的底層實現（簡單描述）：

? 它實際上是一個B+樹，首先當我們存入數據時，它會基于數據進行一個排序，排序之后，會使用指針以鏈表的形式連接起來，同時mysql在底層為了進一步優化，基于頁的形式進行管理索引，也就是對我們的數據進行了一頁一頁的存儲，默認頁的大小為16KB。站在整個B+樹這個數據結構來講，一個三層的B+樹可存儲進8億-10億左右的數據，所以一般的項目用兩層足矣。站在一個兩層的B+結構來講，如果基于主鍵查詢，最多動用一次磁盤IO，因為它的頂層是常駐內存的。

4.2 索引為什么是 B+樹,而不是 B樹呢?

參考資料: B樹、B+樹詳解 - Assassinの - 博客園

原因：

??? B-Tree結構圖中可以看到每個節點中不僅包含數據的key值，還有data值。而每一個頁的存儲空間是有限的，如果data數據較大時將會導致每個節點（即一個頁）能存儲的key的數量很小，當存儲的數據量很大時同樣會導致B-Tree的深度較大，增大查詢時的磁盤I/O次數，進而影響查詢效率。在B+Tree中，所有數據記錄節點都是按照鍵值大小順序存放在同一層的葉子節點上，而非葉子節點上只存儲key值信息，這樣可以大大加大每個節點存儲的key值數量，降低B+Tree的高度。

實際情況：

B+Tree中每個節點可能不能填充滿，因此在數據庫中，B+Tree的高度一般都在2~4層。
mysql的InnoDB存儲引擎在設計時是將根節點常駐內存的，也就是說查找某一鍵值的行記錄時最多只需要1~3次磁盤I/O操作。

總結：B+Tree只有葉子節點可以存儲數據，而B-Tree非葉子節點也必須存儲數據，當存儲的數據量很大時，會導致B-Tree的深度較大，增大查詢時的磁盤I/O次數，進而影響查詢效率。

4.3 使用聚簇索引的優勢：

問題：每次使用輔助索引檢索都要經過兩次B+樹查找，看上去聚簇索引的效率明顯要低于非聚簇索引，這不是多此一舉嗎？聚簇索引的優勢在哪？
1.由于行數據和聚簇索引的葉子節點存儲在一起，同一頁中會有多條行數據，訪問同一數據頁不同行記錄時，已經把頁加載到了Buffer中（緩存器），再次訪問時，會在內存中完成訪問，不必訪問磁盤。這樣主鍵和行數據是一起被載入內存的，找到葉子節點就可以立刻將行數據返回了，如果按照主鍵Id來組織數據，獲得數據更快。
2.輔助索引的葉子節點，存儲主鍵值，而不是數據的存放地址。好處是當行數據放生變化時，索引樹的節點也需要分裂變化；或者是我們需要查找的數據，在上一次IO讀寫的緩存中沒有，需要發生一次新的IO操作時，可以避免對輔助索引的維護工作，只需要維護聚簇索引樹就好了。另一個好處是，因為輔助索引存放的是主鍵值，減少了輔助索引占用的存儲空間大小。

4.4 聚簇索引需要注意什么?

當使用主鍵為聚簇索引時，主鍵最好不要使用uuid，因為uuid的值太過離散，不適合排序且可能出線新增加記錄的uuid，會插入在索引樹中間的位置，導致索引樹調整復雜度變大，消耗更多的時間和資源。
建議使用int類型的自增，方便排序并且默認會在索引樹的末尾增加主鍵值，對索引樹的結構影響最小。而且，主鍵值占用的存儲空間越大，輔助索引中保存的主鍵值也會跟著變大，占用存儲空間，也會影響到IO操作讀取到的數據量。

4.5 為什么要設置主鍵自增？

保證每一行數據都有一個唯一標識符，使數據具有唯一性
設置主鍵自增可以使索引建立時避免數據的重排(數據無序時需要排序，使數據按從小到大的順序排列)，從而提高插入性能

注：數據的重排可能會出現頁分裂。比如，將一條記錄插入到一個數據頁中的兩條記錄之間時，此時數據頁已經滿了，根據 B+ 樹的算法，這時候需要申請一個新的數據頁，然后挪動部分數據過去。這個過程稱為頁分裂。

4.6 索引失效情況：

查詢語句中使用LIKE關鍵字：在查詢語句中使用 LIKE 關鍵字進行查詢時，如果匹配字符串的第一個字符為“%”，索引不會被使用。如果“%”不是在第一個位置，索引就會被使用。
查詢語句中使用多列索引：多列索引是在表的多個字段上創建一個索引，只有查詢條件中使用了這些字段中的第一個字段，索引才會被使用。
查詢語句中使用OR關鍵字：查詢語句只有OR關鍵字時，如果OR前后的兩個條件的列都是索引，那么查詢中將使用索引。如果OR前后有一個條件的列不是索引，那么查詢中將不使用索引。