提到數(shù)據(jù)庫索引吼旧，我想你并不陌生郎嫁，在日常工作中會經(jīng)常接觸到捡硅。比如某一個 SQL 查詢比較慢哮内，分析完原因之后，你可能就會說“給某個字段加個索引吧”之類的解決方案壮韭。
一句話簡單來說北发，索引的出現(xiàn)其實就是為了提高數(shù)據(jù)查詢的效率，就像書的目錄一樣泰涂。一本 500 頁的字典鲫竞，如果你想快速找到其中的某一個字，在不借助目錄的情況下逼蒙，那我估計你會找得很辛苦从绘。同樣，對于數(shù)據(jù)庫的表而言，索引其實就是它的“目錄”僵井。
索引的常見模型
索引的出現(xiàn)是為了提高查詢效率陕截，但是實現(xiàn)索引的方式卻有很多種，所以這里也就引入了索引模型的概念批什∨┣可以用于提高讀寫效率的數(shù)據(jù)結(jié)構(gòu)很多，這里我先給你介紹三種常見驻债、也比較簡單的數(shù)據(jù)結(jié)構(gòu)乳规，它們分別是哈希表、有序數(shù)組和搜索樹合呐。
下面我主要從使用的角度暮的，為你簡單分析一下這三種模型的區(qū)別。
哈希表是一種以鍵 - 值（key-value）存儲數(shù)據(jù)的結(jié)構(gòu)淌实，我們只要輸入待查找的鍵即 key冻辩，就可以找到其對應(yīng)的值即 Value。哈希的思路很簡單拆祈，把值放在數(shù)組里恨闪，用一個哈希函數(shù)把 key 換算成一個確定的位置，然后把 value 放在數(shù)組的這個位置放坏。
不可避免地咙咽，多個 key 值經(jīng)過哈希函數(shù)的換算，會出現(xiàn)同一個值的情況轻姿。處理這種情況的一種方法是犁珠，拉出一個鏈表。
假設(shè)互亮，你現(xiàn)在維護(hù)著一個身份證信息和姓名的表，需要根據(jù)身份證號查找對應(yīng)的名字余素，這時對應(yīng)的哈希索引的示意圖如下所示：
圖中豹休，User2 和 User4 根據(jù)身份證號算出來的值都是 N，但沒關(guān)系桨吊，后面還跟了一個鏈表威根。假設(shè)，這時候你要查 ID_card_n2 對應(yīng)的名字是什么视乐，處理步驟就是：首先洛搀，將 ID_card_n2 通過哈希函數(shù)算出 N；然后佑淀，按順序遍歷留美，找到 User2。
需要注意的是，圖中四個 ID_card_n 的值并不是遞增的谎砾，這樣做的好處是增加新的 User 時速度會很快逢倍，只需要往后追加。但缺點(diǎn)是景图，因為不是有序的较雕，所以哈希索引做區(qū)間查詢的速度是很慢的。
你可以設(shè)想下挚币，如果你現(xiàn)在要找身份證號在[ID_card_X, ID_card_Y]這個區(qū)間的所有用戶亮蒋，就必須全部掃描一遍了。
所以妆毕，哈希表這種結(jié)構(gòu)適用于只有等值查詢的場景宛蚓，比如 Memcached 及其他一些 NoSQL 引擎。
而有序數(shù)組在等值查詢和范圍查詢場景中的性能就都非常優(yōu)秀设塔。還是上面這個根據(jù)身份證號查名字的例子凄吏，如果我們使用有序數(shù)組來實現(xiàn)的話，示意圖如下所示：
這里我們假設(shè)身份證號沒有重復(fù)闰蛔，這個數(shù)組就是按照身份證號遞增的順序保存的痕钢。這時候如果你要查 ID_card_n2 對應(yīng)的名字，用二分法就可以快速得到序六，這個時間復(fù)雜度是 O(log(N))任连。
同時很顯然，這個索引結(jié)構(gòu)支持范圍查詢例诀。你要查身份證號在[ID_card_X, ID_card_Y]區(qū)間的 User随抠，可以先用二分法找到 ID_card_X（如果不存在 ID_card_X，就找到大于 ID_card_X 的第一個 User）繁涂，然后向右遍歷拱她，直到查到第一個大于 ID_card_Y 的身份證號，退出循環(huán)扔罪。
如果僅僅看查詢效率秉沼，有序數(shù)組就是最好的數(shù)據(jù)結(jié)構(gòu)了。但是矿酵，在需要更新數(shù)據(jù)的時候就麻煩了唬复，你往中間插入一個記錄就必須得挪動后面所有的記錄，成本太高全肮。
所以敞咧，有序數(shù)組索引只適用于靜態(tài)存儲引擎，比如你要保存的是 2017 年某個城市的所有人口信息辜腺，這類不會再修改的數(shù)據(jù)休建。
二叉搜索樹也是經(jīng)典數(shù)據(jù)結(jié)構(gòu)了乍恐。還是上面根據(jù)身份證號查名字的例子，如果我們用二叉搜索樹來實現(xiàn)的話丰包，示意圖如下所示：
二叉搜索樹的特點(diǎn)是：父節(jié)點(diǎn)左子樹所有結(jié)點(diǎn)的值小于父節(jié)點(diǎn)的值禁熏，右子樹所有結(jié)點(diǎn)的值大于父節(jié)點(diǎn)的值。這樣如果你要查 ID_card_n2 的話邑彪，按照圖中的搜索順序就是按照 UserA -> UserC -> UserF -> User2 這個路徑得到瞧毙。這個時間復(fù)雜度是 O(log(N))。
當(dāng)然為了維持 O(log(N)) 的查詢復(fù)雜度寄症，你就需要保持這棵樹是平衡二叉樹宙彪。為了做這個保證，更新的時間復(fù)雜度也是 O(log(N))有巧。
樹可以有二叉释漆，也可以有多叉。多叉樹就是每個節(jié)點(diǎn)有多個兒子篮迎，兒子之間的大小保證從左到右遞增男图。二叉樹是搜索效率最高的，但是實際上大多數(shù)的數(shù)據(jù)庫存儲卻并不使用二叉樹甜橱。其原因是逊笆，索引不止存在內(nèi)存中，還要寫到磁盤上岂傲。
你可以想象一下一棵 100 萬節(jié)點(diǎn)的平衡二叉樹难裆，樹高 20。一次查詢可能需要訪問 20 個數(shù)據(jù)塊镊掖。在機(jī)械硬盤時代乃戈，從磁盤隨機(jī)讀一個數(shù)據(jù)塊需要 10 ms 左右的尋址時間。也就是說亩进，對于一個 100 萬行的表症虑，如果使用二叉樹來存儲，單獨(dú)訪問一個行可能需要 20 個 10 ms 的時間镐侯，這個查詢可真夠慢的侦讨。
以 InnoDB 的一個整數(shù)字段索引為例，這個 N 差不多是 1200苟翻。這棵樹高是 4 的時候，就可以存 1200 的 3 次方個值骗污，這已經(jīng) 17 億了崇猫。考慮到樹根的數(shù)據(jù)塊總是在內(nèi)存中的需忿，一個 10 億行的表上一個整數(shù)字段的索引诅炉，查找一個值最多只需要訪問 3 次磁盤蜡歹。其實，樹的第二層也有很大概率在內(nèi)存中涕烧，那么訪問磁盤的平均次數(shù)就更少了月而。
N 叉樹由于在讀寫上的性能優(yōu)點(diǎn)，以及適配磁盤的訪問模式议纯，已經(jīng)被廣泛應(yīng)用在數(shù)據(jù)庫引擎中了父款。
你心里要有個概念，數(shù)據(jù)庫底層存儲的核心就是基于這些數(shù)據(jù)模型的瞻凤。每碰到一個新數(shù)據(jù)庫憨攒，我們需要先關(guān)注它的數(shù)據(jù)模型，這樣才能從理論上分析出這個數(shù)據(jù)庫的適用場景阀参。
在 MySQL 中肝集，索引是在存儲引擎層實現(xiàn)的，所以并沒有統(tǒng)一的索引標(biāo)準(zhǔn)蛛壳，即不同存儲引擎的索引的工作方式并不一樣杏瞻。而即使多個存儲引擎支持同一種類型的索引，其底層的實現(xiàn)也可能不同衙荐。由于 InnoDB 存儲引擎在 MySQL 數(shù)據(jù)庫中使用最為廣泛捞挥，所以下面我就以 InnoDB 為例，和你分析一下其中的索引模型赫模。
InnoDB 的索引模型
在 InnoDB 中树肃，表都是根據(jù)主鍵順序以索引的形式存放的，這種存儲方式的表稱為索引組織表瀑罗。又因為前面我們提到的胸嘴，InnoDB 使用了 B+ 樹索引模型，所以數(shù)據(jù)都是存儲在 B+ 樹中的斩祭。
每一個索引在 InnoDB 里面對應(yīng)一棵 B+ 樹劣像。
假設(shè)，我們有一個主鍵列為 ID 的表摧玫，表中有字段 k耳奕，并且在 k 上有索引。
這個表的建表語句是：
mysql> create table T(
id int primary key,
k int not null,
name varchar(16),
index (k))engine=InnoDB;
從圖中不難看出，根據(jù)葉子節(jié)點(diǎn)的內(nèi)容降狠，索引類型分為主鍵索引和非主鍵索引对竣。
主鍵索引的葉子節(jié)點(diǎn)存的是整行數(shù)據(jù)庇楞。在 InnoDB 里，主鍵索引也被稱為聚簇索引（clustered index）否纬。
非主鍵索引的葉子節(jié)點(diǎn)內(nèi)容是主鍵的值吕晌。在 InnoDB 里，非主鍵索引也被稱為二級索引（secondary index）临燃。
根據(jù)上面的索引結(jié)構(gòu)說明睛驳，我們來討論一個問題：基于主鍵索引和普通索引的查詢有什么區(qū)別？
- 如果語句是 select * from T where ID=500谬俄，即主鍵查詢方式柏靶，則只需要搜索 ID 這棵 B+ 樹；
- 如果語句是 select * from T where k=5溃论，即普通索引查詢方式屎蜓，則需要先搜索 k 索引樹，得到 ID 的值為 500钥勋，再到 ID 索引樹搜索一次炬转。這個過程稱為回表。
也就是說算灸，基于非主鍵索引的查詢需要多掃描一棵索引樹扼劈。因此，我們在應(yīng)用中應(yīng)該盡量使用主鍵查詢菲驴。
索引維護(hù)
B+ 樹為了維護(hù)索引有序性荐吵，在插入新值的時候需要做必要的維護(hù)。以上面這個圖為例赊瞬，如果插入新的行 ID 值為 700先煎，則只需要在 R5 的記錄后面插入一個新記錄。如果新插入的 ID 值為 400巧涧，就相對麻煩了薯蝎，需要邏輯上挪動后面的數(shù)據(jù)，空出位置谤绳。
而更糟的情況是占锯，如果 R5 所在的數(shù)據(jù)頁已經(jīng)滿了，根據(jù) B+ 樹的算法缩筛，這時候需要申請一個新的數(shù)據(jù)頁消略，然后挪動部分?jǐn)?shù)據(jù)過去。這個過程稱為頁分裂瞎抛。在這種情況下疑俭，性能自然會受影響。
除了性能外婿失，頁分裂操作還影響數(shù)據(jù)頁的利用率钞艇。原本放在一個頁的數(shù)據(jù)，現(xiàn)在分到兩個頁中豪硅，整體空間利用率降低大約 50%哩照。
當(dāng)然有分裂就有合并。當(dāng)相鄰兩個頁由于刪除了數(shù)據(jù)懒浮，利用率很低之后飘弧，會將數(shù)據(jù)頁做合并。合并的過程砚著，可以認(rèn)為是分裂過程的逆過程次伶。
基于上面的索引維護(hù)過程說明，我們來討論一個案例：
你可能在一些建表規(guī)范里面見到過類似的描述稽穆，要求建表語句里一定要有自增主鍵冠王。當(dāng)然事無絕對，我們來分析一下哪些場景下應(yīng)該使用自增主鍵舌镶，而哪些場景下不應(yīng)該柱彻。
自增主鍵是指自增列上定義的主鍵，在建表語句中一般是這么定義的： NOT NULL PRIMARY KEY AUTO_INCREMENT餐胀。
插入新記錄的時候可以不指定 ID 的值哟楷，系統(tǒng)會獲取當(dāng)前 ID 最大值加 1 作為下一條記錄的 ID 值。
也就是說否灾，自增主鍵的插入數(shù)據(jù)模式卖擅，正符合了我們前面提到的遞增插入的場景。每次插入一條新記錄墨技，都是追加操作惩阶，都不涉及到挪動其他記錄，也不會觸發(fā)葉子節(jié)點(diǎn)的分裂健提。
而有業(yè)務(wù)邏輯的字段做主鍵琳猫，則往往不容易保證有序插入，這樣寫數(shù)據(jù)成本相對較高私痹。
除了考慮性能外脐嫂，我們還可以從存儲空間的角度來看。假設(shè)你的表中確實有一個唯一字段紊遵，比如字符串類型的身份證號账千，那應(yīng)該用身份證號做主鍵，還是用自增字段做主鍵呢暗膜？
由于每個非主鍵索引的葉子節(jié)點(diǎn)上都是主鍵的值匀奏。如果用身份證號做主鍵，那么每個二級索引的葉子節(jié)點(diǎn)占用約 20 個字節(jié)学搜，而如果用整型做主鍵娃善，則只要 4 個字節(jié)论衍，如果是長整型（bigint）則是 8 個字節(jié)。
顯然聚磺，主鍵長度越小坯台，普通索引的葉子節(jié)點(diǎn)就越小，普通索引占用的空間也就越小瘫寝。
所以蜒蕾，從性能和存儲空間方面考量，自增主鍵往往是更合理的選擇焕阿。
有沒有什么場景適合用業(yè)務(wù)字段直接做主鍵的呢咪啡？還是有的。比如暮屡，有些業(yè)務(wù)的場景需求是這樣的：
- 只有一個索引撤摸；
- 該索引必須是唯一索引。
你一定看出來了栽惶，這就是典型的 KV 場景愁溜。
由于沒有其他索引，所以也就不用考慮其他索引的葉子節(jié)點(diǎn)大小的問題外厂。
這時候我們就要優(yōu)先考慮上一段提到的“盡量使用主鍵查詢”原則呵晨，直接將這個索引設(shè)置為主鍵喂江，可以避免每次查詢需要搜索兩棵樹焙蹭。
小結(jié)
今天窃躲，我跟你分析了數(shù)據(jù)庫引擎可用的數(shù)據(jù)結(jié)構(gòu)，介紹了 InnoDB 采用的 B+ 樹結(jié)構(gòu)掖棉，以及為什么 InnoDB 要這么選擇墓律。B+ 樹能夠很好地配合磁盤的讀寫特性，減少單次查詢的磁盤訪問次數(shù)幔亥。
由于 InnoDB 是索引組織表耻讽，一般情況下我會建議你創(chuàng)建一個自增主鍵，這樣非主鍵索引占用的空間最小帕棉。但事無絕對针肥，我也跟你討論了使用業(yè)務(wù)邏輯字段做主鍵的應(yīng)用場景。
希望你對MySQL索引有一個基本的認(rèn)識香伴。
