MySQL之Innodb索引與算法

Innodb 索引與算法

• 一、概述
• 二、資料結構與算法
• • 1、二分查找
  • 2、二叉查找樹和平衡二叉樹
  • • 1）二叉查找樹
    • 2）平衡二叉樹
• 三、B+樹
• • 1、B+樹完整定義
  • 2、關于 M 和 L的標明案例
• 四、B+樹索引
• • 1、聚集索引
  • 2、輔助索引
• 五、Cardinality 值
• • 1、Cardinality定義
  • 2、Cardinality的更新
• 六、B+樹索引的使用
• • 1、聯合索引
  • 2、覆寫索引
  • 3、優化器選擇不使用索引的情況
  • 4、索引提示
  • 5、Multi-Range Read 優化 (MRR)
  • 6、Index Condition Pushdown 優化 （ICP）

一、概述

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

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，這顯然不行。

【樹高為對數值向上取整，例如：log2 = 1，但是樹高為2；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)  
);
           

1. 一個葉子節點代表的是一個資料頁，M 和 L 值的選擇跟他息息相關，假設資料頁大小為：P/位元組 （以本文讨論的MySQL為例，一個資料頁大小為16K 也就是 16384 個位元組。）
2. 非葉節點上：B+樹的關鍵字是主鍵，本例假設主鍵為 50 個位元組，M階B+樹的關鍵字為 M -1 個，占用：50 * （M - 1）個位元組的空間；
3. 再加上它指向 M 個子節點的分支指針，假定每個分支指針占用4個位元組存儲；那麼一個非葉節點中，所有空間消耗共計：50 * （M - 1）+ 4 * M = 54M - 50位元組。

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

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

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

參考下圖，平衡二叉樹最壞時間界為：1.44 * logN = 1.44 * 25.58 = 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 進行統計是非常耗時的，它的統計一般使用采樣的方法來進行。

六、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時，存儲引擎層會通過周遊索引，定位完整的行記錄；然後傳回給資料庫層，再去為這些資料行進行where條件的過濾。
• 啟用ICP時，如果where條件可以使用索引，MySQL會把這部分過濾操作放到存儲引擎層，存儲引擎通過索引過濾，把滿足where 條件的資料取出整行資料并傳回。 ICP可以減少存儲引擎層通路行記錄的次數以及Server層必須通路存儲引擎的次數。

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

Index Condition Pushdown工作原理如下：

1)不使用ICP時

（1）當存儲引擎讀取下一行時，從葉子節點讀到相關的行記錄<聚集索引的引用書簽>，然後使用書簽引用查詢完整的行記錄。

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

（3）執行第1步，直到最後一行資料。

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

（1）存儲引擎從索引中讀取下一條記錄。

（2）存儲引擎從索引讀取資料，根據索引的key使用where條件過濾，如果不滿足條件，存儲引擎将會處理下一條資料（回到上一步）。隻有滿足下推的索引條件的時候，才會繼續去葉子節點中讀取資料。

（3）最後存儲引擎層會将所有滿足被索引覆寫到的條件，的資料傳回資料庫層。

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

本文來自我對 《MySQL技術内幕：InnoDB存儲引擎》一書閱讀過後的二次創作，檔案頗多截圖引用書中插圖，此外本文主要用作個人學習後的思考感悟的記錄，或許不如原書講得深入且全面，強烈建議購買原書深入了解更多的細節。

關于ICP 優化部分，參考了下文：https://blog.csdn.net/wanbin6470398/article/details/82351161