一.索引的常見模型

索引的出現(xiàn)是為了提高查詢效率千康，但是實(shí)現(xiàn)索引的方式卻有很多種，所以這里也就引入了索引模型的概念∷笾桑可以用于提高讀寫效率的數(shù)據(jù)結(jié)構(gòu)很多，這里我先給你介紹三種常見絮吵、也比較簡單的數(shù)據(jù)結(jié)構(gòu)弧烤，它們分別是哈希表、有序數(shù)組和搜索樹蹬敲。

下面我主要從使用的角度暇昂，為你簡單分析一下這三種模型的區(qū)別。

哈希表是一種以鍵一值（key-value）存儲(chǔ)數(shù)據(jù)的結(jié)構(gòu)伴嗡，我們只要輸入待查找的鍵即key急波，就可以找到其對應(yīng)的值即Value。哈希的思路很簡單瘪校，把值放在數(shù)組里澄暮，用一個(gè)哈希函數(shù)把key換算成一個(gè)確定的位置名段，然后把value放在數(shù)組的這個(gè)位置。
不可避免地泣懊，多個(gè)key值經(jīng)過哈希函數(shù)的換算伸辟，會(huì)出現(xiàn)同一個(gè)值的情況。處理這種情況的一種方法是馍刮，拉出一個(gè)鏈表信夫。

圖中，User2和User4根據(jù)身份證號(hào)算出來的值都是N匈辱，但沒關(guān)系姊扔，后面還跟了一個(gè)鏈表。假設(shè)梅誓，這時(shí)候你要查1D_card_n2對應(yīng)的名字是什么恰梢，處理步驟就是：首先，將lD_card_n2通過哈希函數(shù)算出N梗掰；然后嵌言，按順序遍歷，找到User2及穗。

需要注意的是摧茴，圖中四個(gè)lD_card_n的值并不是遞增的，這樣做的好處是增加新的User時(shí)速度會(huì)很快埂陆，只需要往后追加苛白。但缺點(diǎn)是，因?yàn)椴皇怯行虻姆偈怨Ｋ饕鰠^(qū)間查詢的速度是很慢的购裙。

你可以設(shè)想下，如果你現(xiàn)在要找身份證號(hào)在【D_card_X鹃栽，lD_card_Y】這個(gè)區(qū)間的所有用戶躏率，就必須全部掃描一遍了。
所以民鼓，哈希表這種結(jié)構(gòu)適用于只有等值查詢的場景薇芝，比如Memcached及其他一些NoSQL引擎。
而有序數(shù)組在等值查詢和范圍查詢場景中的性能就都非常優(yōu)秀丰嘉。還是上面這個(gè)根據(jù)身份證號(hào)查名字的例子夯到，如果我們使用有序數(shù)組來實(shí)現(xiàn)的話，示意圖如下所示：

同時(shí)很顯然优床，這個(gè)索引結(jié)構(gòu)支持范圍查詢劝赔。你要查身份證號(hào)在【lD_card_X誓焦，ID_card_Y】區(qū)間的User，可以先用二分法找到ID_card_X（如果不存在1D_card_X着帽，就找到大于
lD_card_X的第一個(gè)User）杂伟，然后向右遍歷，直到查到第一個(gè)大于1D_card_Y的身份證號(hào)仍翰，退出循環(huán)赫粥。

如果僅僅看查詢效率，有序數(shù)組就是最好的數(shù)據(jù)結(jié)構(gòu)了予借。但是越平，在需要更新數(shù)據(jù)的時(shí)候就麻煩了，你往中間插入一個(gè)記錄就必須得挪動(dòng)后面所有的記錄灵迫，成本太高秦叛。
所以，有序數(shù)組索引只適用于靜態(tài)存儲(chǔ)引擎瀑粥，比如你要保存的是2017年某個(gè)城市的所有人口信息挣跋，這類不會(huì)再修改的數(shù)據(jù)。

二叉搜索樹的特點(diǎn)是：父節(jié)點(diǎn)左子樹所有結(jié)點(diǎn)的值小于父節(jié)點(diǎn)的值修噪，右子樹所有結(jié)點(diǎn)的值大于父節(jié)點(diǎn)的值查库。這樣如果你要查1D_card_n2的話，按照圖中的搜索順序就是按照UserA->UserC->UserF->User2這個(gè)路徑得到黄琼。這個(gè)時(shí)間復(fù)雜度是O（log（N））膨报。

當(dāng)然為了維持O（log（N））的查詢復(fù)雜度，你就需要保持這棵樹是平衡二叉樹适荣。為了做這個(gè)保證现柠，更新的時(shí)間復(fù)雜度也是O（log（N）。

樹可以有二叉弛矛，也可以有多叉够吩。多叉樹就是每個(gè)節(jié)點(diǎn)有多個(gè)兒子，兒子之間的大小保證從左到右遞增丈氓。二叉樹是搜索效率最高的周循，但是實(shí)際上大多數(shù)的數(shù)據(jù)庫存儲(chǔ)卻并不使用二叉樹强法。其原因是，索引不止存在內(nèi)存中湾笛，還要寫到磁盤上饮怯。

你可以想象一下一棵100萬節(jié)點(diǎn)的平衡二叉樹，樹高20嚎研。一次查詢可能需要訪問20個(gè)數(shù)據(jù)塊蓖墅。在機(jī)械硬盤時(shí)代，從磁盤隨機(jī)讀一個(gè)數(shù)據(jù)塊需要10ms左右的尋址時(shí)間临扮。也就是說论矾，對于一個(gè)100萬行的表，如果使用二叉樹來存儲(chǔ)杆勇，單獨(dú)訪問一個(gè)行可能需要20個(gè)10ms的時(shí)間贪壳，這個(gè)查詢可真夠慢的。

為了讓一個(gè)查詢盡量少地讀磁盤蚜退，就必須讓查詢過程訪問盡量少的數(shù)據(jù)塊闰靴。那么，我們就不應(yīng)該使用二叉樹钻注，而是要使用“N叉”樹蚂且。這里，“N叉”樹中的“N”取決于數(shù)據(jù)塊的大小队寇。

以InnoDB的一個(gè)整數(shù)字段索引為例膘掰，這個(gè)N差不多是1200(MySql默認(rèn)一個(gè)節(jié)點(diǎn)的長度為16K，一個(gè)整數(shù)（bigint）字段索引的長度為 8B,另外每個(gè)索引還跟著6B(固定)的指向其子樹的指針佳遣；所以16K/14B ≈ 1170)识埋。這棵樹高是4的時(shí)候，就可以存1200的3次方個(gè)值零渐，這已經(jīng)17億了窒舟。考慮到樹根的數(shù)據(jù)塊總是在內(nèi)存中的诵盼，一個(gè)10億行的表上一個(gè)整數(shù)字段的索引惠豺，查找一個(gè)值最多只需要訪問3次磁盤。其實(shí)风宁，樹的第二層也有很大概率在內(nèi)存中洁墙，那么訪問磁盤的平均次數(shù)就更少了。

N叉樹由于在讀寫上的性能優(yōu)點(diǎn)戒财，以及適配磁盤的訪問模式热监，已經(jīng)被廣泛應(yīng)用在數(shù)據(jù)庫引擎中了。

不管是哈希還是有序數(shù)組饮寞，或者N叉樹孝扛，它們都是不斷迭代列吼、不斷優(yōu)化的產(chǎn)物或者解決方案。數(shù)據(jù)庫技術(shù)發(fā)展到今天苦始，跳表寞钥、LSM樹等數(shù)據(jù)結(jié)構(gòu)也被用于引擎設(shè)計(jì)中，這里我就不再一展開了陌选。

你心里要有個(gè)概念理郑，數(shù)據(jù)庫底層存儲(chǔ)的核心就是基于這些數(shù)據(jù)模型的。每碰到一個(gè)新數(shù)據(jù)庫柠贤，我們需要先關(guān)注它的數(shù)據(jù)模型香浩，這樣才能從理論上分析出這個(gè)數(shù)據(jù)庫的適用場景类缤。

截止到這里臼勉，我用了半篇文章的篇幅和你介紹了不同的數(shù)據(jù)結(jié)構(gòu)，以及它們的適用場景餐弱，你可能會(huì)覺得有些枯燥宴霸。但是，我建議你還是要多花一些時(shí)間來理解這部分內(nèi)容膏蚓，畢竟這是數(shù)據(jù)庫處理數(shù)據(jù)的核心概念之一瓢谢，在分析問題的時(shí)候會(huì)經(jīng)常用到。當(dāng)你理解了索引的模型后驮瞧，就會(huì)發(fā)現(xiàn)在分析問題的時(shí)候會(huì)有一個(gè)更清晰的視角氓扛，體會(huì)到引擎設(shè)計(jì)的精妙之處。

現(xiàn)在论笔，我們一起進(jìn)入相對偏實(shí)戰(zhàn)的內(nèi)容吧采郎。

在MySQL中，索引是在存儲(chǔ)引擎層實(shí)現(xiàn)的狂魔，所以并沒有統(tǒng)一的索引標(biāo)準(zhǔn)蒜埋，即不同存儲(chǔ)引擎的索引的工作方式并不一樣。而即使多個(gè)存儲(chǔ)引擎支持同一種類型的索引最楷，其底層的實(shí)現(xiàn)也可能不同整份。由于InnoDB存儲(chǔ)引擎在MySQL數(shù)據(jù)庫中使用最為廣泛，所以下面我就以InnoDB為例籽孙，和你分析一下其中的索引模型烈评。

二 .lnnoDB的索引模型

在InnoDB中，表都是根據(jù)主鍵順序以索引的形式存放的犯建，這種存儲(chǔ)方式的表稱為索引組織表讲冠。又因?yàn)榍懊嫖覀兲岬降模琁nnoDB使用了B+樹索引模型，所以數(shù)據(jù)都是存儲(chǔ)在B+樹中的涮母。

每一個(gè)索引在InnoDB里面對應(yīng)一棵B+樹。

假設(shè)全蝶，我們有一個(gè)主鍵列為ID的表德迹，表中有字段k芽卿，并且在k上有索引。
這個(gè)表的建表語句是：

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里般婆，非主鍵索引也被稱為二級索引(secondaryindex)到腥。

根據(jù)上面的索引結(jié)構(gòu)說明，我們來討論一個(gè)問題：基于主鍵索引和普通索引的查詢有什么區(qū)別蔚袍？

• 如果語句是select * fromTwhere ID=500乡范，即主鍵查詢方式，則只需要搜索ID這棵B+樹啤咽；
• 如果語句是select * fromTwhere k=5晋辆，即普通索引查詢方式，則需要先搜索k索引樹闰蚕，得到ID的值為500栈拖，再到ID索引樹搜索一次。這個(gè)過程稱為回表没陡。

也就是說涩哟，基于非主鍵索引的查詢需要多掃描一棵索引樹(回表)。因此盼玄，我們在應(yīng)用中應(yīng)該盡量使用主鍵查詢贴彼。

三.索引維護(hù)

B+樹為了維護(hù)索引有序性，在插入新值的時(shí)候需要做必要的維護(hù)埃儿。（所以推薦使用自增主鍵器仗，就可以保證新的ID一定是在葉子節(jié)點(diǎn)最右邊，不會(huì)影響前面的數(shù)據(jù)。）以上面這個(gè)圖為例精钮，如果插入新的行ID值為700威鹿，則只需要在R5的記錄后面插入一個(gè)新記錄。如果新插入的ID值為400轨香，就相對麻煩了忽你，需要邏輯上挪動(dòng)后面的數(shù)據(jù)，空出位置臂容。

而更糟的情況是科雳，如果R5所在的數(shù)據(jù)頁已經(jīng)滿了，根據(jù)B+樹的算法脓杉，這時(shí)候需要申請一個(gè)新的數(shù)據(jù)頁糟秘，然后挪動(dòng)部分?jǐn)?shù)據(jù)過去。這個(gè)過程稱為頁分裂球散。在這種情況下尿赚，性能自然會(huì)受影響。

除了性能外沛婴，頁分裂操作還影響數(shù)據(jù)頁的利用率吼畏。原本放在一個(gè)頁的數(shù)據(jù)督赤，現(xiàn)在分到兩個(gè)頁中嘁灯，整體空間利用率降低大約50%。

當(dāng)然有分裂就有合并躲舌。當(dāng)相鄰兩個(gè)頁由于刪除了數(shù)據(jù)丑婿，利用率很低之后，會(huì)將數(shù)據(jù)頁做合并没卸。合并的過程羹奉，可以認(rèn)為是分裂過程的逆過程。

基于上面的索引維護(hù)過程說明约计，我們來討論一個(gè)案例：

你可能在一些建表規(guī)范里面見到過類似的描述诀拭，要求建表語句里一定要有自增主鍵。當(dāng)然事無絕對煤蚌，我們來分析一下哪些場景下應(yīng)該使用自增主鍵耕挨，而哪些場景下不應(yīng)該。

自增主鍵是指自增列上定義的主鍵尉桩，在建表語句中一般是這么定義的：NOTNULLPRIMARY KEY AUTO_INCREMENT.

插入新記錄的時(shí)候可以不指定ID的值筒占，系統(tǒng)會(huì)獲取當(dāng)前ID最大值加1作為下一條記錄的ID值。

也就是說蜘犁，自增主鍵的插入數(shù)據(jù)模式翰苫，正符合了我們前面提到的遞增插入的場景。每次插入一條新記錄，都是追加操作奏窑，都不涉及到挪動(dòng)其他記錄导披，也不會(huì)觸發(fā)葉子節(jié)點(diǎn)的分裂。

而有業(yè)務(wù)邏輯的字段做主鍵埃唯，則往往不容易保證有序插入盛卡，這樣寫數(shù)據(jù)成本相對較高。

除了考慮性能外筑凫，我們還可以從存儲(chǔ)空間的角度來看滑沧。假設(shè)你的表中確實(shí)有一個(gè)唯一字段，比如字符串類型的身份證號(hào)巍实，那應(yīng)該用身份證號(hào)做主鍵滓技，還是用自增字段做主鍵呢？

由于每個(gè)非主鍵索引的葉子節(jié)點(diǎn)上都是主鍵的值棚潦。如果用身份證號(hào)做主鍵令漂，那么每個(gè)二級索引的葉子節(jié)點(diǎn)占用約20個(gè)字節(jié)，而如果用整型做主鍵丸边，則只要4個(gè)字節(jié)叠必，如果是長整型（bigint）則是8個(gè)字節(jié)。

顯然妹窖，主鍵長度越小纬朝，普通索引的葉子節(jié)點(diǎn)就越小，普通索引占用的空間也就越小骄呼。
所以共苛，從性能和存儲(chǔ)空間方面考量，自增主鍵往往是更合理的選擇蜓萄。

有沒有什么場景適合用業(yè)務(wù)字段直接做主鍵的呢隅茎？還是有的。比如嫉沽，有些業(yè)務(wù)的場景需求是這樣的：

• 1.只有一個(gè)索引辟犀；
• 2.該索引必須是唯一索引。

你一定看出來了绸硕，這就是典型的KV場景堂竟。
由于沒有其他索引，所以也就不用考慮其他索引的葉子節(jié)點(diǎn)大小的問題臣咖。
這時(shí)候我們就要優(yōu)先考慮上一段提到的“盡量使用主鍵查詢”原則跃捣，直接將這個(gè)索引設(shè)置為主鍵，可以避免每次查詢需要搜索兩棵樹夺蛇。