MySQL索引實現

索引（Index）是幫助資料庫高效獲取數據的數據結構。

左邊是數據表，一共有兩列七條記錄，最左邊的是數據記錄的物理地址（注意邏輯上相鄰的記錄在磁碟上也並不是一定物理相鄰的）。為了加快Col2的查找，可以維護一個右邊所示的二叉查找樹，每個節點分別包含索引鍵值和一個指向對應數據記錄物理地址的指針，這樣就可以運用二叉查找在O(log2n)的複雜度內獲取到相應數據。

MyISAM和InnoDB兩個存儲引擎的索引實現方式不同，InnoDB索引如下圖所示：

MyISAM索引文件和數據文件是分離的，索引文件僅保存數據記錄的地址。

InnoDB的數據文件本身就是索引文件，即按B+Tree組織的索引結構，這棵樹的key是主鍵，葉子節點存放完整的數據記錄。在上圖中，淺綠色的是主鍵值。

上圖的索引也叫聚集索引，其特點是只能有一個，存儲的物理順序和鍵值的邏輯順序相同，聚集索引的葉節點就是最終的數據節點。

MyISAM和InnoDB第二個不同點是關於輔助索引（非主鍵索引），InnoDB的輔助索引data存放記錄的主鍵值，而不是地址。所以使用輔助索引需要檢索兩次索引：首先檢索輔助索引獲得主鍵，然後用主鍵到主索引中檢索獲得記錄。

上圖的輔助索引也是非聚集索引，其特點是可以有多個，存儲記錄在物理上不連續，非聚集索引的葉節仍然是索引節點，存放著主鍵值。

了解了InnoDB索引的實現，就能理解為什麼不提倡主鍵使用過長的欄位，因為這樣會導致輔助索引過大。還有，為什麼主鍵要用自增值，否則會因為維持B+Tree的特性有較大的開銷。

參考資料：CodingLabs - MySQL索引背後的數據結構及演算法原理

推薦閱讀：