在我之前的一篇文章中，有參考一個討論用Hash還是Tree的問題，DB中關于查找類資料結構，除了樹，還有Hash(HashMap，HashSet)，
存盤資料結構之爭
B+樹主要是照顧磁盤IO這種特殊的性質應運而生的；然而在記憶體夠多夠大時，Hash某些時候比Tree結構有用得多，
但是Hash做索引的缺點也非常明顯：
1，Hash沖突造成的散列不均勻，線性查找浪費時間；
2，不支持范圍查詢，避免不了全表掃描；
3，記憶體空間要求高，
MySQL中，InnoDB和MyISAM默認的索引是B+ Tree索引；Memory則同時支持Hash和Tree索引(可在創建時直接指定使用何種索引，具體移步），
同時，Memory這種存盤引擎“斷電即毀”的特性也不再推薦使用，
B樹和B+樹之爭
前置知識：知道mysql中索引即資料，資料即索引(頁的存盤結構)；知道為何采用B樹(多路平衡查找樹)，知道為何實際采用了B+樹，
1，B+樹空間利用率更高，B+樹只在葉子節點存盤實際資料，非葉子節點，B+樹有了更多的空間存盤索引，這樣B+樹越靠近矮胖，IO減少，
磁盤讀寫代價低，檢索效率變高，
2，B+樹查詢效率更穩定，B+樹的檢索，任何檢索路徑都需要從根節點到葉子節點（只有葉子節點有資料），時間復雜度固定在O(LogN)；
B樹則在O(1)和O(LogN)之間，即二分查找，
3，B+樹范圍查詢性能更優， B+樹的葉子節點使用了雙向鏈表連接在一起，而且是嚴格的順序存盤，從左到右從小到大，
4，B+樹由于葉子節點使用了鏈表進行串聯，除了支持隨機檢索，還支持順序檢索，
一些常見概念
回表： 查詢計劃不是使用主鍵索引，即通過二級索引查找目標；而二級索引的B+樹只存盤了主鍵資料(索引列，主鍵)，
如仍需要其它資料，需要再次根據主鍵去主鍵索引所在B+樹查找一次資料的程序，即回表，
回表引發的問題：某些情況，使用了索引，但仍然觸發了全表掃描（explain type='All'），因為此時查詢優化器對比了回表IO次數和全表掃描的IO次數，選擇了全表掃描，
MRR：MRR全稱：Multi-Range Read Optimization(多范圍讀取優化)，動機是減少隨機磁盤訪問的次數，實作對基表資料的更順序掃描，
官網的解釋在這，即把隨機磁盤讀轉化為順序磁盤讀，提高查詢性能（磁頭運動&磁盤預讀），本質在做一件以空間換時間的事情，
下面這個圖很形象借用一下：（紅線表示查詢路線，藍線表示磁盤/磁頭運動路線）
未開啟MRR：
開啟MRR：
上面的圖來自文章MySQL的MRR到底是什么？
以空間換時間，這個空間指的是記憶體，記憶體大小設定在系統變數read_rnd_buffer_size，設定請參考官網，
使用SQL命令：SELECT @@optimizer_switch
查看MRR是否已開啟（默認開啟）
索引覆寫：查詢目標可直接從葉子節點獲取資料，不需要回表，即為索引覆寫，
如下圖：country_id是二級索引，查找目標剛好只查詢主鍵索引和二級索引鍵值本身，直接使用二級索引的B+樹就能查到，不需要回表，稱為索引覆寫，
最左匹配原則（多列索引）： 官網的解釋在這里，
舉例：
有組合索引資訊如下：
則驗證的關鍵原則是：
-- 最左匹配原則要點： -- 1，組合索引第一列（最左）作為第一個條件，只有接or不走索引，其它情況全部走索引； -- 2，不以最左作為第一個條件，一般都不會走索引，唯有把組合索引條件都加上才會走（內部優化）， explain select * from staff where first_name='Mike'; -- yes explain select * from staff where last_name='Hillyer'; -- no explain select * from staff where first_name='Mike' and last_name='Hillyer'; -- yes explain select * from staff where last_name='Hillyer' and first_name='Mike'; -- yes（內部優化） explain select * from staff where first_name='Mike' or last_name='Hillyer'; -- no explain select * from staff where first_name='Mike' and(last_name='Hillyer' or last_name=''); -- yes
索引(條件)下推：即ICP，全稱是Index Condition Pushdown Optimization，官網的解釋在這里，我們一般叫索引下推，其實正式應該稱為：索引條件下推，
怎么理解？下推什么呢？ 顧名思義，Condition Pushdown，把查詢條件往下推，官網的這句：
With ICP enabled, ... , the MySQL server pushes this part of the WHERE condition down to the storage engine.
翻譯即是：ICP啟用后，把where條件的部分從server層下推到storage engine層，
需要先了解MySQL的大概架構：
就是，原來where條件篩選在Server層這里，現在下推到存盤引擎層去，
舉例：
下表中，id是主鍵，name，age是聯合索引，
查找姓張且年齡是10歲的記錄：select * from tuser where name like '張%' and age=10;
沒有使用ICP：二級索引找到主鍵1和4，分別回表去查找對應的完整記錄，Server層再根據where條件的age=10進行篩選，這個程序要回表兩次，
使用ICP： 二級索引找到主鍵1和4，存盤引擎層（Server的下層）根據聯合索引where條件age=10進行篩選，根據篩選結果再回表查到完整記錄，這個程序回表1次，
上面的ICP舉例和圖片出自這里，
使用執行計劃分析時，使用索引下推在Extra欄位會出現：Using index condition資訊，具體參見，
MySQL默認啟用索引（條件）下推，系統設定變數為：index_condition_pushdown
避免全表掃描：官網的解釋在這里，
使用查詢計劃分析時，對于大型表，應盡力避免type=All的情況， 表掃描非常昂貴，
本文閱讀MySQL檔案為5.7，
下一篇繼續探索索引優化部分，
作者：hangwei
出處：http://www.cnblogs.com/hangwei/
關于作者：專注于開源平臺，分布式系統的架構設計與開發、資料庫性能調優等作業，如有問題或建議，請多多賜教！
著作權宣告：本文著作權歸作者和博客園共有，歡迎轉載，但未經作者同意必須保留此段宣告，且在文章頁面明顯位置給出原文鏈接，
如果您覺得文章對您有幫助，可以點擊文章右下角“推薦”一下，您的鼓勵是作者堅持原創和持續寫作的最大動力！
轉載請註明出處，本文鏈接：https://www.uj5u.com/shujuku/540562.html
標籤：MySQL
上一篇：MyBatis是如何初始化的？