索引，類似于圖書目錄，可以根據(jù)目錄某個(gè)頁(yè)碼立即找到對(duì)應(yīng)的內(nèi)容。
索引的有點(diǎn)顯而易見：（有可能）提升查詢效率
同時(shí)也有缺點(diǎn)：增大數(shù)據(jù)庫(kù)空間占用，降低表更新的效率

從實(shí)現(xiàn)上來(lái)說(shuō)，索引可以分為兩種：聚集索引、非聚集索引。
說(shuō)到索引的實(shí)現(xiàn)，不得不提B+樹，提到B+樹，就要先搞明白B樹。

一、B樹與B+樹

1.B樹

B樹是一種多路平衡查找樹，一個(gè)高度為m的B樹有以下幾個(gè)特點(diǎn)：
1.根節(jié)點(diǎn)至少有兩個(gè)子節(jié)點(diǎn)；
2.每個(gè)中間節(jié)點(diǎn)都包含k-1個(gè)元素和k個(gè)子節(jié)點(diǎn)，其中m/2 <= k <= m；
3.每個(gè)葉節(jié)點(diǎn)包含k-1個(gè)元素，其中m/2 <= k <= m；
4.所有的葉節(jié)點(diǎn)都位于同一層；
5.每個(gè)節(jié)點(diǎn)中的元素從小到大排列，節(jié)點(diǎn)中k-1個(gè)元素正好是k個(gè)子節(jié)點(diǎn)所包含元素的值域劃分。

B樹

查找

MySQL將數(shù)據(jù)按照頁(yè)來(lái)存儲(chǔ)，默認(rèn)一頁(yè)為16KB，查詢時(shí)，不會(huì)只加載某一條數(shù)據(jù)，而是將目標(biāo)所在的頁(yè)都加載到PageCache中。B樹中，一個(gè)節(jié)點(diǎn)代表了一頁(yè)，查找的時(shí)候，每經(jīng)過(guò)一個(gè)節(jié)點(diǎn)就需要一次磁盤IO，可以發(fā)現(xiàn)，以上圖中的B樹為例，查找的最壞情況需要3次磁盤IO，即樹的高度。

插入

B樹還有一個(gè)特點(diǎn)，自平衡，這也使得其在插入新數(shù)據(jù)的時(shí)候比較復(fù)雜。還是用上圖的B樹舉例，假設(shè)我們要插入一個(gè)新值4。自頂向下查找到應(yīng)該插入的位置，發(fā)現(xiàn)應(yīng)該在3,5之間。

插入4

節(jié)點(diǎn)3，5已經(jīng)是兩元素節(jié)點(diǎn)，無(wú)法再增加。父親節(jié)點(diǎn) 2， 6 也是兩元素節(jié)點(diǎn)，也無(wú)法再增加。根節(jié)點(diǎn)9是單元素節(jié)點(diǎn)，可以升級(jí)為兩元素節(jié)點(diǎn)。于是拆分節(jié)點(diǎn)3，5與節(jié)點(diǎn)2，6，讓根節(jié)點(diǎn)9升級(jí)為兩元素節(jié)點(diǎn)4，9。節(jié)點(diǎn)6獨(dú)立為根節(jié)點(diǎn)的第二個(gè)孩子。

自平衡

刪除

再來(lái)看看刪除，假設(shè)我們要?jiǎng)h除11這個(gè)數(shù)據(jù)。

刪除11

刪除11后，節(jié)點(diǎn)12只有一個(gè)孩子，不符合B樹規(guī)范。因此找出12,13,15三個(gè)節(jié)點(diǎn)的中位數(shù)13，取代節(jié)點(diǎn)12，而節(jié)點(diǎn)12自身下移成為第一個(gè)孩子。（這個(gè)過(guò)程稱為左旋）

左旋

最終結(jié)果

B樹主要應(yīng)用于文件系統(tǒng)及某些數(shù)據(jù)庫(kù)索引，比如MongoDB。對(duì)于同等數(shù)量的數(shù)據(jù)，相較于二叉查找樹，B樹的每一層能存放更多數(shù)據(jù)，二叉樹比較“瘦高”，而B樹比較“胖矮”，這樣能有效減少查詢過(guò)程中磁盤IO的次數(shù)。

2.B+樹

B+樹在B樹的基礎(chǔ)上做了改進(jìn)。先來(lái)看看B+樹的特征：
1.有k個(gè)子樹的中間節(jié)點(diǎn)包含有k個(gè)元素（B樹中是k-1個(gè)元素），每個(gè)元素不保存數(shù)據(jù)，只用來(lái)索引，所有數(shù)據(jù)都保存在葉子節(jié)點(diǎn)。
2.所有的葉子結(jié)點(diǎn)中包含了全部元素的信息，及指向含這些元素記錄的指針，且葉子結(jié)點(diǎn)本身依關(guān)鍵字的大小自小而大順序鏈接。
3.所有的中間節(jié)點(diǎn)元素都同時(shí)存在于子節(jié)點(diǎn)，在子節(jié)點(diǎn)元素中是最大（或最?。┰亍?/p>

B+樹

圖中的B+樹，父節(jié)點(diǎn)中的元素是各子節(jié)點(diǎn)中的最大元素?？梢园l(fā)現(xiàn)，根節(jié)點(diǎn)的最大值15，也是整個(gè)樹的最大值；此外，所有的葉節(jié)點(diǎn)包含了全量元素，每個(gè)葉節(jié)點(diǎn)都有一個(gè)指針指向下一個(gè)葉節(jié)點(diǎn)，形成了一個(gè)有序鏈表。

除此之外，還需要了解一個(gè)概念——衛(wèi)星數(shù)據(jù)（Satellite Data）。所謂衛(wèi)星數(shù)據(jù)，指的是索引元素所指向的數(shù)據(jù)記錄，比如數(shù)據(jù)庫(kù)中的某一行。B樹中，無(wú)論是中間節(jié)點(diǎn)還是葉節(jié)點(diǎn)，都帶有衛(wèi)星數(shù)據(jù)。這個(gè)特點(diǎn)會(huì)導(dǎo)致中間節(jié)點(diǎn)不能存儲(chǔ)大量的索引。

B樹

而B+樹針對(duì)這個(gè)做了優(yōu)化，只有葉節(jié)點(diǎn)帶有衛(wèi)星數(shù)據(jù)，中間節(jié)點(diǎn)只包含索引元素和指針。

B+樹

我們假設(shè)一個(gè)非頁(yè)子節(jié)點(diǎn)是 16kb，每個(gè)索引，即主鍵是 bigint，即 8b，指針為 8b。那么每頁(yè)能存儲(chǔ)大約 1000 個(gè)索引(16KB / (8B + 8B))。
而一顆 3 層的 B+樹能夠存儲(chǔ)多少索引呢？如下圖：

索引

大約能夠存儲(chǔ) 10 億個(gè)索引。由此可見，相比于B樹，B+樹更加矮胖，查詢的時(shí)候（平均情況下）磁盤IO的次數(shù)更少。

除此之外，范圍查詢時(shí)，B樹找到范圍起始的索引元素后，只能通過(guò)中序遍歷的方式，過(guò)程復(fù)雜；而B+樹由于葉節(jié)點(diǎn)全量的元素形成了一個(gè)鏈表，方便快捷。

相比較于B樹，B+樹實(shí)現(xiàn)索引有以下三個(gè)特點(diǎn)：1.更少的磁盤IO；2.查詢性能穩(wěn)定（因?yàn)镮O次數(shù)總等于樹高）；3.范圍查詢簡(jiǎn)便。

二、索引分類

1.單列索引 與 復(fù)合索引

只包含一個(gè)字段的索引叫做單列索引，包含兩個(gè)或以上字段的索引叫做復(fù)合索引（或組合索引）。建立復(fù)合索引時(shí)，字段的順序極其重要。
下面這個(gè)SQL語(yǔ)句在 列X，列Y，列Z 上建立了一個(gè)復(fù)合索引。

CREATE INDEX 索引名 ON 表名(列名X, 列名Y, 列名Z);

其實(shí)這相當(dāng)于建立了三個(gè)索引，分別是：
1、單列索引（列X） 2、復(fù)合索引（列X, 列Y） 3、復(fù)合索引（列X，列Y，列Z）。

2.唯一索引 與 主鍵

唯一索引是在表上一個(gè)或者多個(gè)字段組合建立的索引，這個(gè)（或這幾個(gè)）字段的值組合起來(lái)在表中不可以重復(fù)。一張表可以建立任意多個(gè)唯一索引，但一般只建立一個(gè)。

主鍵是一種特殊的唯一索引，區(qū)別在于，唯一索引列允許null值，而主鍵列不允許為null值。一張表最多建立一個(gè)主鍵，也可以不建立主鍵。

3.聚簇索引、非聚簇索引

聚簇索引的葉子節(jié)點(diǎn)就是數(shù)據(jù)節(jié)點(diǎn)，而非聚簇索引的葉子節(jié)點(diǎn)仍然是索引節(jié)點(diǎn)，只不過(guò)有指向?qū)?yīng)數(shù)據(jù)塊的指針。通常我們建表的時(shí)候，會(huì)指定一個(gè)字段為主鍵，主鍵唯一且不能為空，一般情況下主鍵就是聚簇索引。一張表只允許存在一個(gè)聚簇索引，因?yàn)檎鎸?shí)數(shù)據(jù)的物理順序只能有一種。如果一張表上還沒(méi)有聚簇索引，為它新創(chuàng)建聚簇索引時(shí)，就需要對(duì)已有數(shù)據(jù)重新進(jìn)行排序，所以對(duì)表進(jìn)行修改速度較慢是聚簇索引的缺點(diǎn)，對(duì)于經(jīng)常更新的列不宜建立聚簇索引。

我們總說(shuō)的數(shù)據(jù)庫(kù)調(diào)優(yōu)的手段之一——建索引，通常指的是非聚簇索引。一張表可以建立任意多個(gè)索引，每個(gè)索引可以是任意多個(gè)字段的組合。索引可能會(huì)提高查詢速度（如果查詢時(shí)使用了索引），但一定會(huì)減慢寫入速度，因?yàn)槊看螌懭霑r(shí)都需要更新索引，所以索引只應(yīng)該加在經(jīng)常需要搜索的列上，不要加在寫多讀少的列上。

執(zhí)行某條查詢SQL，從非聚簇索引到聚簇索引，再到數(shù)據(jù)節(jié)點(diǎn)，流程如下：

不管以任何方式查詢表， 最終都會(huì)利用主鍵通過(guò)聚簇索引來(lái)定位到數(shù)據(jù)， 聚簇索引（主鍵）是通往真實(shí)數(shù)據(jù)所在的唯一路徑。然而凡事都有例外，有一種非主流的方式可以不通過(guò)聚簇索引就能查詢出所需要的數(shù)據(jù)，這就是覆蓋索引。當(dāng)為字段建立索引以后， 字段中的內(nèi)容會(huì)被同步到索引之中， 如果為一個(gè)索引指定兩個(gè)字段， 那么這個(gè)兩個(gè)字段的內(nèi)容都會(huì)被同步至索引之中。

先看下面這個(gè)SQL語(yǔ)句

-- 建立索引
create index index_birthday_and_user_name on user_info(birthday, user_name);
-- 查詢生日在1991年11月1日出生用戶的用戶名
select user_name from user_info where birthday = '1991-11-1'

這句SQL語(yǔ)句的執(zhí)行過(guò)程如下：

通過(guò)非聚集索引index_birthday_and_user_name查找birthday等于1991-11-1的葉節(jié)點(diǎn)的內(nèi)容，然而， 葉節(jié)點(diǎn)中除了有user_name表主鍵ID的值以外， user_name字段的值也在里面， 因此不需要通過(guò)主鍵ID值的查找數(shù)據(jù)行的真實(shí)所在， 直接取得葉節(jié)點(diǎn)中user_name的值返回即可。 通過(guò)這種覆蓋索引直接查找的方式， 可以省略不使用覆蓋索引查找的后面兩個(gè)步驟， 大大的提高了查詢性能。

4.其他

其他索引的類型還有外鍵索引、全文索引等，這里簡(jiǎn)單帶過(guò)，不再展開來(lái)講。

外鍵索引：只有InnoDB類型的表才可以使用外鍵索引，保證數(shù)據(jù)的一致性、完整性和實(shí)現(xiàn)級(jí)聯(lián)操作。

全文索引：MySQL 自帶的全文索引只能用于 InnoDB、MyISAM ，并且只能對(duì)英文進(jìn)行全文檢索，一般使用全文索引引擎（ES，Solr）。