Mysql Innodb儲存引擎之索引與演演算法

一、概述

索引太少，查詢效率低；索引太多程式效能受到影響，索引的使用應該貼合實際情況。
Innodb 支援的索引包括：

• 全文檢索，使用倒排索引
• 雜湊索引，自適應，不能人為干預，依據緩衝池中的聚集索引頁建立，並不會將整張表進行雜湊索引，所以建立索引非常快。
• B+樹索引，傳統意義上的索引，目前關係型資料庫中最有效和最常用的索引。

B+樹並不能定位到表上具體的行記錄，而是返回該行記錄所在的頁；最後在記憶體中根據 slot槽 資訊，以及行記錄頭中的next record 資訊進行精確定位。

二、資料結構與演演算法

1、二分查詢

二分查詢只能用來對一組有序的線性資料進行查詢，每次取中值，小往前，大往後。時間複雜度 ：log N，如圖為對有序陣列中的數位48的查詢。

2、二叉查詢樹和平衡二元樹

1）二叉查詢樹

二叉查詢樹指的是，一個二元樹中，都滿足：任意節點左子節點比自身小，任意節點右子節點大於自身的二元樹，即為二叉查詢樹。

普通的二元樹無法保證 O(logN) 的存取時間，因為當極端情況下，它甚至可以退化成連結串列。

當把一組有序的資料按序構建一個二元樹，那麼就得到了一個連結串列，此時時間複雜度變為：O(N)

2）平衡二元樹

平衡二元樹是二元搜尋樹，但是它多了一個限制條件：任意節點的兩個子節點的樹高相差不能超過1。構建二元樹的過程中，如果破壞了這個條件，可以通過適當的旋轉來解決。

平衡二元樹保證了時間複雜度為：O(logN)

雖然能保證O(logN) 的存取時間，但是它並不適合用來做資料庫索引：

二元樹樹高攀升非常快(1024 = 2的10次冪)，當資料量非常巨大時log(N) 也是非常可觀的。

其中最糟糕的是，二元樹的葉子節點只能存放一個資料，必定要進行多次的磁碟IO。然而實際應用中相較於CPU的執行指令的時間，頻繁讀取磁碟將是災難性的。所以，二元樹並不適合用來做資料庫的索引。

對於機械硬碟，其存取時間取決於磁碟轉速和磁頭移動時間，這都是由機械結構完成的，對比cpu 中執行的電訊號指令，速度必定天差地別。<CPU的時鐘週期一般以GHz為單位。>

1000萬資料，如果使用平衡二元樹（最壞時間界限為 1.44 * logN ），即便不取最壞時間界，按 log(N) 計算最終約為 24，那麼說明需要進行 24 次磁碟IO，這顯然不行。

【樹高為對數值向上取整，例如：log3 = 1.58，樹高為2；】

三、B+樹

由於平衡二元樹的侷限，所以需要引入B+樹。

B+樹是專為磁碟或其它直接存取輔助裝置設計的一種平衡查詢樹，B+ 樹中，所有記錄節點都是按鍵值大小， 順序存放在同一層的葉子節點上，由各葉子節點指標進行連結。

1、B+樹完整定義

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

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

1）資料項必須存在葉子節點上

2）非葉節點存貯M-1個關鍵字以指示搜尋方向；關鍵字 i 代表非葉節點的第i + 1 棵子樹中最小的關鍵字；假設5階B+樹，那麼它有 5 - 1 = 4 個關鍵字。

3）B+樹要麼只有一個樹葉節點作為根節點(沒有任何兒子節點)；如果它有兒子節點，它的節點數必須屬於集合：{2~M}；

4）除根外，所有非葉節點的兒子節點數必須滿足屬於集合： { M/2 ，M } ；

5）所有樹葉都在相同深度上，且樹葉節點的資料項個數必須屬於集合：{ L/2 ，L } ；

2、關於 M 和 L的選定案例

以下表為例，模擬推演B+樹，主鍵50位元組，算上行記錄本身消耗空間，假定所有欄位總長不超過500位元組：

已知所有行記錄都會消耗一些位元組記錄行資訊：例如變長欄位，行記錄頭，事務ID，回滾指標等等。

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

一個葉子節點代表的是一個資料頁，M 和 L 值的選擇跟他息息相關，假設資料頁大小為：P/位元組 （以本文討論的MySQL為例，一個資料頁大小為16K 也就是 16384 個位元組。）

非葉節點上：B+樹的關鍵字是主鍵，本例假設主鍵為 50 個位元組，M階B+樹的關鍵字為 M -1 個，佔用：50 * （M - 1）個位元組的空間；

再加上它指向 M 個子節點的分支指標，假定每個分支指標占用4個位元組儲存；那麼一個非葉節點中，所有空間消耗共計：50 * （M - 1）+ 4 * M = 54M - 50位元組。

當使用MySQL，且假設主鍵50個位元組，成立不等式： 54M - 50 <= P，其中P = 16384，那麼關於 M 的解為：M <= 302 ，階數M最大可選值約為：302；此處我們最大可以選擇一顆，302 階 B+ 樹。

葉子節點上，已知表中定義的每個行的容量的最大為： 500 位元組，這時成立如下表示式：L * 500 <= 16384 成立，L的解集為：L <= 32 ；這時 L 我們最大可以選擇：32。

如下圖，此時5000W資料，樹高大於3，說明我們只需要最多4次磁碟IO就能查到資料。

參考下圖，平衡二元樹最壞時間界為：1.44 * logN = 25.58 * 1.44 = 36.83；也就是說5000W 資料若使用平衡二叉，樹最壞情況下會超過36 次磁碟IO，最少26次磁碟IO。

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

哈哈哈畫圖太麻煩了，我從資料結構與演演算法分析這本書上拍的照片，機智如我。

這裡只講B+樹定義以及引數選取詳情，B+樹的插入、B+樹的刪除部分類容不在贅述。

四、B+樹索引

一般B+ 樹樹高 為2~4 層，也就是查詢行記錄時一般只需要2 ~ 4 次磁碟IO就能找到行記錄所在的頁。不論聚集索引還是非聚集索引，內部都是高度平衡的，索引的資料都存放於葉子節點，區別是聚集索引的葉子節點存放了整個行記錄資料。

1、聚集索引

聚集索引的葉子節點存放整行資料，每張表只能擁有一個聚集索引。

2、輔助索引

輔助索引的葉子節點儲存了鍵值和一個書籤，該書籤告訴Innodb 儲存引擎從哪裡可以找到於索引相應的行記錄完整資料。<可以認為該書籤就是聚集索引的關鍵字，也就是表的主鍵>

每張表可以有多個輔助索引

使用輔助索引的缺點是，找到輔助索引儲存的書籤後，還需要去離散的讀聚集索引，才能最終得到完整的行資料。

五、關於 Cardinality 值

對於Cardinality的討論都是基於非聚集索引的，每個非聚集索引都會有一個Cardinality值。

1、Cardinality定義

須知並不是所有查詢條件中的列都需要加索引；比如：性別、年紀、科目等取值範圍小、密集分佈的字典量，就不需要建立索引。
Cardinality 表示索引中不重複記錄數量的 預估值 ，一般： Cardinality / 表中記錄行數 應儘量接近 1；如果非常小，則需要考慮該索引是否應該去掉。(聚集索引中該值必定接近於1，沒有討論價值)。

2、Cardinality的更新

• MySQL中由於各儲存引擎對於B+樹索引的實現各不相同，所以Cardinality 的統計是在儲存引擎層實現的。
• 當表中資料量非常巨大時，對Cardinality 進行統計是非常耗時的，它的統計一般使用取樣的方法來進行。
• Cardinality 的存在，可以幫助我們很好的分析索引是否有存在的意義。

六、B+樹索引的使用

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

1、聯合索引

聯合索引是在表上的多個列上建索引，它也是B+樹結構，與單個索引的區別僅是它存在多個列。

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

上表中，設定聯合主鍵idx_ab，其儲存結構如下所述：

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

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

如下sql 不能使用該索引；檢視範例圖中聯合索引葉子節點存放的資料我們可以發現：兩個葉子節點上，關於欄位b的存放顯然不是有序的。

	select * from t where b = ?

聯合索引本身還有一個好處，輔助索引本身已經對第二個鍵值進行了排序，如下語句可以避免多一次的排序。

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

輔助索引中已經對 b 列進行了排序，所以此時使用輔助索引更高效。

2、覆蓋索引

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

再形如：select count(*) from table name where b <= ? and b >= ? 的sql，如果有滿足條件的輔助索引，它會優先使用輔助索引因為輔助索引體積遠遠小於聚集索引。

3、優化器選擇不使用索引的情況

某些情況下，通過EXPLAIN指令會發現一些SQL，並沒有選擇使用滿足條件的輔助索引去查資料，而是直接選擇了全表掃描(聚集索引)，這種情況一般發生於 範圍查詢、join連結操作等情況下。

當發生此類查詢時，一般是查詢一個較大範圍內的資料，當範圍較大時同樣意味著大量的資料需要再進行一次書籤存取去獲取完整資料，已知順序讀取速度大於離散讀取速度，所以此時不會使用輔助索引，而是直接查聚集索引(整表掃描)。（一般當存取資料超過表中資料總數 20%時，就不會再進行索引覆蓋，而是進行全表掃描。）

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

如上定義表，a和b兩列構成聯合索引，列a上有獨立的輔助索引，對於語句：

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

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

4、索引提示

索引提示指MySQL支援在SQL中顯式的告訴優化器使用哪個索引。

當優化器選擇索引錯誤，可以手動指定索引。[極小概率事件]

當索引太多時，優化器選擇索引的操作時間開銷大，此時可以手動指定索引。

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

5、Multi-Range Read 優化 (MRR)

MySQL5.6版本開始支援Multi-Range Read (MRR) 優化，它的目的是減少磁碟的離散讀，將離散的存取優化為相對有序的存取，它使用於 range ref eq_ref 型別的查詢。

1).MRR優化有如下好處：

• 它使得資料存取變得較為順序，當根據輔助索引查詢時，會將查詢結果按照主鍵排序後，再去聚集索引進行書籤查詢。
• 減少緩衝池中頁被替換的次數；
• 批次處理對鍵值的查詢操作；

2).對於 JOIN 和 範圍查詢，Innodb 中MRR的工作方式為：

• 將通過輔助索引查詢到的資料放到一個快取中，此時這些資料是按照輔助索引鍵值排序的；
• 將快取中的資料按照主鍵順序排序；
• 根據主鍵順序存取實際資料檔案；

可以想象，當緩衝池不夠大的時候進行大範圍資料的查詢，那麼會頻繁出現資料頁被從LRU列表剔除的情況。如果被查詢的輔助索引不是按主鍵排序的，可能會多次發生如下的情況：一個頁在同一次查詢中被剔出LRU列表後又再次被載入出來。

設定項：read_rnd_buffer_size 用來設定上述描述的鍵值緩衝區大小，預設為256K；當發生溢位時，執行器只對已經快取的資料進行排序。

3).對於範圍查詢：MMR還支援對鍵值的拆分，將範圍查詢拆分為鍵值對進行批次的資料查詢.

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語句的條件可以拆分為鍵值對集合：{( 50 , 100 ),( 50 , 101 ),......,( 50 , 20000 )}，這樣就將範圍查詢優化為對鍵值對的查詢；否則會進行範圍查詢，將 b ∈ {100，20000} 的所有資料都取出。

Multi-Range Read 是否啟用，由如下引數中的，mrr 和 mrr_cost_based 標記進行控制，mrr標記是 MRR優化的開關。若前者設定為on，後者設定為off表示當滿足條件時總是使用MRR優化；若前者設定為 on，後者也設定 on 表示通過 cost base 方式判斷是否需要 MRR優化。

6、Index Condition Pushdown 優化 （ICP）

ICP優化也從MySQL 5.6 開始支援，它是一種根據索引進行查詢的優化方式，它支援對：range、ref、eq_ref、ref_or_null 型別的查詢進行優化。

• 禁用ICP時，儲存引擎層會通過遍歷索引，定位完整的行記錄；然後返回給資料庫層(Server層)，再去為這些資料行進行where條件的過濾。
• 啟用ICP時，如果where條件可以使用索引，MySQL會把這部分過濾操作放到儲存引擎層，儲存引擎通過索引過濾，把滿足where 條件的資料取出整行資料並返回。 ICP可以減少儲存引擎層存取行記錄的次數以及資料庫層(Server層)必須存取儲存引擎的次數。

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

Index Condition Pushdown工作原理如下：

1)不使用ICP時

（1）當儲存引擎讀取下一行時，從輔助索引的葉子節點讀到相關的行記錄，然後使用該記錄的書籤中的主鍵參照，以查詢完整的行記錄返回給資料庫層(Server層)。

（2） 資料庫層對完整的行記錄進行where條件過濾，如果該行資料滿足where條件則使用，否則丟棄。

（3）執行第1步，直到讀完所有滿足條件的資料。

2）使用ICP時，如何進行索引掃描

（1）儲存引擎從索引中逐條讀取資料......

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

（3）最後儲存引擎層會將所有滿足查詢條件資料的完整行記錄返回資料庫層。

（4）資料庫層再繼續使用，沒有被索引覆蓋到的where後的查詢條件進行過濾。

總結

到此這篇關於Mysql Innodb儲存引擎之索引與演演算法的文章就介紹到這了,更多相關Innodb索引與演演算法內容請搜尋it145.com以前的文章或繼續瀏覽下面的相關文章希望大家以後多多支援it145.com！