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

在這裡插入圖片描述

【樹高為對數值向上取整，例如：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 = 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 進行統計是非常耗時的，它的統計一般使用取樣的方法來進行。

。。。。。。待續

六、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 優化部分，參考了下文：//blog.csdn.net/wanbin6470398/article/details/82351161

Tags:

VirMach 便宜 VPS

QNews

QNews