## 什么是索引 索引是一種數據結構。 根據結構分類 * B+Tree * Hash  * 結構說明 每個磁盤塊表示一個節點，頂部的磁盤塊1分為數據域和指針域，17，35表示數據，P1，P2，P3表示指針，P1指向磁盤塊2，P2指向磁盤塊3，P3指向磁盤塊4。 根據節點分類有葉子節點，根結點，中間節點。從數據組成來看，葉子節點只有數據域，非葉子節點包含數據域，指針域。 * 查找過程（查找30） 1. 加載磁盤塊1到內存，發生一次磁盤I/O，使用二分法確定數據在P2指針的指向位置 2. 通過P2指針加載磁盤塊3到內存，重復步驟1返回P2指針。 3. 通過P2指針加載磁盤塊8，獲取數據。 ## Explain 分析sql性能，以多個字段呈現。  1. id 表示執行優先級，id值降序執行 2. select_type 查詢類型 * SIMPLE: 簡單查詢，不包含union或者自查詢 * PRIMARY: 包含子查詢的SQL語句的最外層查詢 * SUBQUERY：第一個子查詢 * UNION：UNION查詢的非第一個查詢 * DEPENDENT UNION：UNION查詢的非第一個查詢，且用到了外面查詢的字段 * UNION RESULT：UNION的結果 * DEPENDENT SUBQUERY: 子查詢依賴外層查詢的結果 * DERIVED：衍生，查詢結果被作為外查詢的數據源 3. table 表名or 衍生表  id為1的table“<derived2>“表示由id為2的表衍生而來 4. type 使用索引的方式，性能關系如下: ALL < index < range < ref < eq_ref < const * const：通過主鍵或者唯一索引等值查詢，至多返回一條數據 * eq_ref：在多表查詢時，前表索引列的每一個查詢結果，后表至多匹配到一行結果 * ref：與eq_ref類似，但是可能匹配多行 * range：對索引列的范圍查詢 * index：全索引掃描 * ALL：全表掃描 5. possible_keys 可能用到的索引 6. key 查詢中實際使用的索引 7. key_len 查詢優化器使用了索引的字節數 8. rows 查詢結果集需要掃描的數據行數（非索引行數） 9. extra * using filesort：涉及到在內存或者磁盤中進行文件排序 * using index：查詢結果用到了覆蓋索引 * using temporary：用到了臨時表 * using where： # 索引的算法和結構基礎 ## B-Tree和B+Tree 先從B-Tree和B+Tree的數據結構談起 ## B-Tree  ### 結構特點 * d為大于1的整數，稱為B-Tree的度，表示B-Tree的寬度 * h為正整數，稱為B-Tree的高度 * 每個節點由n個指針和n-1個key組成，其中d<n<2d * key和指針相互間隔，節點的兩邊是指針 ### 增刪查改 由于B-Tree結構的特性，檢索數據變得很簡單：首先在根結點根據二分法查找key，找到時返回key對應的data，否則根據指針指向的節點遞歸查找，直到找到key對應的data，或者null指針。 在節點中插入刪除key時需要維護樹結構 ## B+Tree  B+Tree是B-Tree的變種，相比B-Tree，B+Tree有以下不同： * 非葉子節點中不保存data，葉子節點不保存指針 * key數量和指針數量一致 * B+Tree應用到文件系統中之后新增了方便葉子節點順序訪問的指針 小結：以上對B-Tree和B+Tree做了簡單介紹，下一節結合存儲器的存取原理驗證為什么使用B+Tree結構 ## 為什么使用B+Tree 紅黑樹結構，B-Tree，B+Tree等結構都可以用來實現索引。 索引文件一般保存在磁盤中，相比內存存取，磁盤I/O消耗的時間大出了幾個量級，而索引的性能與磁盤I/O的次數直接相關。 ### 主存存儲原理 * 讀取 當系統需要從主存讀取數據時，通過【地址總線】將地址信號傳到主存，解析地址信號之后讀取數據并放入【數據總線】。 * 寫入 系統分別將地址信號和數據放入地址總線和數據總線，主存讀取之后寫入主存。 總主存寫入讀取數據的耗時和操作次數成正比。 ### 磁盤存取原理 檢索索引需要磁盤I/O操作，與主存不同，磁盤I/O存在機械運動耗時。 * 讀取 磁盤收到數據的邏輯地址之后， 需要花費尋址時間和旋轉時間 ### 局部性原理和磁盤預讀 磁盤讀取速度比內存讀取速度要慢得多，為了提高效率需要降低磁盤讀取的次數。通過預讀來達到這個目的。 &nbsp; 預讀指的是即使只需要一個字節，磁盤也會從該位置開始，順序讀取一定長度的數據返回。這樣做的理論依據是計算機屆的一個理論，局部性原理。 局部性原理：當一個數據被用到時，其附近的數據也通常會馬上被使用。 &nbsp; **即對于滿足局部性原理的程序，預讀可以降低磁盤I/O次數，提交I/O效率。** &nbsp; 預讀的長度一般為頁（page）的整數倍，頁的大小通常為4K。操作系統將內存，磁盤分割為大小相同的存儲塊，每個存儲塊稱為一頁，內存和磁盤以頁為單位交換數據。 ### B+Tree的性能分析 根據B+Tree的定位，檢索數據需要訪問h個節點。數據庫設計人員利用磁盤預讀原理，將每一個節點的大小設為一個頁大小，這樣每個節點只需要一次磁盤I/O即可載入。 &nbsp; B+Tree索引檢索數據時只需要h-1次的磁盤I/O（根結點常駐內存）。 &nbsp; 相比較而言，紅黑樹的高度h比B+Tree大得多，檢索數據消耗的I/O次數也就大得多，即查詢效率就越低。 &nbsp; 相比較B-Tree，B+Tree結構去掉了非葉子節點的數據域data，以便在頁單位的節點中保存更多的key，以減少I/O次數。 # MySQL的索引實現 B+Tree結構的索引在不同的存儲引擎下有不一樣的實現，分別是MyISAM下的非聚簇索引和Innodb下的聚簇索引 ## MyISAM索引實現  葉子節點的數據域data存放的是數據記錄的指針地址。 主鍵索引和輔助索引保持一致 ## InnoDB索引實現 * 主鍵索引  葉子節點的data域中保存了完整的數據行 &nbsp; * 輔助索引  葉子節點的data域中保存對應數據的主鍵 # 索引使用策略和優化 ## 參考文獻 * [MySQL索引背后的數據結構及算法原理](https://blog.codinglabs.org/articles/theory-of-mysql-index.html)