目錄
概要
MyISAM索引實作
InnoDB索引實作
總結
概要
Mysql的BTree索引使用的是B數中的B+Tree，但對于主要的兩種存儲引擎的實作方式是不同的。
MyISAM索引實作
MyISAM引擎使用B+Tree作為索引結構，葉節點的data域存放的是資料記錄的位址。下圖是MyISAM索引的原理圖：
這裡設表一共有三列，假設我們以Col1為主鍵，則上圖是一個MyISAM表的主索引（Primary key）示意。可以看出MyISAM的索引檔案僅僅儲存資料記錄的位址。在MyISAM中，主索引和輔助索引（Secondary key）在結構上沒有任何差別，隻是主索引要求key是唯一的，而輔助索引的key可以重複。如果我們在Col2上建立一個輔助索引，則此索引的結構如下圖所示：
同樣也是一顆B+Tree，data域儲存資料記錄的位址。是以，MyISAM中索引檢索的算法為首先按照B+Tree搜尋算法搜尋索引，如果指定的Key存在，則取出其data域的值，然後以data域的值為位址，讀取相應資料記錄。
MyISAM的索引方式也叫做“非聚集”的。
InnoDB索引實作
雖然InnoDB也使用B+Tree作為索引結構，但具體實作方式卻與MyISAM截然不同。
第一個重大差別是InnoDB的資料檔案本身就是索引檔案。從上文知道，MyISAM索引檔案和資料檔案是分離的，索引檔案僅儲存資料記錄的位址。而在InnoDB中，表資料檔案本身就是按B+Tree組織的一個索引結構，這棵樹的葉節點data域儲存了完整的資料記錄。這個索引的key是資料表的主鍵，是以InnoDB表資料檔案本身就是主索引。
上圖是InnoDB主索引（同時也是資料檔案）的示意圖，可以看到葉節點包含了完整的資料記錄。這種索引叫做聚集索引。因為InnoDB的資料檔案本身要按主鍵聚集，是以InnoDB要求表必須有主鍵（MyISAM可以沒有），如果沒有顯式指定，則MySQL系統會自動選擇一個可以唯一辨別資料記錄的列作為主鍵，如果不存在這種列，則MySQL自動為InnoDB表生成一個隐含字段作為主鍵，這個字段長度為6個位元組，類型為長整形。
第二個與MyISAM索引的不同是InnoDB的輔助索引data域存儲相應記錄主鍵的值而不是位址。換句話說，InnoDB的所有輔助索引都引用主鍵作為data域。例如，定義在Col3上的一個輔助索引：
這裡以英文字元的ASCII碼作為比較準則。聚集索引這種實作方式使得按主鍵的搜尋十分高效，但是輔助索引搜尋需要檢索兩遍索引：首先檢索輔助索引獲得主鍵，然後用主鍵到主索引中檢索獲得記錄。
了解不同存儲引擎的索引實作方式對于正确使用和優化索引都非常有幫助，例如知道了InnoDB的索引實作後，就很容易明白為什麼不建議使用過長的字段作為主鍵，因為所有輔助索引都引用主索引，過長的主索引會令輔助索引變得過大。再例如，用非單調的字段作為主鍵在InnoDB中不是個好主意，因為InnoDB資料檔案本身是一顆B+Tree，非單調的主鍵會造成在插入新記錄時資料檔案為了維持B+Tree的特性而頻繁的分裂調整，十分低效，而使用自增字段作為主鍵則是一個很好的選擇。
總結
MyISAM:
- B+Tree葉節點的data域存放的是資料記錄的位址
- 主索引和輔助索引（Secondary key）在結構上沒有任何差別，隻是主索引要求key是唯一的，而輔助索引的key可以重複
InnoDB:
- 其資料檔案本身就是索引檔案,書的葉子節點data域儲存了完整的資料記錄。這個索引的key是資料表的主鍵，是以InnoDB表資料檔案本身就是主索引。
- InnoDB的輔助索引data域存儲相應記錄主鍵的值而不是位址，首先檢索輔助索引獲得主鍵，然後用主鍵到主索引中檢索獲得記錄