1、索引概述

索引（index）
是幫助MySQL高效獲取數(shù)據(jù)的數(shù)據(jù)結(jié)構(gòu)（有序）。在數(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

左邊是數(shù)據(jù)表，一共有兩列七條記錄，最左邊的是數(shù)據(jù)記錄的物理地址（注意邏輯上相鄰的記錄在磁盤上也并不是一定物理相鄰的）。

為了加快Col2的查找，可以維護(hù)一個(gè)右邊所示的二叉查找樹，每個(gè)節(jié)點(diǎn)分別包含索引鍵值和一個(gè)指向?qū)?yīng)數(shù)據(jù)記錄物理地址的指針，這樣就可以運(yùn)用二叉查找快速獲取到相應(yīng)數(shù)據(jù)。

一般來(lái)說(shuō)索引本身也很大，不可能全部存儲(chǔ)在內(nèi)存中，因此索引往往以索引文件的形式存儲(chǔ)在磁盤上。索引是數(shù)據(jù)庫(kù)中用來(lái)提高性能的最常用的工具。

畫圖分析：

image.png

2、索引的優(yōu)勢(shì)與劣勢(shì)

優(yōu)勢(shì)：
1）類似于書籍的目錄索引，提高數(shù)據(jù)檢索的效率，降低數(shù)據(jù)庫(kù)的IO成本。
2）通過(guò)索引列對(duì)數(shù)據(jù)進(jìn)行排序，降低數(shù)據(jù)排序的成本，降低CPU的消耗。

劣勢(shì)
1）實(shí)際上索引也是一張表，該表中保存了主鍵與索引字段，并指向?qū)嶓w類的記錄，所以索引列也是要占用空間的。
2）雖然索引大大提高了查詢效率，同時(shí)卻也降低更新表的速度，如對(duì)表進(jìn)行INSERT、UPDATE、DELETE。因?yàn)楦卤頃r(shí)，MySQL 不僅要保存數(shù)據(jù)，還要保存一下索引文件，每次更新添加了索引列的字段，都會(huì)調(diào)整因?yàn)楦滤鶐?lái)的鍵值變化后的索引信息。

3、索引結(jié)構(gòu)

索引是在MySQL的存儲(chǔ)引擎層中實(shí)現(xiàn)的，而不是在服務(wù)器層實(shí)現(xiàn)的。所以每種存儲(chǔ)引擎的索引都不一定完全相同，也不是所有的存儲(chǔ)引擎都支持所有的索引類型的。

MySQL目前提供了以下4種索引：

① BTREE 索引：最常見的索引類型，大部分索引都支持 B 樹索引。
② HASH 索引：只有Memory引擎支持，使用場(chǎng)景簡(jiǎn)單。
③ R-tree 索引（空間索引）：空間索引是MyISAM引擎的一個(gè)特殊索引類型，主要用于地理空間數(shù)據(jù)類型，通常使用較少，不做特別介紹。
④ Full-text （全文索引）：全文索引也是MyISAM的一個(gè)特殊索引類型，主要用于全文索引，InnoDB從Mysql5.6版本開始支持全文索引。

MyISAM、InnoDB、Memory三種存儲(chǔ)引擎對(duì)各種索引類型的支持：

image.png

我們平常所說(shuō)的索引，如果沒有特別指明，都是指B+樹（多路搜索樹，并不一定是二叉的）結(jié)構(gòu)組織的索引。其中聚集索引、復(fù)合索引、前綴索引、唯一索引默認(rèn)都是使用B+tree 索引，統(tǒng)稱為索引。

3.1、BTREE 結(jié)構(gòu)

BTree又叫多路平衡搜索樹，一顆m叉的BTree特性如下：

樹中每個(gè)節(jié)點(diǎn)最多包含m個(gè)孩子。
除根節(jié)點(diǎn)與葉子節(jié)點(diǎn)外，每個(gè)節(jié)點(diǎn)至少有[ceil(m/2)]個(gè)孩子。
若根節(jié)點(diǎn)不是葉子節(jié)點(diǎn)，則至少有兩個(gè)孩子。
所有的葉子節(jié)點(diǎn)都在同一層。
每個(gè)非葉子節(jié)點(diǎn)由n個(gè)key與n+1個(gè)指針組成，其中[ceil(m/2)-1] <= n <= m-1

以5叉BTree為例，key的數(shù)量：公式推導(dǎo)[ceil(m/2)-1] <= n <= m-1。所以 2 <= n <=4 。當(dāng)n>4時(shí)，中間節(jié)點(diǎn)分裂到父節(jié)點(diǎn)，兩邊節(jié)點(diǎn)分裂。

插入 C N G A H E K Q M F W L T Z D P R X Y S 數(shù)據(jù)為例。

演變過(guò)程如下：
1). 插入前4個(gè)字母 C N G A