10分鐘了解Mysql索引

一、索引介紹

索引是什麼

官方介紹索引是幫助MySQL高效擷取資料的資料結構。更通俗的說，資料庫索引好比是一本書前面的目錄，能加快資料庫的查詢速度。

一般來說索引本身也很大，不可能全部存儲在記憶體中，是以索引往往是存儲在磁盤上的檔案中的（可能存儲在單獨的索引檔案中，也可能和資料一起存儲在資料檔案中）。

我們通常所說的索引，包括聚集索引、覆寫索引、組合索引、字首索引、唯一索引等，沒有特别說明，預設都是使用B+樹結構組織（多路搜尋樹，并不一定是二叉的）的索引。

索引的優勢和劣勢

優勢：可以提高資料檢索的效率，降低資料庫的IO成本，類似于書的目錄。

通過索引列對資料進行排序，降低資料排序的成本，降低了CPU的消耗。

被索引的列會自動進行排序，包括【單列索引】和【組合索引】，隻是組合索引的排序要複雜一些。

如果按照索引列的順序進行排序，對應order by語句來說，效率就會提高很多。

劣勢：索引會占據磁盤空間

索引雖然會提高查詢效率，但是會降低更新表的效率。比如每次對表進行增删改操作，MySQL不僅要儲存資料，還有儲存或者更新對應的索引檔案。

二、索引類型

主鍵索引：索引列中的值必須是唯一的，不允許有空值。

普通索引：MySQL中基本索引類型，沒有什麼限制，允許在定義索引的列中插入重複值和空值。

唯一索引：索引列中的值必須是唯一的，但是允許為空值。

全文索引：隻能在文本類型CHAR,VARCHAR,TEXT類型字段上建立全文索引。字段長度比較大時，如果建立普通索引，在進行like模糊查詢時效率比較低，這時可以建立全文索引。 MyISAM和InnoDB中都可以使用全文索引。

空間索引：MySQL在5.7之後的版本支援了空間索引，而且支援OpenGIS幾何資料模型。MySQL在空間索引這方面遵循OpenGIS幾何資料模型規則。

字首索引：在文本類型如CHAR,VARCHAR,TEXT類列上建立索引時，可以指定索引列的長度，但是數值類型不能指定。

其他（按照索引列數量分類）單列索引、組合索引

組合索引的使用，需要遵循最左字首比對原則（最左比對原則）。一般情況下在條件允許的情況下使用組合索引替代多個單列索引使用。

索引的資料結構

三、Hash表

Hash表，在Java中的HashMap，TreeMap就是Hash表結構，以鍵值對的方式存儲資料。我們使用Hash表存儲表資料Key可以存儲索引列，Value可以存儲行記錄或者行磁盤位址。Hash表在等值查詢時效率很高，時間複雜度為O(1)；但是不支援範圍快速查找，範圍查找時還是隻能通過掃描全表方式。

顯然這種并不适合作為經常需要查找和範圍查找的資料庫索引使用。

四、二叉查找樹

二叉樹，我想大家都會在心裡有個圖。

二叉樹特點：每個節點最多有2個分叉，左子樹和右子樹資料順序左小右大。

這個特點就是為了保證每次查找都可以這折半而減少IO次數，但是二叉樹就很考驗第一個根節點的取值，因為很容易在這個特點下出現我們并發想發生的情況“樹不分叉了”，這就很難受很不穩定。

顯然這種情況不穩定的我們再選擇設計上必然會避免這種情況的

平衡二叉樹

平衡二叉樹是采用二分法思維，平衡二叉查找樹除了具備二叉樹的特點，最主要的特征是樹的左右兩個子樹的層級最多相差1。在插入删除資料時通過左旋/右旋操作保持二叉樹的平衡，不會出現左子樹很高、右子樹很矮的情況。

使用平衡二叉查找樹查詢的性能接近于二分查找法，時間複雜度是 O(log2n)。查詢id=6，隻需要兩次IO。

就這個特點來看，可能各位會覺得這就很好，可以達到二叉樹的理想的情況了。然而依然存在一些問題：

時間複雜度和樹高相關。樹有多高就需要檢索多少次，每個節點的讀取，都對應一次磁盤 IO 操作。樹的高度就等于每次查詢資料時磁盤 IO 操作的次數。磁盤每次尋道時間為10ms，在表資料量大時，查詢性能就會很差。（1百萬的資料量，log2n約等于20次磁盤IO，時間20*10=0.2s）

平衡二叉樹不支援範圍查詢快速查找，範圍查詢時需要從根節點多次周遊，查詢效率不高。