一、概述

索引太少，查詢效率低；索引太多程序性能受到影響，索引的使用應(yīng)該貼合實(shí)際情況。
Innodb 支持的索引包括：

• 全文檢索，使用倒排索引
• 哈希索引，自適應(yīng)，不能人為干預(yù)，依據(jù)緩沖池中的聚集索引頁創(chuàng)建，并不會(huì)將整張表進(jìn)行哈希索引，所以建立索引非常快。
• B+樹索引，傳統(tǒng)意義上的索引，目前關(guān)系型數(shù)據(jù)庫中最有效和最常用的索引。

B+樹并不能定位到表上具體的行記錄，而是返回該行記錄所在的頁；最后在內(nèi)存中根據(jù) slot槽 信息，以及行記錄頭中的next record 信息進(jìn)行精確定位。

二、數(shù)據(jù)結(jié)構(gòu)與算法

1、二分查找

二分查找只能用來對(duì)一組有序的線性數(shù)據(jù)進(jìn)行查找，每次取中值，小往前，大往后。時(shí)間復(fù)雜度 ：log N，如圖為對(duì)有序數(shù)組中的數(shù)字48的查找。

2、二叉查找樹和平衡二叉樹

1）二叉查找樹

二叉查找樹指的是，一個(gè)二叉樹中，都滿足：任意節(jié)點(diǎn)左子節(jié)點(diǎn)比自身小，任意節(jié)點(diǎn)右子節(jié)點(diǎn)大于自身的二叉樹，即為二叉查找樹。

普通的二叉樹無法保證 O(logN) 的訪問時(shí)間，因?yàn)楫?dāng)極端情況下，它甚至可以退化成鏈表。

當(dāng)把一組有序的數(shù)據(jù)按序構(gòu)建一個(gè)二叉樹，那么就得到了一個(gè)鏈表，此時(shí)時(shí)間復(fù)雜度變?yōu)椋篛(N)

2）平衡二叉樹

平衡二叉樹是二叉搜索樹，但是它多了一個(gè)限制條件：任意節(jié)點(diǎn)的兩個(gè)子節(jié)點(diǎn)的樹高相差不能超過1。構(gòu)建二叉樹的過程中，如果破壞了這個(gè)條件，可以通過適當(dāng)?shù)男D(zhuǎn)來解決。

平衡二叉樹保證了時(shí)間復(fù)雜度為：O(logN)

雖然能保證O(logN) 的訪問時(shí)間，但是它并不適合用來做數(shù)據(jù)庫索引：

二叉樹樹高攀升非常快(1024 = 2的10次冪)，當(dāng)數(shù)據(jù)量非常巨大時(shí)log(N) 也是非常可觀的。

其中最糟糕的是，二叉樹的葉子節(jié)點(diǎn)只能存放一個(gè)數(shù)據(jù)，必定要進(jìn)行多次的磁盤IO。然而實(shí)際應(yīng)用中相較于CPU的執(zhí)行指令的時(shí)間，頻繁讀取磁盤將是災(zāi)難性的。所以，二叉樹并不適合用來做數(shù)據(jù)庫的索引。

對(duì)于機(jī)械硬盤，其訪問時(shí)間取決于磁盤轉(zhuǎn)速和磁頭移動(dòng)時(shí)間，這都是由機(jī)械結(jié)構(gòu)完成的，對(duì)比cpu 中執(zhí)行的電信號(hào)指令，速度必定天差地別。<CPU的時(shí)鐘周期一般以GHz為單位。>

1000萬數(shù)據(jù)，如果使用平衡二叉樹（最壞時(shí)間界限為 1.44 * logN ），即便不取最壞時(shí)間界，按 log(N) 計(jì)算最終約為 24，那么說明需要進(jìn)行 24 次磁盤IO，這顯然不行。

【樹高為對(duì)數(shù)值向上取整，例如：log3 = 1.58，樹高為2；】

三、B+樹

由于平衡二叉樹的局限，所以需要引入B+樹。

B+樹是專為磁盤或其它直接存取輔助設(shè)備設(shè)計(jì)的一種平衡查找樹，B+ 樹中，所有記錄節(jié)點(diǎn)都是按鍵值大小， 順序存放在同一層的葉子節(jié)點(diǎn)上，由各葉子節(jié)點(diǎn)指針進(jìn)行鏈接。

1、B+樹完整定義

一顆M階的B+樹需要滿足如下的性質(zhì)：

下列所有定義中的關(guān)于兩數(shù)相除，不能整除時(shí)往上取整，而不是丟棄小數(shù)位。(案例中推演不等式除外)

1）數(shù)據(jù)項(xiàng)必須存在葉子節(jié)點(diǎn)上

2）非葉節(jié)點(diǎn)存貯M-1個(gè)關(guān)鍵字以指示搜索方向；關(guān)鍵字 i 代表非葉節(jié)點(diǎn)的第i + 1 棵子樹中最小的關(guān)鍵字；假設(shè)5階B+樹，那么它有 5 - 1 = 4 個(gè)關(guān)鍵字。

3）B+樹要么只有一個(gè)樹葉節(jié)點(diǎn)作為根節(jié)點(diǎn)(沒有任何兒子節(jié)點(diǎn))；如果它有兒子節(jié)點(diǎn)，它的節(jié)點(diǎn)數(shù)必須屬于集合：{2~M}；

4）除根外，所有非葉節(jié)點(diǎn)的兒子節(jié)點(diǎn)數(shù)必須滿足屬于集合： { M/2 ，M } ；

5）所有樹葉都在相同深度上，且樹葉節(jié)點(diǎn)的數(shù)據(jù)項(xiàng)個(gè)數(shù)必須屬于集合：{ L/2 ，L } ；

2、關(guān)于 M 和 L的選定案例

以下表為例，模擬推演B+樹，主鍵50字節(jié)，算上行記錄本身消耗空間，假定所有字段總長(zhǎng)不超過500字節(jié)：

已知所有行記錄都會(huì)消耗一些字節(jié)記錄行信息：例如變長(zhǎng)字段，行記錄頭，事務(wù)ID，回滾指針等等。

create table context(
	id  varchar(50) primary key,
	name varchar(50) not null,
	description varchar(360)  
);

一個(gè)葉子節(jié)點(diǎn)代表的是一個(gè)數(shù)據(jù)頁，M 和 L 值的選擇跟他息息相關(guān)，假設(shè)數(shù)據(jù)頁大小為：P/字節(jié) （以本文討論的MySQL為例，一個(gè)數(shù)據(jù)頁大小為16K 也就是 16384 個(gè)字節(jié)。）

非葉節(jié)點(diǎn)上：B+樹的關(guān)鍵字是主鍵，本例假設(shè)主鍵為 50 個(gè)字節(jié)，M階B+樹的關(guān)鍵字為 M -1 個(gè)，占用：50 * （M - 1）個(gè)字節(jié)的空間；

再加上它指向 M 個(gè)子節(jié)點(diǎn)的分支指針，假定每個(gè)分支指針占用4個(gè)字節(jié)存儲(chǔ)；那么一個(gè)非葉節(jié)點(diǎn)中，所有空間消耗共計(jì)：50 * （M - 1）+ 4 * M = 54M - 50字節(jié)。

當(dāng)使用MySQL，且假設(shè)主鍵50個(gè)字節(jié)，成立不等式： 54M - 50 <= P，其中P = 16384，那么關(guān)于 M 的解為：M <= 302 ，階數(shù)M最大可選值約為：302；此處我們最大可以選擇一顆，302 階 B+ 樹。

葉子節(jié)點(diǎn)上，已知表中定義的每個(gè)行的容量的最大為： 500 字節(jié)，這時(shí)成立如下表達(dá)式：L * 500 <= 16384 成立，L的解集為：L <= 32 ；這時(shí) L 我們最大可以選擇：32。

如下圖，此時(shí)5000W數(shù)據(jù)，樹高大于3，說明我們只需要最多4次磁盤IO就能查到數(shù)據(jù)。

參考下圖，平衡二叉樹最壞時(shí)間界為：1.44 * logN = 25.58 * 1.44 = 36.83；也就是說5000W 數(shù)據(jù)若使用平衡二叉，樹最壞情況下會(huì)超過36 次磁盤IO，最少26次磁盤IO。

如圖為一顆5 階普通B+樹 (M = 5)，此處每個(gè)節(jié)點(diǎn)最多5個(gè)值（L = 5）; M和L不一定相等，就如上述分析而言: M 和 L視實(shí)際情況而定。

哈哈哈畫圖太麻煩了，我從數(shù)據(jù)結(jié)構(gòu)與算法分析這本書上拍的照片，機(jī)智如我。

這里只講B+樹定義以及參數(shù)選取詳情，B+樹的插入、B+樹的刪除部分類容不在贅述。

四、B+樹索引

一般B+ 樹樹高 為2~4 層，也就是查找行記錄時(shí)一般只需要2 ~ 4 次磁盤IO就能找到行記錄所在的頁。不論聚集索引還是非聚集索引，內(nèi)部都是高度平衡的，索引的數(shù)據(jù)都存放于葉子節(jié)點(diǎn)，區(qū)別是聚集索引的葉子節(jié)點(diǎn)存放了整個(gè)行記錄數(shù)據(jù)。

1、聚集索引

聚集索引的葉子節(jié)點(diǎn)存放整行數(shù)據(jù)，每張表只能擁有一個(gè)聚集索引。

2、輔助索引

輔助索引的葉子節(jié)點(diǎn)存儲(chǔ)了鍵值和一個(gè)書簽，該書簽告訴Innodb 存儲(chǔ)引擎從哪里可以找到于索引相應(yīng)的行記錄完整數(shù)據(jù)。<可以認(rèn)為該書簽就是聚集索引的關(guān)鍵字，也就是表的主鍵>

每張表可以有多個(gè)輔助索引

使用輔助索引的缺點(diǎn)是，找到輔助索引存儲(chǔ)的書簽后，還需要去離散的讀聚集索引，才能最終得到完整的行數(shù)據(jù)。

五、關(guān)于 Cardinality 值

對(duì)于Cardinality的討論都是基于非聚集索引的，每個(gè)非聚集索引都會(huì)有一個(gè)Cardinality值。

1、Cardinality定義

須知并不是所有查詢條件中的列都需要加索引；比如：性別、年紀(jì)、科目等取值范圍小、密集分布的字典量，就不需要建立索引。
Cardinality 表示索引中不重復(fù)記錄數(shù)量的 預(yù)估值 ，一般： Cardinality / 表中記錄行數(shù) 應(yīng)盡量接近 1；如果非常小，則需要考慮該索引是否應(yīng)該去掉。(聚集索引中該值必定接近于1，沒有討論價(jià)值)。

2、Cardinality的更新

• MySQL中由于各存儲(chǔ)引擎對(duì)于B+樹索引的實(shí)現(xiàn)各不相同，所以Cardinality 的統(tǒng)計(jì)是在存儲(chǔ)引擎層實(shí)現(xiàn)的。
• 當(dāng)表中數(shù)據(jù)量非常巨大時(shí)，對(duì)Cardinality 進(jìn)行統(tǒng)計(jì)是非常耗時(shí)的，它的統(tǒng)計(jì)一般使用采樣的方法來進(jìn)行。
• Cardinality 的存在，可以幫助我們很好的分析索引是否有存在的意義。

六、B+樹索引的使用

【 本部分討論的索引多指輔助索引，對(duì)聚集索引的查詢一般稱為全表掃描。】

1、聯(lián)合索引

聯(lián)合索引是在表上的多個(gè)列上建索引，它也是B+樹結(jié)構(gòu)，與單個(gè)索引的區(qū)別僅是它存在多個(gè)列。

create table t (
	a int,
	b int,
	primary key (a),
	key idx_ab (a, b)
)engine=innodb;

上表中，設(shè)置聯(lián)合主鍵idx_ab，其存儲(chǔ)結(jié)構(gòu)如下所述：

如上圖所述，鍵值有序，需要注意的是，如下SQL可以使用該索引：

	select * from t where a = ? and b = ?
	
	select * from t where a = ? 

如下sql 不能使用該索引；查看示例圖中聯(lián)合索引葉子節(jié)點(diǎn)存放的數(shù)據(jù)我們可以發(fā)現(xiàn)：兩個(gè)葉子節(jié)點(diǎn)上，關(guān)于字段b的存放顯然不是有序的。

	select * from t where b = ?

聯(lián)合索引本身還有一個(gè)好處，輔助索引本身已經(jīng)對(duì)第二個(gè)鍵值進(jìn)行了排序，如下語句可以避免多一次的排序。

	select b from t where a = ?  order by b desc

輔助索引中已經(jīng)對(duì) b 列進(jìn)行了排序，所以此時(shí)使用輔助索引更高效。

2、覆蓋索引

Innodb 支持覆蓋索引(covering index，或稱為索引覆蓋)，即從輔助索引中就可以得到結(jié)果，而不需要查詢聚集索引中的記錄。因?yàn)檩o助索引不包含完整的行記錄，所以它比聚集索引要小很多，可以減少大量IO操作。

再形如：select count(*) from table name where b <= ? and b >= ? 的sql，如果有滿足條件的輔助索引，它會(huì)優(yōu)先使用輔助索引因?yàn)檩o助索引體積遠(yuǎn)遠(yuǎn)小于聚集索引。

3、優(yōu)化器選擇不使用索引的情況

某些情況下，通過EXPLAIN指令會(huì)發(fā)現(xiàn)一些SQL，并沒有選擇使用滿足條件的輔助索引去查數(shù)據(jù)，而是直接選擇了全表掃描(聚集索引)，這種情況一般發(fā)生于 范圍查找、join鏈接操作等情況下。

當(dāng)發(fā)生此類查找時(shí)，一般是查找一個(gè)較大范圍內(nèi)的數(shù)據(jù)，當(dāng)范圍較大時(shí)同樣意味著大量的數(shù)據(jù)需要再進(jìn)行一次書簽訪問去獲取完整數(shù)據(jù)，已知順序讀取速度大于離散讀取速度，所以此時(shí)不會(huì)使用輔助索引，而是直接查聚集索引(整表掃描)。（一般當(dāng)訪問數(shù)據(jù)超過表中數(shù)據(jù)總數(shù) 20%時(shí)，就不會(huì)再進(jìn)行索引覆蓋，而是進(jìn)行全表掃描。）

	create table t (
		a int,
		b int,
		primary key (a,b),
		key idx_a (a)
	)engine=innodb;

如上定義表，a和b兩列構(gòu)成聯(lián)合索引，列a上有獨(dú)立的輔助索引，對(duì)于語句：

select * from  t where  a >= 3  and a<= 1000000;

按理說，該語句是可以選擇使用輔助索引 idx_a 進(jìn)行查找的，但是通過執(zhí)行 explain 發(fā)現(xiàn)該語句發(fā)生了全表掃描(聚集索引)，而不是使用輔助索引： idx_a。

4、索引提示

索引提示指MySQL支持在SQL中顯式的告訴優(yōu)化器使用哪個(gè)索引。

當(dāng)優(yōu)化器選擇索引錯(cuò)誤，可以手動(dòng)指定索引。[極小概率事件]

當(dāng)索引太多時(shí)，優(yōu)化器選擇索引的操作時(shí)間開銷大，此時(shí)可以手動(dòng)指定索引。

使用索引提示的前提是我們自己要對(duì)sql的執(zhí)行非常了解，非常明確該操作能帶來更好的效率。

5、Multi-Range Read 優(yōu)化 (MRR)

MySQL5.6版本開始支持Multi-Range Read (MRR) 優(yōu)化，它的目的是減少磁盤的離散讀，將離散的訪問優(yōu)化為相對(duì)有序的訪問，它使用于 range ref eq_ref 類型的查詢。

1).MRR優(yōu)化有如下好處：

• 它使得數(shù)據(jù)訪問變得較為順序，當(dāng)根據(jù)輔助索引查詢時(shí)，會(huì)將查詢結(jié)果按照主鍵排序后，再去聚集索引進(jìn)行書簽查詢。
• 減少緩沖池中頁被替換的次數(shù)；
• 批量處理對(duì)鍵值的查詢操作；

2).對(duì)于 JOIN 和 范圍查詢，Innodb 中MRR的工作方式為：

• 將通過輔助索引查詢到的數(shù)據(jù)放到一個(gè)緩存中，此時(shí)這些數(shù)據(jù)是按照輔助索引鍵值排序的；
• 將緩存中的數(shù)據(jù)按照主鍵順序排序；
• 根據(jù)主鍵順序訪問實(shí)際數(shù)據(jù)文件；

可以想象，當(dāng)緩沖池不夠大的時(shí)候進(jìn)行大范圍數(shù)據(jù)的查詢，那么會(huì)頻繁出現(xiàn)數(shù)據(jù)頁被從LRU列表剔除的情況。如果被查詢的輔助索引不是按主鍵排序的，可能會(huì)多次發(fā)生如下的情況：一個(gè)頁在同一次查詢中被剔出LRU列表后又再次被加載出來。

配置項(xiàng)：read_rnd_buffer_size 用來配置上述描述的鍵值緩沖區(qū)大小，默認(rèn)為256K；當(dāng)發(fā)生溢出時(shí)，執(zhí)行器只對(duì)已經(jīng)緩存的數(shù)據(jù)進(jìn)行排序。

3).對(duì)于范圍查詢：MMR還支持對(duì)鍵值的拆分，將范圍查詢拆分為鍵值對(duì)進(jìn)行批量的數(shù)據(jù)查詢.

create table t (
	a integer,
	b integer,
	primary key (a),
	key idx_ab (a, b)
)engine=innodb;

select * from t where a = 50  and  b>= 100 and  b<= 20000

由于存在輔助索引 idx_ab，上述sql語句的條件可以拆分為鍵值對(duì)集合：{( 50 , 100 ),( 50 , 101 ),......,( 50 , 20000 )}，這樣就將范圍查詢優(yōu)化為對(duì)鍵值對(duì)的查詢；否則會(huì)進(jìn)行范圍查詢，將 b ∈ {100，20000} 的所有數(shù)據(jù)都取出。

Multi-Range Read 是否啟用，由如下參數(shù)中的，mrr 和 mrr_cost_based 標(biāo)記進(jìn)行控制，mrr標(biāo)記是 MRR優(yōu)化的開關(guān)。若前者設(shè)置為on，后者設(shè)置為off表示當(dāng)滿足條件時(shí)總是使用MRR優(yōu)化；若前者設(shè)置為 on，后者也設(shè)置 on 表示通過 cost base 方式判斷是否需要 MRR優(yōu)化。

6、Index Condition Pushdown 優(yōu)化 （ICP）

ICP優(yōu)化也從MySQL 5.6 開始支持，它是一種根據(jù)索引進(jìn)行查詢的優(yōu)化方式，它支持對(duì)：range、ref、eq_ref、ref_or_null 類型的查詢進(jìn)行優(yōu)化。

• 禁用ICP時(shí)，存儲(chǔ)引擎層會(huì)通過遍歷索引，定位完整的行記錄；然后返回給數(shù)據(jù)庫層(Server層)，再去為這些數(shù)據(jù)行進(jìn)行where條件的過濾。
• 啟用ICP時(shí)，如果where條件可以使用索引，MySQL會(huì)把這部分過濾操作放到存儲(chǔ)引擎層，存儲(chǔ)引擎通過索引過濾，把滿足where 條件的數(shù)據(jù)取出整行數(shù)據(jù)并返回。 ICP可以減少存儲(chǔ)引擎層訪問行記錄的次數(shù)以及數(shù)據(jù)庫層(Server層)必須訪問存儲(chǔ)引擎的次數(shù)。

【使用這個(gè)過濾的前提是：該過濾條件需要是，索引可以覆蓋到的范圍】

Index Condition Pushdown工作原理如下：

1)不使用ICP時(shí)

（1）當(dāng)存儲(chǔ)引擎讀取下一行時(shí)，從輔助索引的葉子節(jié)點(diǎn)讀到相關(guān)的行記錄，然后使用該記錄的書簽中的主鍵引用，以查詢完整的行記錄返回給數(shù)據(jù)庫層(Server層)。

（2） 數(shù)據(jù)庫層對(duì)完整的行記錄進(jìn)行where條件過濾，如果該行數(shù)據(jù)滿足where條件則使用，否則丟棄。

（3）執(zhí)行第1步，直到讀完所有滿足條件的數(shù)據(jù)。

2）使用ICP時(shí)，如何進(jìn)行索引掃描

（1）存儲(chǔ)引擎從索引中逐條讀取數(shù)據(jù)......

（2）存儲(chǔ)引擎從索引讀取數(shù)據(jù)時(shí)，根據(jù)索引的key使用where條件過濾，如果該行記錄不滿足條件，存儲(chǔ)引擎將會(huì)處理下一條數(shù)據(jù)（回到上一步）。只有滿足查詢條件的時(shí)候，才會(huì)繼續(xù)去聚集索引中讀取完整數(shù)據(jù)。

（3）最后存儲(chǔ)引擎層會(huì)將所有滿足查詢條件數(shù)據(jù)的完整行記錄返回?cái)?shù)據(jù)庫層。

（4）數(shù)據(jù)庫層再繼續(xù)使用，沒有被索引覆蓋到的where后的查詢條件進(jìn)行過濾。

總結(jié)

到此這篇關(guān)于Mysql Innodb存儲(chǔ)引擎之索引與算法的文章就介紹到這了,更多相關(guān)Innodb索引與算法內(nèi)容請(qǐng)搜索腳本之家以前的文章或繼續(xù)瀏覽下面的相關(guān)文章希望大家以后多多支持腳本之家！