溫馨提示×
您好，登錄后才能下訂單哦！
點擊 登錄注冊 即表示同意《億速云用戶服務條款》
您好，登錄后才能下訂單哦！
這篇文章將為大家詳細講解有關Mysql Innodb存儲引擎之索引與算法的示例分析，小編覺得挺實用的，因此分享給大家做個參考，希望大家閱讀完這篇文章后可以有所收獲。
索引太少，查詢效率低；索引太多程序性能受到影響，索引的使用應該貼合實際情況。
Innodb 支持的索引包括：
全文檢索，使用倒排索引
哈希索引，自適應，不能人為干預，依據緩沖池中的聚集索引頁創建，并不會將整張表進行哈希索引，所以建立索引非常快。
B+樹索引，傳統意義上的索引，目前關系型數據庫中最有效和最常用的索引。
B+樹并不能定位到表上具體的行記錄，而是返回該行記錄所在的頁；最后在內存中根據 slot槽 信息，以及行記錄頭中的next record 信息進行精確定位。
二分查找只能用來對一組有序的線性數據進行查找，每次取中值，小往前，大往后。時間復雜度 ：log N，如圖為對有序數組中的數字48的查找。
二叉查找樹指的是，一個二叉樹中，都滿足：任意節點左子節點比自身小，任意節點右子節點大于自身的二叉樹，即為二叉查找樹。
普通的二叉樹無法保證 O(logN) 的訪問時間，因為當極端情況下，它甚至可以退化成鏈表。
當把一組有序的數據按序構建一個二叉樹，那么就得到了一個鏈表，此時時間復雜度變為：O(N)
平衡二叉樹是二叉搜索樹，但是它多了一個限制條件：任意節點的兩個子節點的樹高相差不能超過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+ 樹中，所有記錄節點都是按鍵值大小， 順序存放在同一層的葉子節點上，由各葉子節點指針進行鏈接。
一顆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 } ；
以下表為例，模擬推演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+ 樹樹高 為2~4 層，也就是查找行記錄時一般只需要2 ~ 4 次磁盤IO就能找到行記錄所在的頁。不論聚集索引還是非聚集索引，內部都是高度平衡的，索引的數據都存放于葉子節點，區別是聚集索引的葉子節點存放了整個行記錄數據。
聚集索引的葉子節點存放整行數據，每張表只能擁有一個聚集索引。
輔助索引的葉子節點存儲了鍵值和一個書簽，該書簽告訴Innodb 存儲引擎從哪里可以找到于索引相應的行記錄完整數據。<可以認為該書簽就是聚集索引的關鍵字，也就是表的主鍵>
每張表可以有多個輔助索引
使用輔助索引的缺點是，找到輔助索引存儲的書簽后，還需要去離散的讀聚集索引，才能最終得到完整的行數據。
對于Cardinality的討論都是基于非聚集索引的，每個非聚集索引都會有一個Cardinality值。
須知并不是所有查詢條件中的列都需要加索引；比如：性別、年紀、科目等取值范圍小、密集分布的字典量，就不需要建立索引。
Cardinality 表示索引中不重復記錄數量的 預估值 ，一般： Cardinality / 表中記錄行數 應盡量接近 1；如果非常小，則需要考慮該索引是否應該去掉。(聚集索引中該值必定接近于1，沒有討論價值)。
MySQL中由于各存儲引擎對于B+樹索引的實現各不相同，所以Cardinality 的統計是在存儲引擎層實現的。
當表中數據量非常巨大時，對Cardinality 進行統計是非常耗時的，它的統計一般使用采樣的方法來進行。
Cardinality 的存在，可以幫助我們很好的分析索引是否有存在的意義。
【 本部分討論的索引多指輔助索引，對聚集索引的查詢一般稱為全表掃描。】
聯合索引是在表上的多個列上建索引，它也是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 列進行了排序，所以此時使用輔助索引更高效。
Innodb 支持覆蓋索引(covering index，或稱為索引覆蓋)，即從輔助索引中就可以得到結果，而不需要查詢聚集索引中的記錄。因為輔助索引不包含完整的行記錄，所以它比聚集索引要小很多，可以減少大量IO操作。
再形如：select count(*) from table name where b <= ? and b >= ? 的sql，如果有滿足條件的輔助索引，它會優先使用輔助索引因為輔助索引體積遠遠小于聚集索引。
某些情況下，通過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。
索引提示指MySQL支持在SQL中顯式的告訴優化器使用哪個索引。
當優化器選擇索引錯誤，可以手動指定索引。[極小概率事件]
當索引太多時，優化器選擇索引的操作時間開銷大，此時可以手動指定索引。
使用索引提示的前提是我們自己要對sql的執行非常了解，非常明確該操作能帶來更好的效率。
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優化。
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存儲引擎之索引與算法的示例分析”這篇文章就分享到這里了，希望以上內容可以對大家有一定的幫助，使各位可以學到更多知識，如果覺得文章不錯，請把它分享出去讓更多的人看到。
免責聲明：本站發布的內容（圖片、視頻和文字）以原創、轉載和分享為主，文章觀點不代表本網站立場，如果涉及侵權請聯系站長郵箱：is@yisu.com進行舉報，并提供相關證據，一經查實，將立刻刪除涉嫌侵權內容。
