索引是在存儲引擎層實現(xiàn)的，下面主要說說 InnoDB 引擎的索引。
索引模型
在 InnoDB 中，表都是根據(jù)主鍵順序以索引的形式存放的，這種存儲方式的表稱為索引組織表，每一個索引對應(yīng)一個 B+ 樹。
為了讓一個查詢盡量少的讀磁盤，就得讓查詢過程訪問盡量少的數(shù)據(jù)塊，所以索引采用了 n 叉樹，n 取決于數(shù)據(jù)塊的大小。
以 InnoDB 一個整型字段索引為例，n 差不多是 1200，當樹高是 4 的時候，就可以存 1200 的 3 次方個值，已經(jīng)是 17 億了。考慮到樹根的數(shù)據(jù)塊總是在內(nèi)存中，一個 10 億行的表上一個整數(shù)字段的索引，查找一個值最多只需要訪問 3 次磁盤，樹的第二層也有很大概率在內(nèi)存中，那訪問磁盤的平均次數(shù)就更少了。
所以 B+ 樹能夠很好的配合磁盤的讀寫特性，減少單次查詢的磁盤訪問次數(shù)。
亂入：B+ 樹和 B 樹的區(qū)別
- B+ 樹中的節(jié)點不存儲數(shù)據(jù)，只是索引，而B樹中的節(jié)點存儲數(shù)據(jù)
- B 樹中的葉子結(jié)點不需要鏈表來串聯(lián)
假設(shè)有個表 T，主鍵為 id，字段 k 上有索引，建表語句如下：
create table T(
id int(11) not null primary key,
k int(11) not null,
name varchar(16),
index (k)
) engine=InnoDB;
表中 R1～R5 的 (id,k) 值分別為 (100,1)、(200,2)、(300,3)、(400,4)、(500,5)，兩棵樹的圖如下：
如圖，根據(jù)葉子節(jié)點的內(nèi)容，索引類型分為主鍵索引和非主鍵索引。
主鍵索引也叫聚簇索引，它的葉子節(jié)點的內(nèi)容是整行數(shù)據(jù)。
非主鍵索引也叫二級索引，它的葉子節(jié)點的內(nèi)容是主鍵的值。
索引上的一個葉子節(jié)點就是一頁，一頁里存有多行數(shù)據(jù)。
基于主鍵索引和普通索引的查詢有什么區(qū)別？
- 如果語句是 select * from T where id = 1，即主鍵查詢方式，只需要搜索 id 這棵樹。
- 如果語句是 select * from T where k = 1，即普通索引查詢方式，得先搜索 k 樹，得到 id 值為 500，再去 id 樹搜索一次，這個過程稱為回表。
所以基于非主鍵索引的查詢需要多掃描一棵索引樹（當然覆蓋索引除外）。
索引維護
B+樹為了維護索引的有序性，在插入新值的時候需要做必要的維護。
已上圖 id 索引樹為例，如果插入新行的 id 值為 700，只需在 R5 后面插入新紀錄。如果插入新行 id 值為 400，需要邏輯上挪動后面的數(shù)據(jù)，空出位置。
更糟糕的是，如果如果 R5 所在的數(shù)據(jù)頁已滿，根據(jù) B+ 樹的算法，需要申請一個新的數(shù)據(jù)頁，然后挪動部分數(shù)據(jù)過去，這個過程叫頁分裂，這種情況下性能當然會受到影響。
除了性能外，頁分裂操作還影響了數(shù)據(jù)頁的利用率，原本在一頁的數(shù)據(jù)，現(xiàn)在分到兩個頁中，整體空間利用率大概降低 50%。
當相鄰的兩個頁由于刪除數(shù)據(jù)，利用率很低之后，會將數(shù)據(jù)頁合并，這個過程叫頁合并。頁分裂和頁合并都會影響性能。
自增主鍵
你可能在建表規(guī)范里見過這樣的描述：要求建表語句一定要有自增主鍵。那哪些情況應(yīng)該使用自增主鍵，哪些情況可以不用呢？
自增主鍵是指自增列上定義的主鍵，插入新紀錄時，可以不指定 id 的值，系統(tǒng)會獲取當前最大 id 值加一作為下一條記錄的 id 值。
所以自增主鍵的插入模式，就是遞增插入，每次插入新紀錄，都是追加操作，不涉及挪動其他記錄，也不會出發(fā)頁分裂。如果用業(yè)務(wù)邏輯的字段做主鍵，往往不容易保證有序插入，這樣寫數(shù)據(jù)的成本相對較高。
除了性能外，還可以從存儲空間的角度考慮。主鍵長度越小，普通索引的葉子結(jié)點就越小，普通索引占用的空間就越小。所以從性能和存儲空間方面考慮，自增主鍵往往是更合理的選擇。
那有沒有適合直接用業(yè)務(wù)字段做主鍵的場景呢？下面的場景就是：
- 只有一個索引
- 該索引必須是唯一索引
由于沒有其他索引，所以不必考慮普通索引葉子結(jié)點大小問題，直接作為主鍵，也避免每次查詢都要搜索兩棵樹。
覆蓋索引
普通索引已經(jīng)覆蓋了所有查詢字段和查詢條件字段。這樣可以避免回表，減少樹搜索次數(shù)。
最左前綴原則
聯(lián)合索引的最左 n 個字段、或字符串索引最左 m 個字符，只要滿足最左前綴，就可以利用索引加速檢索。
建立聯(lián)合索引的時候，如何安排索引內(nèi)的字段順序？
第一原則是，如果通過調(diào)整順序，可以少維護一個索引，那這個順序就是需要優(yōu)先考慮的。
當索引不能減少時，就要從存儲空間角度考慮。
索引下推
如果用到了聯(lián)合索引，在滿足最左前綴原則的時候，剩下右邊那些用不到的索引字段怎么辦呢？
以下面的查詢語句為例：
select * from users where name like '張%' and age = 10;
假設(shè)有個 (name, age) 的聯(lián)合索引，在搜索索引樹的時候，只能用 ‘張’ 找到第一個滿足條件的記錄，然后再判斷其他條件是否滿足。
在 MySQL 5.6 版本之前，并不會看 age 的值，只能一條一條的回表，去主鍵索引樹找到對應(yīng)的數(shù)據(jù)行，判斷 age 是不是 10。5.6 版本引入了索引下推優(yōu)化（index condition pushdown），可以在索引遍歷過程中，對索引中包含的字段先做判斷，直接過濾掉不滿足條件的記錄，減少回表次數(shù)。
覆蓋索引、最左前綴、索引下推，從這些概念中可以看出，在滿足語句要需求的情況下，盡量少的訪問資源，是數(shù)據(jù)庫設(shè)計的重要原則之一。
