MySQL索引、算法（基於InnoDB引擎）和優化

來源：https://www.jianshu.com/p/fded71cd0264

索引

索引是應用程序設計和開發的一個重要方面。如果索引太多，應用的性能可能會受到影響；如果索引太少，對查詢性能又會產生影響。

1 innodb存儲引擎介紹

innodb存儲引擎支持兩種常見的索引：B+樹索引和哈希索引。

innodb支持哈希索引是自適應的，innodb會根據表的使用情況自動生成哈希索引。

B+樹索引就是傳統意義上的索引，是關係型數據庫中最常用最有效的索引。B+樹是從最早的平衡二叉樹演變而來，但是B+樹不是一個二叉樹。B+中的B不代表二叉(Binary),而是代表平衡(Balance)。

注意：

B+樹索引並不能找到一個鍵值對應的具體行。b+樹索引只能查到被查找數據行所在的頁，然後數據庫通過把頁讀入內存，再在內存中查找，最後得到結果。

2 B+樹索引介紹

B+樹索引的本質是B+樹在數據庫中的實現。但是B+樹索引有一個特點是高扇出性，因此在數據庫中，B+樹的高度一般在2到3層。也就是說查找某一鍵值的記錄，最多隻需要2到3次IO開銷。按磁盤每秒100次IO來計算，查詢時間只需0.0.2到0.03秒。

數據庫中B+樹索引分為聚集索引（clustered index)和非聚集索引（secondary index)，這兩種索引的共同點是內部都是B+樹，高度都是平衡的，葉節點存放著所有數據。不同點是葉節點是否存放著一整行數據。

1. 聚集索引

Innodb存儲引擎表是索引組織表，即表中數據按主鍵順序存放。而聚集索引就是按每張表的主鍵構造一顆B+樹。並且葉節點存放整張表的行記錄數據。每張表只能有一個聚集索引（一個主鍵）。

聚集索引的另一個好處是它對於主鍵的排序查找和範圍的速度非常快。葉節點的數據就是我們要找的數據。

2. 輔助索引

輔助索引（也稱非聚集索引）。葉級別不包含行的全部數據，葉級別除了包含行的鍵值以外，每個索引行還包含了一個書籤（bookmark），該書籤告訴innodb存儲引擎，哪裡可以找到與索引對應的數據。

輔助索引的存在並不影響數據再聚集索引中的組織，因此一個表可以有多個輔助索引。當通過輔助索引查找數據時，innodb會遍歷輔助索引並通過葉級別的指針獲得指向主鍵索引的主鍵。然後再通過主鍵索引找到一行完整的數據

3 使用場景

1. 快速查找符合where條件的記錄
2. 快速確定候選集。若where條件使用了多個索引字段，則MySQL會優先使用能使候選記錄集規模最小的那個索引，以便儘快淘汰不符合條件的記錄。
3. 如果表中存在幾個字段構成的聯合索引，則查找記錄時，這個聯合索引的最左前綴匹配字段也會被自動作為索引來加速查找。例如，若為某表創建了3個字段(c1, c2, c3)構成的聯合索引，則(c1), (c1, c2), (c1, c2, c3)均會作為索引，(c2, c3)就不會被作為索引，而(c1, c3)其實只利用到c1索引。
4. 多表做join操作時會使用索引（如果參與join的字段在這些表中均建立了索引的話）
5. 若某字段已建立索引，求該字段的min()或max()時，MySQL會使用索引
6. 對建立了索引的字段做sort或group操作時，MySQL會使用索引

4 建立、修改索引

1 索引創建：兩種方式

ALTER [ONLINE | OFFLINE] [IGNORE] TABLE tbl_name| ADD {INDEX|KEY}
 [index_name] [index_type] (index_col_name,...) [index_option]
CREATE [ONLINE|OFFLINE] [UNIQUE|FULLTEXT|SPATIAL] INDEX index_name 
 [index_type] ON tbl_name (index_col_name,...)

2 索引刪除：兩種方式

ALTER [ONLINE | OFFLINE] [IGNORE] TABLE tbl_name 
| DROP PRIMARY KEY | DROP {INDEX|KEY} index_names
DROP [ONLINE|OFFLINE] INDEX index_name ON tbl_name

算法（B+樹）

B+樹是為磁盤及其他存儲輔助設備而設計一種平衡查找樹（不是二叉樹）。B+樹中，所有記錄的節點按大小順序存放在同一層的葉節點中，各葉節點用指針進行連接。

下面演示一個B+數結構，高度為2，每頁可放4條記錄，扇出(fan out)為5。從下圖1可以看出，所有記錄都在頁節點中，並且為順序存放，我們從最左邊的葉節點開始遍歷，可以得到所有鍵值的順序排序：5、10、15、20、25、30、50、55、60、65、75、80、85、90.

圖1 高度為2的B+樹

1. B+樹的插入操作
2. B+樹的插入必須保證插入後葉節點的記錄依然排序。同時要考慮插入B+樹的三種情況，每種情況都可能導致不同的插入算法。如下表所示：

1. 
   
2. B+樹插入的3種情況
3. 我們實例分析B+樹的插入，在圖1的B+樹中，我們需要插入28這個值。因為Leaf Page和Index page都沒有滿，我們直接將記錄插入葉節點就可以了。如下圖2所示：

1. 
   
2. 圖2 插入鍵值28
3. 下面我們再插入70這個值，這時Leaf Page已經滿了，但是Index Page還沒有滿，符合上面的第二種情況。這時插入Leaf Page的情況為50、55、60、65、70.我們根據中間的值60拆分葉節點，可得到下圖3所示（雙項鍊表指針依然存在，沒有畫出)：

1. 
   
2. 圖3 插入鍵值70
3. 
   
4. 
   
5. 最後我們再插入95，這個Leaf Page和Index Page都滿了，符合上面第三種情況。需要做2次拆分，如下圖4所示：

1. 
   
2. 圖4 插入鍵值95
3. 
   
4. 可以看到，不管怎麼變化，B+樹總會保持平衡。但是為了保持平衡，對於新插入的鍵值可能需要做大量的拆分頁操作。B+樹主要用於磁盤，拆分意味著磁盤的操作，應該在可能的情況下儘量減少頁的拆分。因此，B+樹提供了旋轉功能。旋轉發生在Leaf Page已經滿了，但是左右兄弟節點沒有滿的情況下。這時B+樹並不是急著做頁的拆分，而是旋轉。旋轉結果如圖5所示，可以看到旋轉操作使B+樹減少了一次頁的拆分操作，高度仍然為2.

1. 
   
2. 圖5 B+樹的旋轉操作
3. 
   
4. B+樹的刪除操作
5. B+樹使用填充因子來控制數的刪除變化。填充因子可以設置的最小值為50%。B+樹的刪除操作同樣保證刪除後葉節點的記錄依然排序。
6. 根據填充因子的變化，B+樹刪除依然需要考慮三種情況，如下表所示：

根據圖4的B+樹，我們進行刪除操作，首先刪除鍵值為70的這條記錄，該記錄符合上表第一種情況，刪除後如下圖6所示：

圖6 刪除鍵值70

接著我們刪除鍵值為25的記錄，這也是屬於上表第一種情況，不同的是該值還是index page中的值。因此在刪除Leaf Page中的25後，還需要將25的右兄弟節點28更新到Index Page中，如下圖7所示（圖中有兩個筆誤，紅色為修正值）：

圖7 刪除鍵值28

最後我們刪除鍵值為60的記錄。刪除Leaf page鍵值為60的記錄後，其填充因子小於50%。需要做合併操作。同樣在刪除Index page中相關記錄後需要做Index Page的合併操作。

優化

MySQL數據庫是常見的兩個瓶頸是CPU和I/O的瓶頸，CPU在飽和的時候一般發生在數據裝入內存或從磁盤上讀取數據時候。磁盤I/O瓶頸發生在裝入數據遠大於內存容量的時候，如果應用分佈在網絡上，那麼查詢量相當大的時候那麼平瓶頸就會出現在網絡上，我們可以用mpstat, iostat, sar和vmstat來查看系統的性能狀態。

除了服務器硬件的性能瓶頸，對於MySQL系統本身，我們可以使用工具來優化數據庫的性能，通常有三種：使用索引，使用EXPLAIN分析查詢以及調整MySQL的內部配置

1 性能分析工具

show profile;
mysqlsla; // 壓測
mysqldumpslow; // 慢查詢slow sql
explain;
show slow log;
show processlist;
show query_response_time(percona);

2 Explain

explain select count(*) from XXX;
+----+-------------+---------+------+---------------+------+---------+------+------+-------+
| id | select_type | table | type | possible_keys | key | key_len | ref | **rows** | Extra |
+----+-------------+---------+------+---------------+------+---------+------+------+-------+
| 1 | SIMPLE | XXX | ALL | NULL | NULL | NULL | NULL | 6897 | NULL |+----+-------------+---------+------+---------------+------+---------+------+------+-------+

EXPLAIN字段:

• id:本次 select 的標識符。在查詢中每個 select都有一個順序的數值。
• select_type:

SIMPLE：查詢中不包含子查詢或者UNION

PRIMARY：查詢中若包含任何複雜的子部分，最外層查詢則被標記為

SUBQUERY：在SELECT或WHERE列表中包含了子查詢，該子查詢被標記為

DERIVED（衍生)：在FROM列表中包含的子查詢被標記為

UNION: 若第二個SELECT出現在UNION之後，則被標記為UNION；若UNION包含在 FROM子句的子查詢中，外層SELECT將被標記為：DERIVED

從UNION表獲取結果的SELECT被標記為：UNION RESULT

• Table：顯示這一行的數據是關於哪張表的
• possible_keys：顯示可能應用在這張表中的索引。如果為空，沒有可能的索引。可以為相關的域從WHERE語句中選擇一個合適的語句
• key：實際使用的索引。如果為NULL，則沒有使用索引。MYSQL很少會選擇優化不足的索引，此時可以在SELECT語句中使用USE INDEX（index）來強制使用一個索引或者用IGNORE INDEX（index）來強制忽略索引
• key_len：使用的索引的長度。在不損失精確性的情況下，長度越短越好
• ref：顯示索引的哪一列被使用了，如果可能的話，是一個常數
• rows：MySQL認為必須檢索的用來返回請求數據的行數
• type：這是最重要的字段之一，顯示查詢使用了何種類型。從最好到最差的連接類型為system、const、eq_reg、ref、range、index和ALL

system、const：可以將查詢的變量轉為常量. 如id=1; id為 主鍵或唯一鍵.

eq_ref：訪問索引,返回某單一行的數據.(通常在聯接時出現，查詢使用的索引為主鍵或惟一鍵)

ref：訪問索引,返回某個值的數據.(可以返回多行) 通常使用=時發生

range：這個連接類型使用索引返回一個範圍中的行，比如使用>或

index：以索引的順序進行全表掃描，優點是不用排序,缺點是還要全表掃描

ALL：全表掃描，應該儘量避免

• Extra：關於MYSQL如何解析查詢的額外信息。
• 主要有以下幾種：

using index：只用到索引,可以避免訪問表.

using where：使用到where來過慮數據. 不是所有的where clause都要顯示using where. 如以=方式訪問索引.

using tmporary：用到臨時表

using filesort：用到額外的排序. (當使用order by v1,而沒用到索引時,就會使用額外的排序)

range checked for eache record(index map:N)：沒有好的索引.

閱讀更多 javafirst 的文章

關鍵字: 算法 性能 程序設計