索引

index，是存儲引擎用于快速找到數據的一種數據結構。

MySQL默認使用InnoDB存儲引擎，該存儲引擎是最重要，使用最廣泛的，除非有非常特別的原因需要使用其他存儲引擎，否則優先考慮InnoDB。

索引優點：

• 減少服務器需要掃描的數據量
• 幫助服務器避免排序和臨時表
• 索引可以將隨機I/O變為順序I/O，提高查詢性能

缺點：

• 從空間角度考慮，建立索引需要占用物理空間
• 從時間角度考慮，創建和維護索引都需要花費時間，例如對數據進行增刪改時就需要維護索引。

因此在不需要頻繁的增刪改但需要頻繁查的表中創建索引是更好的選擇。

我們建立索引就類似于建議一個圖中黃色的一個索引表，通過author字段快速定位，然后找到需要的數據，這只是一個例子方便我們理解，不是真正的索引運行。

常見索引類型

• 哈希索引：基于哈希表實現，查找非常快。但不支持范圍查找和排序操作，也不支持部分索引列的查找，只支持等值比較的查詢。如果哈希沖突很多的話，索引的維護代價會很高。因此，哈希索引只適用于某些特定場合。在InnoDB中，支持的哈希索引是自適應的，不能人為創建。

哈希索引不支持范圍查找的原因：哈希索引只包含哈希值和行指針，通過找哈希值通過行指針來找到要查找的數據，存儲時輸入的數據通過哈希函數映射出一個哈希值，但是哈希值是無序的，就像1，2映射出的哈希值就可能是5678和1234，因此哈希索引每查詢一個就要全盤掃描來尋找下一個要查詢的哈希值，因此哈希索引不支持范圍查詢。

哈希索引不支持排序操作的原因：與不支持范圍查找的原因相同，因為每行數據的哈希值不含有任何順序特性，即使原始字段值是按照某種順序排列的，經過哈希函數處理后，這些值在哈希索引的存儲順序也是完全被打亂的。所以在對某一列進行排序時哈希索引不能提供任何幫助，因為它的結構中沒有保留字段值的順序信息。

• 全文索引：用于全文搜索的索引類型（倒排索引），可以執行關鍵字搜索。全文索引有很多限制，例如當數據量很大，內存無法裝載全部索引時，搜索速度會非常慢。同時全文索引的維護成本也很大。MyISAM支持全文索引，InnoDB從1.2版本（MySQL5.6）開始支持全文索引。
• B+樹索引：B+樹索引就是傳統意義上的索引，時目前關系型數據庫中查找最為常見和最為有效的索引。B+樹索引能夠加快訪問數據的速度，因為存儲引擎不再需要進行全表掃描來獲取需要的數據。B+樹索引是順序組織存儲的，所以很適合查找范圍數據，查到范圍中的首個數據后就可以一直查找到范圍中最后一個數據，不需要全表掃描。B+樹索引分為聚簇索引（主鍵索引）和非聚簇索引（二級索引）。

B+樹

主要闡述一下常見的搜尋方法和B+樹怎么發展出來的

二分查找法

從5，10，19，21，31，37，42，48，50，55中查找48，使用二分查找法只需3次。如果順序查找需要8次。

二叉搜索樹和平衡二叉樹

二叉搜索樹，左子節點小于父節點的值，右子節點大于父節點的值。如果我們需要查找8，需要3次，而順序查找需要6次。

同樣是二叉搜索樹，下圖的情況查找效率會很低，從而引出平衡二叉樹（AVL樹），平衡二叉樹要求任何節點的子樹高度最大差為1。平衡性確保查找的數獨可以很快，避免了下圖二叉搜索樹的極端情況，即樹退化成鏈表

B樹和B+樹

平衡二叉樹隨著節點的增加，樹的高度會越來越高，會增加磁盤的I/O次數，影響查詢效率，從而引出了B樹，B樹不限制一個節點只能由2個子節點，從而降低樹的高度。

B樹可以將節點的大小優化為磁盤塊的大小，每次讀取可以有效加載多個節點，B樹常用于數據庫等需要高效訪問磁盤的場景。

B+樹是對B樹的升級，B+樹只有葉子節點存數據，非葉子節點只存索引。葉子節點包含所有索引，葉子節點構成一個有序鏈表，范圍查找更快。由于非葉子節點只存索引，B+樹比B樹的非葉子節點可以存更多索引，高度更低，磁盤I/O次數更少。

B+樹范圍搜索更快的原因：

由兩張圖我們可以看出B+樹的葉子節點構成了一個有序鏈表，而B樹則沒有組成一個有序鏈表，如果要查1—10條數據，B+樹找到第1條數據之后就可以沿著鏈表一直找到第10條，但B樹找到第1條數據后可以找到第2條但是第3條記錄就需要重新掃描去找，因此B+樹的范圍索引更快。