提問(wèn)：常見(jiàn)索引有哪些？

1、從數(shù)據(jù)結(jié)構(gòu)角度
* B-Tree/B+Tree索引：B-Tree/B+Tree簡(jiǎn)介。
* Hash索引：1、查詢效率非常高，一次查詢即可；2、僅能滿足=、in，不能用于范圍查詢；3、* 只有memory引擎顯示支持。
* 全文索引：用于查找文本中的關(guān)鍵詞，InnoDB和MyISAM都支持。
* R-Tree索引：用于對(duì)GIS數(shù)據(jù)類型創(chuàng)建SPATIAL索引。

2、從物理存儲(chǔ)角度
* 聚集索引：InnoDB的B+Tree索引，葉子節(jié)點(diǎn)保存數(shù)據(jù)，索引和數(shù)據(jù)都存在數(shù)據(jù)文件里，根據(jù)主鍵聚集。
* 非聚集索引：MyISAM的B+Tree索引，葉子節(jié)點(diǎn)保存具體數(shù)據(jù)的地址，索引和數(shù)據(jù)分別存在兩個(gè)文件里，數(shù)據(jù)不聚集。

3、從邏輯角度
* 主鍵索引：一種特殊的唯一索引，不允許有空值。
普通索引或者單列索引。
* 多列索引（復(fù)合索引）：在多個(gè)字段上創(chuàng)建的索引，只有在查詢條件中使用了創(chuàng)建索引時(shí)的第一個(gè)字段，索引才會(huì)被使用。使用復(fù)合索引時(shí)遵循最左前綴集合。
* 唯一索引或者非唯一索引。
* 空間索引：空間索引是對(duì)空間數(shù)據(jù)類型的字段建立的索引，MYSQL中的空間數(shù)據(jù)類型有4種，分別是GEOMETRY、POINT、LINESTRING、POLYGON。

1、索引的本質(zhì)

MySQL官方對(duì)索引的定義為：索引（Index）是幫助MySQL高效獲取數(shù)據(jù)的數(shù)據(jù)結(jié)構(gòu)。提取句子主干，就可以得到索引的本質(zhì)：索引是數(shù)據(jù)結(jié)構(gòu)。

我們知道，數(shù)據(jù)庫(kù)查詢是數(shù)據(jù)庫(kù)的最主要功能之一。我們都希望查詢數(shù)據(jù)的速度能盡可能的快，因此數(shù)據(jù)庫(kù)系統(tǒng)的設(shè)計(jì)者會(huì)從查詢算法的角度進(jìn)行優(yōu)化。最基本的查詢算法當(dāng)然是順序查找（linear search），這種復(fù)雜度為O(n)的算法在數(shù)據(jù)量很大時(shí)顯然是糟糕的，當(dāng)然我們也有很多更優(yōu)秀的查找算法，例如二分查找（binary search）、二叉樹(shù)查找（binary tree search）等。如果稍微分析一下會(huì)發(fā)現(xiàn)，每種查找算法都只能應(yīng)用于特定的數(shù)據(jù)結(jié)構(gòu)之上，例如二分查找要求被檢索數(shù)據(jù)有序，而二叉樹(shù)查找只能應(yīng)用于二叉查找樹(shù)上，但是數(shù)據(jù)本身的組織結(jié)構(gòu)不可能完全滿足各種數(shù)據(jù)結(jié)構(gòu)（例如，理論上不可能同時(shí)將兩列都按順序進(jìn)行組織），所以，在數(shù)據(jù)之外，數(shù)據(jù)庫(kù)系統(tǒng)還維護(hù)著滿足特定查找算法的數(shù)據(jù)結(jié)構(gòu)，這些數(shù)據(jù)結(jié)構(gòu)以某種方式引用（指向）數(shù)據(jù)，這樣就可以在這些數(shù)據(jù)結(jié)構(gòu)上實(shí)現(xiàn)高級(jí)查找算法。這種數(shù)據(jù)結(jié)構(gòu)，就是索引。

image.png

2、B-Tree和B+Tree

目前大部分?jǐn)?shù)據(jù)庫(kù)系統(tǒng)及文件系統(tǒng)都采用B-Tree或其變種B+Tree作為索引結(jié)構(gòu)，所以本小節(jié)先簡(jiǎn)單介紹一下這兩種數(shù)據(jù)結(jié)構(gòu)。

2.1、B-Tree

• d為大于1的一個(gè)正整數(shù)，稱為B-Tree的度。
• h為一個(gè)正整數(shù)，稱為B-Tree的高度。
• 每個(gè)非葉子節(jié)點(diǎn)由n-1個(gè)key和n個(gè)指針組成，其中d<=n<=2d。
• 每個(gè)葉子節(jié)點(diǎn)最少包含一個(gè)key和兩個(gè)指針，最多包含2d-1個(gè)key和2d個(gè)指針，葉節(jié)點(diǎn)的指針均為null 。
• 所有葉節(jié)點(diǎn)具有相同的深度，等于樹(shù)高h(yuǎn)。
• key和指針互相間隔，節(jié)點(diǎn)兩端是指針。
• 一個(gè)節(jié)點(diǎn)中的key從左到右非遞減排列。

image.png

2.2、B+Tree

B-Tree的變種，與B-Tree相比有以下不同點(diǎn)：

• 每個(gè)節(jié)點(diǎn)的指針上限為2d而不是2d+1。
• 內(nèi)節(jié)點(diǎn)不存儲(chǔ)data，只存儲(chǔ)key；葉子節(jié)點(diǎn)不存儲(chǔ)指針。

image.png

2.3、帶順序訪問(wèn)指針的B+Tree

一般在數(shù)據(jù)庫(kù)系統(tǒng)或文件系統(tǒng)中使用的B+Tree結(jié)構(gòu)都在經(jīng)典B+Tree的基礎(chǔ)上進(jìn)行了優(yōu)化，增加了順序訪問(wèn)指針。

image.png

如圖所示，在B+Tree的每個(gè)葉子節(jié)點(diǎn)增加一個(gè)指向相鄰葉子節(jié)點(diǎn)的指針，就形成了帶有順序訪問(wèn)指針的B+Tree。做這個(gè)優(yōu)化的目的是為了提高區(qū)間訪問(wèn)的性能，例如圖4中如果要查詢key為從18到49的所有數(shù)據(jù)記錄，當(dāng)找到18后，只需順著節(jié)點(diǎn)和指針順序遍歷就可以一次性訪問(wèn)到所有數(shù)據(jù)節(jié)點(diǎn)，極大提到了區(qū)間查詢效率。

3、為什么使用B-/+Tree

3.1、主存的存取原理

• 讀取主存時(shí)，將地址信號(hào)放到地址總線上傳給主存，主存讀到地址信號(hào)后，解析信號(hào)并定位到指定存儲(chǔ)單元，然后將此存儲(chǔ)單元數(shù)據(jù)放到數(shù)據(jù)總線上，供其它部件讀取。
• 寫主存時(shí)，系統(tǒng)將要寫入單元地址和數(shù)據(jù)分別放在地址總線和數(shù)據(jù)總線上，主存讀取兩個(gè)總線的內(nèi)容，做相應(yīng)的寫操作。

這里可以看出，主存存取的時(shí)間僅與存取次數(shù)呈線性關(guān)系，因?yàn)椴淮嬖跈C(jī)械操作，兩次存取的數(shù)據(jù)的“距離”不會(huì)對(duì)時(shí)間有任何影響，例如，先取A0再取A1和先取A0再取D3的時(shí)間消耗是一樣的。

image.png

3.2、磁盤的存取原理

當(dāng)需要從磁盤讀取數(shù)據(jù)時(shí)，系統(tǒng)會(huì)將數(shù)據(jù)邏輯地址傳給磁盤，磁盤的控制電路按照尋址邏輯將邏輯地址翻譯成物理地址，即確定要讀的數(shù)據(jù)在哪個(gè)磁道，哪個(gè)扇區(qū)。為了讀取這個(gè)扇區(qū)的數(shù)據(jù)，需要將磁頭放到這個(gè)扇區(qū)上方，為了實(shí)現(xiàn)這一點(diǎn)，磁頭需要移動(dòng)對(duì)準(zhǔn)相應(yīng)磁道，這個(gè)過(guò)程叫做尋道，所耗費(fèi)時(shí)間叫做尋道時(shí)間，然后磁盤旋轉(zhuǎn)將目標(biāo)扇區(qū)旋轉(zhuǎn)到磁頭下，這個(gè)過(guò)程耗費(fèi)的時(shí)間叫做旋轉(zhuǎn)時(shí)間。

由于存儲(chǔ)介質(zhì)的特性，磁盤本身存取就比主存慢很多，再加上機(jī)械運(yùn)動(dòng)耗費(fèi)，磁盤的存取速度往往是主存的幾百分分之一，因此為了提高效率，要盡量減少磁盤I/O。為了達(dá)到這個(gè)目的，磁盤往往不是嚴(yán)格按需讀取，而是每次都會(huì)預(yù)讀，即使只需要一個(gè)字節(jié)，磁盤也會(huì)從這個(gè)位置開(kāi)始，順序向后讀取一定長(zhǎng)度的數(shù)據(jù)放入內(nèi)存。這樣做的理論依據(jù)是計(jì)算機(jī)科學(xué)中著名的局部性原理：當(dāng)一個(gè)數(shù)據(jù)被用到時(shí)，其附近的數(shù)據(jù)也通常會(huì)馬上被使用。

image.png

3.3、B-/+Treed的性能分析

一般使用磁盤I/O次數(shù)評(píng)價(jià)索引結(jié)構(gòu)的優(yōu)劣。根據(jù)B-/+Tree的定義，可知檢索一次最多需要訪問(wèn)h個(gè)節(jié)點(diǎn)。數(shù)據(jù)庫(kù)系統(tǒng)的設(shè)計(jì)者巧妙利用了磁盤預(yù)讀原理，將一個(gè)節(jié)點(diǎn)的大小設(shè)為等于一個(gè)頁(yè)，這樣每個(gè)節(jié)點(diǎn)只需要一次I/O就可以完全載入。為了達(dá)到這個(gè)目的，在實(shí)際實(shí)現(xiàn)B-Tree還需要使用如下技巧：

• 每次新建節(jié)點(diǎn)時(shí)，直接申請(qǐng)一個(gè)頁(yè)的空間，這樣就保證一個(gè)節(jié)點(diǎn)物理上也存儲(chǔ)在一個(gè)頁(yè)里，加之計(jì)算機(jī)存儲(chǔ)分配都是按頁(yè)對(duì)齊的，就實(shí)現(xiàn)了一個(gè)node只需一次I/O。
• B-/+Tree中一次檢索最多需要h-1次I/O（根節(jié)點(diǎn)常駐內(nèi)存），漸進(jìn)復(fù)雜度為O(h)=O(logdN)。一般實(shí)際應(yīng)用中，出度d是非常大的數(shù)字，通常超過(guò)100，因此h非常?。ㄍǔ２怀^(guò)3）。

綜上所述，用B-Tree作為索引結(jié)構(gòu)效率是非常高的。

而紅黑樹(shù)這種結(jié)構(gòu)，h明顯要深的多。由于邏輯上很近的節(jié)點(diǎn)（父子）物理上可能很遠(yuǎn)，無(wú)法利用局部性，所以紅黑樹(shù)的I/O漸進(jìn)復(fù)雜度也為O(h)，效率明顯比B-Tree差很多。

為什么mysql的索引使用B+樹(shù)而不是B樹(shù)呢？

• B+樹(shù)更適合外部存儲(chǔ)(一般指磁盤存儲(chǔ)),由于內(nèi)節(jié)點(diǎn)(非葉子節(jié)點(diǎn))不存儲(chǔ)data，所以一個(gè)節(jié)點(diǎn)可以存儲(chǔ)更多的內(nèi)節(jié)點(diǎn)，每個(gè)節(jié)點(diǎn)能索引的范圍更大更精確。也就是說(shuō)使用B+樹(shù)單次磁盤IO的信息量相比較B樹(shù)更大，IO效率更高。
• mysql是關(guān)系型數(shù)據(jù)庫(kù)，經(jīng)常會(huì)按照區(qū)間來(lái)訪問(wèn)某個(gè)索引列，B+樹(shù)的葉子節(jié)點(diǎn)間按順序建立了鏈指針，加強(qiáng)了區(qū)間訪問(wèn)性，所以B+樹(shù)對(duì)索引列上的區(qū)間范圍查詢很友好。而B(niǎo)樹(shù)每個(gè)節(jié)點(diǎn)的key和data在一起，無(wú)法進(jìn)行區(qū)間查找。

4、Mysql索引的實(shí)現(xiàn)原理

4.1、MyISAM實(shí)現(xiàn)原理

MyISAM中索引檢索的算法為首先按照B+Tree搜索算法搜索索引，如果指定的Key存在，則取出其data域的值，然后以data域的值為地址，讀取相應(yīng)數(shù)據(jù)記錄。

• MyISAM的索引文件僅僅保存數(shù)據(jù)記錄的地址。
• MyISAM的索引方式也叫做“非聚集”的，之所以這么稱呼是為了與InnoDB的聚集索引區(qū)分。

image.png

4.2、InnoDB實(shí)現(xiàn)原理

雖然InnoDB也使用B+Tree作為索引結(jié)構(gòu)，但具體實(shí)現(xiàn)方式卻與MyISAM截然不同。

一個(gè)比較大區(qū)別是InnoDB的數(shù)據(jù)文件本身就是索引文件。從上文知道，MyISAM索引文件和數(shù)據(jù)文件是分離的，索引文件僅保存數(shù)據(jù)記錄的地址。而在InnoDB中，表數(shù)據(jù)文件本身就是按B+Tree組織的一個(gè)索引結(jié)構(gòu)，這棵樹(shù)的葉節(jié)點(diǎn)data域保存了完整的數(shù)據(jù)記錄。這個(gè)索引的key是數(shù)據(jù)表的主鍵，因此InnoDB表數(shù)據(jù)文件本身就是主索引。

image.png

上圖是InnoDB主索引（同時(shí)也是數(shù)據(jù)文件）的示意圖，可以看到葉節(jié)點(diǎn)包含了完整的數(shù)據(jù)記錄。這種索引叫做聚集索引。因?yàn)镮nnoDB的數(shù)據(jù)文件本身要按主鍵聚集，所以InnoDB要求表必須有主鍵（MyISAM可以沒(méi)有），如果沒(méi)有顯式指定，則MySQL系統(tǒng)會(huì)自動(dòng)選擇一個(gè)可以唯一標(biāo)識(shí)數(shù)據(jù)記錄的列作為主鍵，如果不存在這種列，則MySQL自動(dòng)為InnoDB表生成一個(gè)隱含字段作為主鍵，這個(gè)字段長(zhǎng)度為6個(gè)字節(jié)，類型為長(zhǎng)整形。

5、總結(jié)

1. 索引的本質(zhì)：數(shù)據(jù)結(jié)構(gòu)。
2. 索引普遍使用的數(shù)據(jù)結(jié)構(gòu)：B-Tree和B+Tree。
3. 為什么使用B-Tree和B+Tree：具有更好的性能。
4. Mysql索引的實(shí)現(xiàn)原理：B+Tree（MyISAM、InnoDB）。