前言
索引對于DB查詢的性能起到至關重要的作用。對于索引如何提升查詢性能，通常都會拿查字典來做類比。字典前面會有拼音索引，我們查字典會先查拼音索引，以此來提高查字典的速度。對于這個類比，我們可以思考的更深入點，看看通過拼音索引提升查詢速度的根本原因是什麼。我們考慮如下幾個問題：
1、通過拼音索引能直接定位到字的具體位置嗎？
不能，拼音索引隻能定位到字所在的頁，如果想找到所要的字或者詞，還需要在頁中再次定位。這個過程和InnoDB的索引設計相同，通過索引隻能定位到資料所在頁。
2、定位到頁後，如何定位到具體字的？
定位到頁後，我們一般是從第一個字開始向後查找我們所要的字。或者一眼望過去随機找到所要的字。如果DB也采用這種方式将會比較耗時，因為DB中一頁中存儲的資料比較多。InnoDB采用了稀疏索引來提升查詢頁内查找速度。頁内資料按主鍵順序存放，為主鍵建立稀疏索引。顧名思義，稀疏索引隻為部分鍵值建立索引，通過索引直接定位到資料所在區間段。區間内再進行查找。這樣可以兼顧速度和空間占用。關于稀疏索引我們後面再詳細介紹。
3、如果查找“照”這個字，使用拼音索引定位拼音zhao的過程是怎樣的？
你肯定不會從A開始往後逐字母查到Z。你應該會先定位到拼音索引最後幾頁，然後翻到最後一頁，在此頁中找到Z。提出這個問題，其實我是想出入索引的查找機制，也就是如何高效的在索引中定位到想要的值。按照順序周遊查找顯然是效率最低的查找方式。人類可以通過自己的經驗得出Z在索引的最後，但是DB沒有這個能力。DB依賴查找算法來定位資料。查找相關算法我們應該再熟悉不過了，InnoDB采用的是B+樹的資料結構來組織索引資料以提升查找速度。在下一節會重點介紹相關算法。
通過和字典類比，我們已經大緻了解了索引的作用和定位資料的過程。資料庫定位資料和用字典查字的過程很像。我們在學習索引的過程中，可以多回顧字典查字的例子。
索引相關算法
二分查找
如果不考慮查找算法，索引鍵值可以以數組或者連結清單的資料結構來儲存。為了查找更快，我們進一步将索引值按字典順序儲存。這樣我們就可以采用二分法快速查找。
二分查找法首先需要将資料按順序排列。先用查找的值比較中間位置數值。如果查找的數值更小，那麼查找的範圍縮小一半，隻需要再按同樣的方式查找中間位置的左半部分。反之，則在右半部分進行查找。
可以看到二分查找法，每比較一次都會縮小一半查找範圍，直至找到數值。
我們以下圖為例，看看用二分查找法查找 52 所在位置的過程：
資料庫中的檢索也會用到二分查找法。我們都知道資料庫采用B+數組織索引，但是通過B+樹隻能定位到你所要的資料所在的頁。在頁的内部定位資料時，采用的是二分查找法。字典通過拼音索引也隻能定位到頁，頁内需要再次查找到你所要的字。
二叉樹和平衡二叉樹
二叉樹
二叉樹左子樹鍵值小于根節點鍵值，右子樹鍵值大于根節點鍵值。我們看下面這個二叉樹：
可以看到以上二叉樹中查找52的過程也是三步，查找路徑是37->56->52。 這和二分查找法完全一樣。這是因為這棵二叉樹額外滿足了其他的一些條件。
還是這些資料，我們還可以構造如下二叉樹：
可以看到這次的二叉樹直到第8層才有了左側子樹。1到7層雖然也滿足二叉樹的定義，但實際上已經退化為連結清單。用這個二叉樹進行查找，效率幾乎和順序查找一樣了。
平衡二叉樹
第二個二叉樹為什麼查找效率會低呢？因為這個二叉樹失衡了，左輕右重，已經近乎退化為連結清單。失去了二叉查找樹的意義。此時我們引出平衡二叉樹。平衡二叉樹在二叉樹的基礎上，還需要滿足任意根節點的左右子樹高度差不能超過1。上文二叉樹的兩個例子，第一個是平衡二叉樹，第二個不是平衡二叉樹。
平衡二叉樹的查找效率非常高。因為它的根節點就是二分查找的中間位置資料。每一顆子樹都是如此。換句話講，平衡二叉樹已經按照我們想要的二分查找方式構造好了資料結構。
平衡二叉樹的資料結構比對查詢方式，是以查詢很快。但反過來維護平衡二叉樹的資料結構，則需要付出較大的代價。有更新的發生時，可以通過一次或者多次左旋、右旋來保持平衡。本文就不再展開講平衡二叉樹的維護。
B+樹
B+樹也是一種平衡查找樹，它是為磁盤或其他直接存取輔助裝置設計的一種平衡樹。我們直接看下面的B+樹例子，該例子是以學号為索引構造的學生資料B+樹：
可以看到非葉子節點存儲的隻是索引鍵值（學号）以及子節點的指針。完整資料存儲在葉子節點中。葉子節點中的資料是按照順序排列的。葉子節點存儲完整資料，非葉子節點則是構造的索引值的平衡樹。對于給定的索引值，可以通過B+樹快速定位到葉子節點。然後在葉子節點内部再次定位到完整的一行資料。
在B+樹的維護過程中可能會出現拆分頁的現象。由于B+樹主要用于磁盤，這意味着大量的磁盤操作。是以如果表的索引很多，在大資料量寫入過程中，由于需要大量維護B+樹的操作。那麼磁盤IO和CPU使用都會大幅上升。
B+樹索引
InnoDB 中采用 B+ 樹資料結構來存儲索引，是以稱之為B+樹索引。B+樹索引又分為聚集索引和輔助索引。每張表有且僅有一個聚集索引。簡單來說聚集索引就是以主鍵構造的B+樹索引。而輔助索引則是根據表中索引列構造的B+樹索引。
聚集索引
InnoDB中，表中資料按照主鍵順序存放。聚集索引就是按照主鍵順序構造的B+樹索引。聚集索引中，葉子節點其實就是真實存放資料的頁。這意味着聚集索引的葉子節點存放完整資料。而非葉子節點存放的則是主鍵值和子節點的引用。是以通過主鍵檢索非常快，原因是能夠直接定位到資料。
輔助索引
我們經常說為表加索引，實際添加的就是輔助索引。輔助索引的葉子節點并不是資料存儲的頁。這是為什麼呢？首先，B+樹的葉子節點是有序的。資料頁已經按照主鍵順序存儲了，是以就無法再按照别的順序存儲。此外，如果我們按照添加的索引字段順序把完整的資料多存儲一份，不但會有很大的備援，而且當資料發生變化時會有一緻性的問題。這也是不可取的。是以，InnoDB采用的方式是，輔助索引的葉子節點中存儲的資料隻是主鍵值。葉子節點中的主鍵值按照目前索引字段的順序儲存。
使用輔助索引查詢時，在輔助索引B+樹上隻能定位到符合條件的主鍵值。資料庫拿到主鍵值後還需要用聚集索引再做一次查詢拿到完整的資料。
稀疏索引
如果我們不是為所有的資料都加上索引，而是以一定的步長去添加索引，那麼這就是稀疏索引。
我們看個例子，學生表中有10名學生的資料，按照學号建立索引如下：
如果我們按照3為步長來索引這10名學生（稀疏索引），那麼索引如下：
可以看到稀疏索引隻能定位到某個學生的所在區間段。區間段内需要二次查找。例如我們想要查詢學号為5的學生資料，通過稀疏索引我們先定位到學号為4的資料位置，然後再向下查找一次，找到學号為5的學生資料。稀疏索引其實是以時間換取空間，進而達到更好的平衡。
資料庫頁内部的查找使用了稀疏索引。資料頁的一個組成部分叫做 Page Directory。Page Directory 中按順序存儲了資料的主鍵和資料在頁中的相對位置。并不是每條資料都會被索引到 Page Directory。而是以一定步長跳躍的選擇資料儲存，也就是稀疏索引。通過 B+ 樹索引定位到具體的頁後，頁内部再通過 Page Directory 定位到資料的具體位置。
索引查找示例
我們通過下面這個例子，來總結下InnoDB通過索引查詢資料的過程。
我們有如下 student 表：
CREATE TABLE `student` (
`id` INT NOT NULL,
`name` VARCHAR(20) NULL,
`age` INT NULL,
PRIMARY KEY (`id`),
INDEX `idx_name` (`name`)
);
id作為主鍵，InnoDB會為id建立聚集索引。此外還為name建立了輔助索引。
查詢 name=xxx 的記錄。查找的過程是這樣的：
自适應哈希
哈希表是一種查詢速度很快的資料結構，一般情況下隻需要 1 次查找就可以定位到資料。而 B+ 樹的查找速度和自身的高度有關系，n 層的 B+ 樹至少需要 n 次查詢才能定位到資料。是以可以看到哈希表會比 B+ 樹檢索速度更快。
InnoDB 通過監控索引頁的使用，如果分析出建立哈希索引速度會更快，就會建立哈希索引。之是以叫做自适應哈希索引，是因為哈希索引的建立由資料庫自己來控制。
如果對于某張表的查詢一直以同樣的字段作為檢索條件，那麼可能會觸發自适應哈希索引的建立。例如一直使用where a=xxx查詢，但是如果中間穿插 where b=xxx或者 where a=xxxx and b=xxx，則不會建立自适應索引。此外自适應哈希的建立還需滿足如下要求：
1、以同樣的查詢條件查詢100次
2、通過同樣的方式查詢了某個頁N次。N=頁中資料總數/16
通過以上建立哈希索引的條件可以看出，資料庫在尋求效率最高的方式。哈希索引固然檢索更快，但是建立哈希索引同樣需要成本，不管是時間還是空間。隻有在大量使用某個索引列做查詢，并且頻繁定位到同一個頁的時候，資料庫才認為有必要建立哈希索引。
索引使用
Cardinality值
通過show index from table_name可以看到DB中索引的情況。列出的屬性中你可以找到Cardinality，對應的值是一個數字。代表的含義是表中此索引唯一值的數目估算值。這個值越接近行數，意味着索引重複值越少。此時索引的意義會更大。如果索引的重複值很多，比行數小很多，那麼此索引并不會為搜尋性能帶來很大提升。
搜尋優化器會更具此值來判斷是否走索引。但是這個值并不會實時更新，我們可以根據analyze table指令來重新整理Cardinality值。
InnoDB對Cardinality的更新發生在insert或者Upate操作。為了避免給資料庫帶來過大的負荷，并不是每次都會去計算。更新的政策為：
1、1/16的資料發生了變化
2、stat_modified_counter>2000000000。這個值是一個計數器，表示資料發生變化的次數
計算過程是随機對8個葉子節點進行采樣，計算不重複的記錄數量。求出8個葉子節點的平均值後，用平均值乘以葉子節點總數。
公式如下：
(P1+P2+P3+P4+P5+P6+P7+P8)*Total/8
由于8個葉子節點随機選取，是以同樣的資料，計算出的Cardinality可能不同。
聯合索引
聯合索引指的是對表中多個列進行索引。例如我們建立如下員工上班記錄表：
我們為employee_no和sign_in_date建立聯合索引。聯合索引同樣采用的是B+樹的資料結構，那麼這個聯合索引B+樹的葉子節點存儲的資料是按照什麼排序的呢？
這是一個輔助索引，是以葉子節點存儲的資料是索引值。葉子節點存儲資料的排序規則和你建立聯合索引時列的順序保持一緻。比如索引順序是 employee_no在先，sign_in_date在後，那麼先按employee_no排序，重複的話再按照sign_in_date排序。
這個順序會帶來如下兩個特性：
1、最左比對原則。多個字段的聯合索引，按照索引建立的字段順序，如果你的檢索條件中使用索引左邊連續的字段。那麼檢索字段都會會走索引的。如果不連續使用索引字段，那麼隻有左側連續的字段可以走索引。
舉個例子，一張表有a,b,c三個字段，聯合索引按照a,b,c順序建立。檢索條件和索引使用情況如下：
| 檢索使用字段 | 走索引情況 | |
|---|---|---|
| 1 | a,b,c | 3個字段都走索引 |
| 2 | a,b | 2個字段都走索引 |
| 3 | a,c | a走索引，c不走索引 |
| 4 | b,c | 2個字段都不走索引 |
情況1和2，因為你符合最左比對原則，是以使用的字段都會走索引。情況3，由于沒有連續使用索引字段，跳過了b，是以隻有a走索引，c不會走索引。第4種情況，由于最左側的a沒有作為檢索字段，是以b,c都不會走索引。
為什麼隻會最左比對呢，這是因為聯合索引葉子節點存儲資料的順序是按索引字段順序從左到右進行排序的。是以隻有索引字段是按照建立順序從左到右連續用來檢索，才符合B+樹構造的順序，進而才能通過B+樹快速查詢。
2、某些場景可以避免一次排序。例如第一個例子中，索引順序是employee_no、sign_in_date。如果我們查詢某個employee，最近三次的sign_in_date。由于sign_in_date在聯合索引中，已經排好序，是以DB不會再做排序操作。如果這張表隻對employee_no建立了索引，那麼同樣的查詢，DB還需要做一次排序操作。
覆寫索引
覆寫索引的含義是，通過輔助索引即可查詢到所需要的資料，不需要搜尋聚集索引中的記錄。輔助索引的資料包含索引鍵值以及主鍵。那麼隻要檢索出的字段在這個範圍内，就可以僅使用一次輔助索引即可完成。例如某張表主鍵為a，b，c。還有一個輔助索引，字段為d，e。那麼如下查詢隻會走輔助索引，不需要再去用聚集索引查詢具體資料：
select a, b, c, d, e from table where d = xxxx
字段a,b,c,d,e任意組合都會隻走輔助索引。
索引提示
Mysql 支援使用索引提示顯示告知索引優化器使用哪個索引。通常我們用到索引提示是下面兩個場景：
- 索引優化器錯誤的使用了索引，導緻查詢很慢。此時我們可以通過索引提示強制優化器選擇指定的索引
- 某張表的索引很多，索引優化器在選擇索引的時候會消耗比較長的時間。此時我們可以直接指定索引
我們可以通過以下方式使用索引提示：
通過user index可以告知索引選擇器可以使用某個索引，但是索引選擇器可能并不會最終選擇這個索引。如果想強制優化器使用你指定的文法，可以使用force關鍵字，如下：
上面的sql會指定優化器使用index a。
總結
本文從查字典的過程做類比講起，先講解了索引相關的基本算法，然後重點介紹了B+樹索引。最後講了一些索引使用的小技巧。資料庫的設計和字典十分相近，資料庫的資料也存儲在頁上，對索引的使用、查找資料的過程也是類似的。
資料庫通過B+樹加快索引查找速度，頁内查找則采用稀疏索引的方式。而查字典則是依賴人腦的智能，查找方式并不固定。可能是憑經驗，比如字母Z應該在拼音索引最後面。或者是周遊查找，比如拼音定位到某一頁後，頁内再定位到具體的字。我很期待未來資料庫可以引入人工智能來加速查詢。