MySQL索引背后的數(shù)據(jù)結(jié)構(gòu)及算法原理
MyISAM索引實(shí)現(xiàn)
InnoDB索引實(shí)現(xiàn)
雖然InnoDB也使用B+Tree作為索引結(jié)構(gòu)箱靴，但具體實(shí)現(xiàn)方式卻與MyISAM截然不同腺逛。
第一個重大區(qū)別是InnoDB的數(shù)據(jù)文件本身就是索引文件。從上文知道衡怀，MyISAM索引文件和數(shù)據(jù)文件是分離的棍矛，索引文件僅保存數(shù)據(jù)記錄的地址。而在InnoDB中抛杨，表數(shù)據(jù)文件本身就是按B+Tree組織的一個索引結(jié)構(gòu)够委，這棵樹的葉節(jié)點(diǎn)data域保存了完整的數(shù)據(jù)記錄。這個索引的key是數(shù)據(jù)表的主鍵蝶桶，因此InnoDB表數(shù)據(jù)文件本身就是主索引慨绳。
圖10
圖10是InnoDB主索引（同時也是數(shù)據(jù)文件）的示意圖，可以看到葉節(jié)點(diǎn)包含了完整的數(shù)據(jù)記錄真竖。這種索引叫做聚集索引脐雪。因?yàn)镮nnoDB的數(shù)據(jù)文件本身要按主鍵聚集，所以InnoDB要求表必須有主鍵（MyISAM可以沒有）恢共，如果沒有顯式指定战秋，則MySQL系統(tǒng)會自動選擇一個可以唯一標(biāo)識數(shù)據(jù)記錄的列作為主鍵，如果不存在這種列讨韭，則MySQL自動為InnoDB表生成一個隱含字段作為主鍵脂信，這個字段長度為6個字節(jié)，類型為長整形透硝。
第二個與MyISAM索引的不同是InnoDB的輔助索引data域存儲相應(yīng)記錄主鍵的值而不是地址狰闪。換句話說，InnoDB的所有輔助索引都引用主鍵作為data域濒生。例如埋泵，圖11為定義在Col3上的一個輔助索引：
圖11
這里以英文字符的ASCII碼作為比較準(zhǔn)則。聚集索引這種實(shí)現(xiàn)方式使得按主鍵的搜索十分高效，但是輔助索引搜索需要檢索兩遍索引：首先檢索輔助索引獲得主鍵丽声，然后用主鍵到主索引中檢索獲得記錄礁蔗。
了解不同存儲引擎的索引實(shí)現(xiàn)方式對于正確使用和優(yōu)化索引都非常有幫助，例如知道了InnoDB的索引實(shí)現(xiàn)后雁社，就很容易明白為什么不建議使用過長的字段作為主鍵浴井，因?yàn)樗休o助索引都引用主索引，過長的主索引會令輔助索引變得過大霉撵。再例如磺浙，用非單調(diào)的字段作為主鍵在InnoDB中不是個好主意，因?yàn)镮nnoDB數(shù)據(jù)文件本身是一顆B+Tree喊巍，非單調(diào)的主鍵會造成在插入新記錄時數(shù)據(jù)文件為了維持B+Tree的特性而頻繁的分裂調(diào)整屠缭，十分低效，而使用自增字段作為主鍵則是一個很好的選擇崭参。
B-Tree
