摘要：通過增加額外的寫操作和存儲空間來維護數據庫索引，可以提高從數據庫中讀取數據的速度。數據庫索引的實現常見的數據庫索引實現有平衡樹樹樹哈希樹，樹參考，中的索引數據庫支持多種索引類型，如索引，哈希索引，全文索引等等。

數據庫索引是一種數據結構。通過增加額外的寫操作和存儲空間來維護數據庫索引，可以提高從數據庫中讀取數據的速度。通過索引，不需要搜索數據庫的每一條記錄，就可以快速地定位到特定的數據。索引可以建在在表中某一個字段或多個字段之上。總而言之：數據庫索引是一種數據結構

用于支持快速地查找到數據

若沒有索引，通常需要遍歷所有記錄才能找到相應地數據（O(N)）;而通過索引，一般只需要O(log(N))次就可以定位到數據，提高了查找效率

管理數據庫約束

索引通常還會被用于管理數據庫約束，例如UNIQUE, EXCLUSION, PRIMARY KEY 和 FOREIGN KEY。當一個索引被定義為UNIQUE時，數據庫同時創建一個隱式的約束。

聚集索引是指數據庫表行中數據的物理順序與鍵值的邏輯（索引）順序相同。一個表只能有一個聚集索引，因為一個表的物理順序只有一種情況，所以，對應的聚集索引只能有一個。如果某索引不是聚集索引，則表中的行物理順序與索引順序不匹配，與非聚集索引相比，聚集索引有著更快的檢索速度。如下圖，葉節點中直接包含了具體數據。

與聚集索引不同，非聚集索引的邏輯順序與磁盤上行的物理存儲順序不同。磁盤上的數據可以隨意分布，而通過非聚集索引，可以在邏輯上為數據排序。如下圖，葉節點沒有包含具體的數據，而是包含了一個指向具體數據的指針。

當索引通過二叉樹的形式進行描述時，我們可以這樣區分聚集與非聚集索引的區別：聚集索引的葉節點就是最終的數據節點，而非聚集索引的葉節仍然是索引節點，但它有一個指向最終數據的指針。

常見的數據庫索引實現有

平衡樹（B樹）

B+樹

Hashes（哈希）

參考B-tree wiki，B+ tree wiki

MySQL數據庫支持多種索引類型，如B+ Tree索引，哈希索引，全文索引等等。下面只分析B+ Tree索引。

MyISAM引擎使用B+Tree作為索引實現，并且所有的索引都是非聚集索引。
下圖是主鍵索引：

若在Col2上建立輔助索引，其依然是一個非聚集索引，與主鍵索引類似：

MyISAM引擎中，使用索引查找數據時，先通過索引獲取到數據的物理地址，然后通過物理地址讀取數據。

InnoDB引擎同樣使用B+Tree作為索引實現，但與MyISAM不同，在InnoDB引擎中，主鍵索引是聚集索引，而輔助索引則是非聚集索引。下圖是主鍵索引：

若在Col2上建立輔助索引，則是一個非聚集索引，葉節點的值為數據的主鍵：

在InnoDB中，通過主鍵索引，可以直接獲取到具體的數據；而通過輔助索引，在葉節點獲取到的是數據的主鍵，然后再通過主鍵索引最終獲取到數據。

在上面的介紹中，我們主要是針對一個字段建立索引，而實際上，可以建立一個基于多個字段的索引。假設某張表中有a，b，c，d四個字段。現在在a，b，c上建立索引(a,b,c)（注意: a,b,c順序不同建立的是不同的索引）。則索引首先會按a字段排序；在a字段相同的情況下按照b字段排序；在a，b字段相同的情況下按照c字段排序，以此類推。。。

當建立聯合索引時，該索引的所有最左前綴匹配可以用于優化查找。以上面建立的(a,b,c)索引為例，其所有最左前綴匹配為(a),(a,b),(a,b,c)。即涉及到(a),(a,b),(a,b,c)的查找都可以利用索引(a,b,c)，但涉及(a,c)的查找無法利用索引(a,b,c)，因為(a,c)不滿足最左前綴匹配原則。

前綴索引就是針對字段的“前特定個字符”建立索引，而非對整個字段的值建立索引。顯然，因為沒有對完整的字段值建立索引，所以這樣建立的索引更小，查詢更快。MySQL的前綴索引能有效減小索引文件的大小，提高索引的速度。但是前綴索引也有它的壞處：MySQL 不能在 ORDER BY 或 GROUP BY 中使用前綴索引，也不能把它們用作覆蓋索引(Covering Index)。
可以通過下面的預發建立前綴索引：

ALTER TABLE table_name ADD KEY(column_name(prefix_length));

覆蓋索引（covering index）指一個查詢語句的執行只需要從輔助索引中就可以得到查詢記錄，而不需要查詢聚集索引中的記錄。也可以稱之為實現了索引覆蓋。輔助索引不包含一整行的記錄，因此可以大大減少IO操作。覆蓋索引是mysql dba常用的一種SQL優化手段。

如果查詢中的列不是獨立的，則MySQL就不會使用索引。“獨立的列”是指索引列不能是表達式的一部分，也不能是函數的參數。因此應該簡化WHERE條件，始終將索引列多帶帶放在比較符號的一側

SELECT actor_id FROM sakila.actor WHERE actor_id + 1 = 5;(無法使用actor_id列的索引)
SELECT actor_id FROM sakila.actor WHERE actor_id = 4;(可以使用actor_id列的索引)

有時候需要索引很長的字符列，這會使索引變得大且慢。通常可以索引開始的部分字符，這樣可以大大節約索引空間，從而提高索引效率。但這樣也會降低索引的選擇性。索引的選擇性是指，不重復的索引值（也稱為基數）和數據的記錄總數（#T）的比值，范圍從1/#T到1之間。索引的選擇性越高則查詢效率越高。唯一索引的選擇性是1，這是最好的索引選擇性，性能也是最好的。

一般情況下某個列的前綴的選擇性也是足夠高的，足以滿足查詢性能。對于BLOB，TEXT或很長的VARCHAR類型的列，必須使用前綴索引，因為MySQL不允許索引這些列的完整長度。通常情況，我們應該盡量使前綴的“基數”接近于完整列的“基數”。

前綴索引的缺點 : MySQL無法使用前綴索引做ORDER BY和GROUP BY，也無法使用前綴索引做覆蓋掃描。

在多個列上建立獨立的單列索引大部分情況下并不能提高MySQL的查詢性能。此時應該考慮建立多列索引。

當不需要考慮排序和分組時，通常將選擇性最高的列放到索引最前列。
有時可能需要根據那些運行頻率最高的查詢來調整索引列的順序。

如果一個索引包含（或者說是覆蓋）所有需要查詢的字段的值，我們就稱為“覆蓋索引”，使用覆蓋索引能夠極大地提高性能。

MySQL可以使用同一個索引既滿足排序，又用于查找行。因此，如果可能，涉及索引時應該盡可能地同時滿足這兩種任務。只有當索引的列順序和ORDER BY子句的順序完全一致，并且索引列的排序方向（倒序或正序）都一樣時，MySQL才能使用索引來對結果排序。如果查詢需要關聯多張表，則只有當ORDER BY子句引用的字段全部為第一個表時，才能使用索引做排序。ORDER BY子句和查找型查詢的限制是一樣的：需要滿足索引的最左前綴需求；否則，MySQL都需要執行排序操作，而無法利用索引排序。

重復索引是指在相同的列上按照相同的順序創建相同類型的索引，應該避免這樣創建的重復索引，發現后也應該立即移除。MySQL允許在相同列上創建多個索引。MySQL需要多帶帶維護重復的索引，并且優化器在優化查詢的時候也需要逐個地進行考慮，這會影響性能。

冗余索引和重復索引又一些不同。如果創建了索引（A,B）,再創建索引（A）就是冗余索引，因為這只是前一個索引的前綴索引。大多數情況下，都不需要冗余索引，應該盡可能擴展已有的索引而不是創建新索引。但也有時候出于性能方面的考慮需要冗余索引，因為擴展已有的索引會導致其變得太大，從而影響其他使用該索引的查詢的性能。

若一個索引不再被使用，則應該考慮刪除。可以通過一些工具找到未使用的索引，如Percona Toolkit中的pt-index-usage