[[434590]]

這段時(shí)間一直在面試，問(wèn)了很多候選人數(shù)據(jù)庫(kù)索引相關(guān)的知識(shí)，能答好的不是很多，令人惋惜啊，我也想留你啊……

面試官：了解過(guò)數(shù)據(jù)庫(kù)索引嗎?

候選人：聽(tīng)過(guò)一些，底層數(shù)據(jù)結(jié)構(gòu)好像是二叉樹(shù)，不對(duì)，好像是 B 樹(shù)，哦，我想起來(lái)了，好像是 B+樹(shù)……(像極了當(dāng)年面試的我)

面試官：聽(tīng)過(guò)哈希索引嗎?

候選人：我知道哈希表，哈希索引沒(méi)聽(tīng)過(guò)

面試官：今天面試先到這里了，回去等消息吧……

溫馨提示：本文是數(shù)據(jù)庫(kù)索引的簡(jiǎn)單入門篇，后面會(huì)通過(guò)圖解的方式逐步帶大家深入索引的原理，敬請(qǐng)期待!

先引入一個(gè)簡(jiǎn)單的示例，通過(guò)示例操作解釋一下為什么需要數(shù)據(jù)庫(kù)索引。

假設(shè)我們有一個(gè)名為 t_employee 的數(shù)據(jù)庫(kù)表，這個(gè)數(shù)據(jù)庫(kù)表有三列：name，age，address，數(shù)據(jù)量有上萬(wàn)行。

如果我們想要查找所有名為「leixiaoshuai」員工的詳細(xì)信息，只需要寫一個(gè)簡(jiǎn)單的 SQL 語(yǔ)句就可以搞定，相信大家都會(huì)寫。

SELECT * FROM t_employee 
 
WHERE name = 'leixiaoshuai' 

如果沒(méi)有索引，會(huì)發(fā)生什么?

一旦我們運(yùn)行了這條 SQL 查詢語(yǔ)句，在數(shù)據(jù)庫(kù)內(nèi)部是如何工作的呢?數(shù)據(jù)庫(kù)會(huì)搜索 t_employee 表中的每一行，從而確定員工的名字(name)是否為 ‘leixiaoshuai’。由于我們想要得到每一個(gè)名字為 leixiaoshuai 的雇員信息，在查詢到第一個(gè)符合條件的行記錄后，不能停止查詢，因?yàn)榭赡苓€有其他符合條件的行。所以，必須一行一行的查找直到最后一行，這就意味數(shù)據(jù)庫(kù)不得不檢查上萬(wàn)行數(shù)據(jù)才能找到所有名字為 leixiaoshuai 的員工。這就是所謂的全表掃描。

數(shù)據(jù)庫(kù)索引如何幫助提高性能?

你可能會(huì)想：「這么簡(jiǎn)單的查詢語(yǔ)句居然還需要全表掃描，數(shù)據(jù)庫(kù)也太笨了吧?!」

這就類似于用人眼從頭到尾逐字逐句讀一本書，效率太低了!

那應(yīng)該怎么辦?聰明的你肯定想到解決方案了：「加個(gè)索引啊」。

這就是索引派上用場(chǎng)的時(shí)候了，使用索引的目的就是**通過(guò)減少表中需要檢查的記錄/行的數(shù)量來(lái)加速搜索查詢。**說(shuō)的再簡(jiǎn)單點(diǎn)：「索引就是用來(lái)加速查詢的」。

什么是索引?

那么問(wèn)題來(lái)了，什么是索引呢?索引本質(zhì)是一種數(shù)據(jù)結(jié)構(gòu)(最常見(jiàn)的是 B+樹(shù))，是在表的列上創(chuàng)建的。

索引的數(shù)據(jù)結(jié)構(gòu)是什么樣的?

常見(jiàn)MySQL索引一般分為：Hash索引和**B+**樹(shù)索引，InnoDB引擎中默認(rèn)的是B+樹(shù)。

B+樹(shù) 是最常用于索引的數(shù)據(jù)結(jié)構(gòu)，時(shí)間復(fù)雜度低：查找、刪除、插入操作都可以可以在 logn 時(shí)間內(nèi)完成。另外一個(gè)重要原因存儲(chǔ)在 B+樹(shù) 中的數(shù)據(jù)是有序的。

在B+樹(shù)常規(guī)檢索場(chǎng)景下，從根節(jié)點(diǎn)到葉子節(jié)點(diǎn)的搜索效率基本相當(dāng)，不會(huì)出現(xiàn)大幅波動(dòng)，而且基于索引的順序掃描時(shí)，也可以利用雙向指針快速左右移動(dòng)，效率非常高。

哈希索引就是采用一定的哈希算法，把鍵值換算成新的哈希值，檢索時(shí)不需要類似B+樹(shù)那樣從根節(jié)點(diǎn)到葉子節(jié)點(diǎn)逐級(jí)查找，只需一次哈希算法即可立刻定位到相應(yīng)的位置，速度非?？臁?/p>

哈希表索引是如何工作的?

如果你在創(chuàng)建索引時(shí)指定數(shù)據(jù)結(jié)構(gòu)為「哈希表」，那這些索引也可稱為「哈希索引」。

哈希索引的優(yōu)點(diǎn)非常明顯，在一定場(chǎng)景下，檢索指定值時(shí)哈希表的效率極高。比如上面我們討論的一個(gè)查詢語(yǔ)句：SELECT * FROM t_employee WHERE name = ‘leixiaoshuai’，如果在 name 列上加一個(gè)哈希索引，檢索速度有可能會(huì)成倍提升。

哈系索引的工作方式是將列的值作為索引的鍵值(key)，鍵值相對(duì)應(yīng)實(shí)際的值(value)是指向該表中相應(yīng)行的指針。因?yàn)楣１砘旧峡梢钥醋魇顷P(guān)聯(lián)數(shù)組，一個(gè)典型的數(shù)據(jù)項(xiàng)就像 「leixiaoshuai => 0x996996」，而 0x996996 是對(duì)內(nèi)存中表中包含 leixiaoshuai 這一行的引用。在哈系索引的中查詢一個(gè)像 leixiaoshuai 這樣的值，并得到對(duì)應(yīng)行的在內(nèi)存中的引用，明顯要比掃描全表獲得值為 leixiaoshuai 的行的方式快很多。

哈希索引的缺點(diǎn)

上面說(shuō)了哈希索引的優(yōu)點(diǎn)，那哈希索引的缺點(diǎn)也是繞不過(guò)去的。

哈希表是無(wú)順的數(shù)據(jù)結(jié)構(gòu)，對(duì)于很多類型的查詢語(yǔ)句哈希索引都無(wú)能為力。舉例來(lái)說(shuō)，假如你想要找出所有小于40歲的員工。你怎么使用使用哈希索引進(jìn)行查詢?這不可行，因?yàn)楣１碇贿m合查詢鍵值對(duì)，也就是說(shuō)查詢相等的查詢(例：like “WHERE name = ‘leixiaoshuai’)。哈希表的鍵值映射也暗示其鍵的存儲(chǔ)是無(wú)序的。這就是為什么哈希索引通常不是數(shù)據(jù)庫(kù)索引的默認(rèn)數(shù)據(jù)結(jié)構(gòu)，因?yàn)樵谧鳛樗饕臄?shù)據(jù)結(jié)構(gòu)時(shí)，其不像B+Tree那么靈活。

總結(jié)一下缺點(diǎn)：

• (1)不支持范圍查詢
• (2)不支持索引完成排序
• (3)不支持聯(lián)合索引的最左前綴匹配規(guī)則

還有什么其他類型的索引?

常見(jiàn)的還有：R 樹(shù)和位圖索引。

R 樹(shù)通常用來(lái)為空間問(wèn)題提供幫助。例如，一個(gè)查詢要求“查詢出所有距離我兩公里之內(nèi)的麥當(dāng)勞”，如果數(shù)據(jù)庫(kù)表使用R樹(shù)索引，這類查詢的效率將會(huì)提高。

位圖索引(bitmap index)， 這類索引適合放在包含布爾值(true 和 false)的列上。

索引如何提高性能?

因?yàn)樗饕旧鲜怯脕?lái)存儲(chǔ)列值的數(shù)據(jù)結(jié)構(gòu)，這使查找這些列值更加快速。如果索引使用B+樹(shù)數(shù)據(jù)結(jié)構(gòu)，那么其中的數(shù)據(jù)是有序的，有序的列值可以極大的提升性能。

假如我們?cè)?name 這一列上創(chuàng)建一個(gè) B+樹(shù) 索引，這意味著當(dāng)我們用之前的SQL查找name=‘leixiaoshuai‘時(shí)不需要再掃描全表，而是用索引查找去查找名字為‘leixiaoshuai’的員工，因?yàn)樗饕呀?jīng)按照按字母順序排序。索引已經(jīng)排序意味著查詢一個(gè)名字會(huì)快很多，因?yàn)槊稚僮帜笧?lsquo;L’的員工都是排列在一起的。另外重要的一點(diǎn)是，索引同時(shí)存儲(chǔ)了表中相應(yīng)行的指針以獲取其他列的數(shù)據(jù)。

數(shù)據(jù)庫(kù)索引中到底存的是什么?

你現(xiàn)在已經(jīng)知道數(shù)據(jù)庫(kù)索引是創(chuàng)建在表的某列上的，并且存儲(chǔ)了這一列的所有值。但是需要理解的重點(diǎn)是數(shù)據(jù)庫(kù)索引并不存儲(chǔ)這個(gè)表中其他列(字段)的值。舉例來(lái)說(shuō)，如果我們?cè)? name 列創(chuàng)建索引，那么 age 列和 address 列上的值并不會(huì)存儲(chǔ)在這個(gè)索引當(dāng)中。如果我們確實(shí)把其他所有字段也存儲(chǔ)在個(gè)這個(gè)索引中，那這樣會(huì)占用太大的空間而且會(huì)十分低效。

索引還存儲(chǔ)指向表行的指針

如果我們?cè)谒饕镎业侥骋粭l記錄作為索引的列的值，如何才能找到這一條記錄的其它值呢?

這很簡(jiǎn)單，數(shù)據(jù)庫(kù)索引同時(shí)存儲(chǔ)了指向表中的相應(yīng)行的指針。指針是指一塊內(nèi)存區(qū)域， 該內(nèi)存區(qū)域記錄的是對(duì)硬盤上記錄的相應(yīng)行的數(shù)據(jù)的引用。因此，索引中除了存儲(chǔ)列的值，還存儲(chǔ)著一個(gè)指向在行數(shù)據(jù)的索引。也就是說(shuō)，索引中的name這列的某個(gè)值(或者節(jié)點(diǎn))可以描述為 (“leixiaoshuai”, 0x996996)， 0x996996 就是包含 “leixiaoshuai”那行數(shù)據(jù)在硬盤上的地址。如果沒(méi)有這個(gè)引用，你就只能訪問(wèn)到一個(gè)單獨(dú)的值(“leixiaoshuai”)，而這樣沒(méi)有意義，因?yàn)槟悴荒塬@取這一行記錄的employee的其他值-例如地址(address)和年齡(age)。

數(shù)據(jù)庫(kù)如何知道何時(shí)使用索引?

當(dāng)你運(yùn)行一條查詢 SQL 語(yǔ)句時(shí)，數(shù)據(jù)庫(kù)會(huì)檢查在查詢的列上是否有索引。假設(shè) name 列上確實(shí)創(chuàng)建了索引，數(shù)據(jù)庫(kù)會(huì)接著檢查使用這個(gè)索引做查詢是否合理 ，因?yàn)橛行﹫?chǎng)景下，使用索引比起全表掃描會(huì)更加低效。

可以強(qiáng)制數(shù)據(jù)庫(kù)在查詢中使用索引嗎?

通常來(lái)說(shuō)， 你不會(huì)告訴數(shù)據(jù)庫(kù)什么時(shí)候使用索引，數(shù)據(jù)庫(kù)自己決定。

如何在SQL中創(chuàng)建索引?

下面是在前面示例中的Employee_Name列上創(chuàng)建索引時(shí)實(shí)際SQL的外觀：

CREATE INDEX name_index 
 
ON t_employee (name) 

如何在SQL中創(chuàng)建聯(lián)合(多列)索引?

我們可以在age 和 address 兩列上創(chuàng)建聯(lián)合索引，SQL如下：

CREATE INDEX age_address_index 
 
ON t_employee (age, address) 

可以把數(shù)據(jù)庫(kù)索引類比成什么?

一個(gè)非常好的類比是把數(shù)據(jù)庫(kù)索引看作是書的索引。

你從頭到尾逐字逐行讀完就是「全表掃描」;

你翻看目錄挑選感興趣的部分閱讀就是走了索引。

使用數(shù)據(jù)庫(kù)索引有什么代價(jià)?

既然索引優(yōu)點(diǎn)這么多，那給所有列加上索引不就完事了，no no no，加索引是有代價(jià)的。

(1)索引會(huì)占用空間。你的表越大，索引占用的空間越大。

(2)在更新操作有性能損失。當(dāng)你在表中添加、刪除或者更新行數(shù)據(jù)的時(shí)候， 在索引中也會(huì)有相同的操作。

基本原則是：如果表中某列在查詢過(guò)程中使用的非常頻繁，那就在該列上創(chuàng)建索引。

參考：

How do database indexes work? And, how do indexes help? Provide a tutorial on database indexes.

數(shù)據(jù)庫(kù)索引漫談

-- End --

好了，以上就是數(shù)據(jù)庫(kù)索引先導(dǎo)篇了，也可以叫做入門篇了。后面會(huì)通過(guò)圖解的方式逐步帶大家深入索引的原理，敬請(qǐng)期待!