MySQL索引背后的數(shù)據(jù)結(jié)構(gòu)及算法原理(2)
MySQL索引背后的數(shù)據(jù)結(jié)構(gòu)及算法原理(2)MySQL索引實現(xiàn)
在MySQL中,索引屬于存儲引擎級別的概念,不同存儲引擎對索引的實現(xiàn)方式是不同的,本文主要討論MyISAM和InnoDB兩個存儲引擎的索引實現(xiàn)方式。
MyISAM索引實現(xiàn)
MyISAM引擎使用B+Tree作為索引結(jié)構(gòu),葉節(jié)點的data域存放的是數(shù)據(jù)記錄的地址。下圖是MyISAM索引的原理圖:
這里設(shè)表一共有三列,假設(shè)我們以Col1為主鍵,則圖8是一個MyISAM表的主索引(Primary key)示意。可以看出MyISAM的索引文件僅僅保存數(shù)據(jù)記錄的地址。在MyISAM中,主索引和輔助索引(Secondary key)在結(jié)構(gòu)上沒有任何區(qū)別,只是主索引要求key是唯一的,而輔助索引的key可以重復(fù)。如果我們在Col2上建立一個輔助索引,則此索引的結(jié)構(gòu)如下圖所示:
同樣也是一顆B+Tree,data域保存數(shù)據(jù)記錄的地址。因此,MyISAM中索引檢索的算法為首先按照B+Tree搜索算法搜索索引,如果指定的Key存在,則取出其data域的值,然后以data域的值為地址,讀取相應(yīng)數(shù)據(jù)記錄。
MyISAM的索引方式也叫做“非聚集”的,之所以這么稱呼是為了與InnoDB的聚集索引區(qū)分。
InnoDB索引實現(xiàn)
雖然InnoDB也使用B+Tree作為索引結(jié)構(gòu),但具體實現(xiàn)方式卻與MyISAM截然不同。
第一個重大區(qū)別是InnoDB的數(shù)據(jù)文件本身就是索引文件。從上文知道,MyISAM索引文件和數(shù)據(jù)文件是分離的,索引文件僅保存數(shù)據(jù)記錄的地址。而在InnoDB中,表數(shù)據(jù)文件本身就是按B+Tree組織的一個索引結(jié)構(gòu),這棵樹的葉節(jié)點data域保存了完整的數(shù)據(jù)記錄。這個索引的key是數(shù)據(jù)表的主鍵,因此InnoDB表數(shù)據(jù)文件本身就是主索引。
上圖是InnoDB主索引(同時也是數(shù)據(jù)文件)的示意圖,可以看到葉節(jié)點包含了完整的數(shù)據(jù)記錄。這種索引叫做聚集索引。因為InnoDB的數(shù)據(jù)文件本身要按主鍵聚集,所以InnoDB要求表必須有主鍵(MyISAM可以沒有),如果沒有顯式指定,則MySQL系統(tǒng)會自動選擇一個可以唯一標(biāo)識數(shù)據(jù)記錄的列作為主鍵,如果不存在這種列,則MySQL自動為InnoDB表生成一個隱含字段作為主鍵,這個字段長度為6個字節(jié),類型為長整形。
第二個與MyISAM索引的不同是InnoDB的輔助索引data域存儲相應(yīng)記錄主鍵的值而不是地址。換句話說,InnoDB的所有輔助索引都引用主鍵作為data域。例如,下圖為定義在Col3上的一個輔助索引:
這里以英文字符的ASCII碼作為比較準(zhǔn)則。聚集索引這種實現(xiàn)方式使得按主鍵的搜索十分高效,但是輔助索引搜索需要檢索兩遍索引:首先檢索輔助索引獲得主鍵,然后用主鍵到主索引中檢索獲得記錄。
了解不同存儲引擎的索引實現(xiàn)方式對于正確使用和優(yōu)化索引都非常有幫助,例如知道了InnoDB的索引實現(xiàn)后,就很容易明白為什么不建議使用過長的字段作為主鍵,因為所有輔助索引都引用主索引,過長的主索引會令輔助索引變得過大。再例如,用非單調(diào)的字段作為主鍵在InnoDB中不是個好主意,因為InnoDB數(shù)據(jù)文件本身是一顆B+Tree,非單調(diào)的主鍵會造成在插入新記錄時數(shù)據(jù)文件為了維持B+Tree的特性而頻繁的分裂調(diào)整,十分低效,而使用自增字段作為主鍵則是一個很好的選擇。
下一章將具體討論這些與索引有關(guān)的優(yōu)化策略。
索引使用策略及優(yōu)化
MySQL的優(yōu)化主要分為結(jié)構(gòu)優(yōu)化(Scheme optimization)和查詢優(yōu)化(Query optimization)。本章討論的高性能索引策略主要屬于結(jié)構(gòu)優(yōu)化范疇。本章的內(nèi)容完全基于上文的理論基礎(chǔ),實際上一旦理解了索引背后的機制,那么選擇高性能的策略就變成了純粹的推理,并且可以理解這些策略背后的邏輯。
示例數(shù)據(jù)庫
為了討論索引策略,需要一個數(shù)據(jù)量不算小的數(shù)據(jù)庫作為示例。本文選用MySQL官方文檔中提供的示例數(shù)據(jù)庫之一:employees。這個數(shù)據(jù)庫關(guān)系復(fù)雜度適中,且數(shù)據(jù)量較大。下圖是這個數(shù)據(jù)庫的E-R關(guān)系圖(引用自MySQL官方手冊):
MySQL官方文檔中關(guān)于此數(shù)據(jù)庫的頁面為http://dev.mysql.com/doc/employee/en/employee.html。里面詳細(xì)介紹了此數(shù)據(jù)庫,并提供了下載地址和導(dǎo)入方法,如果有興趣導(dǎo)入此數(shù)據(jù)庫到自己的MySQL可以參考文中內(nèi)容。
更多文章、技術(shù)交流、商務(wù)合作、聯(lián)系博主
微信掃碼或搜索:z360901061

微信掃一掃加我為好友
QQ號聯(lián)系: 360901061
您的支持是博主寫作最大的動力,如果您喜歡我的文章,感覺我的文章對您有幫助,請用微信掃描下面二維碼支持博主2元、5元、10元、20元等您想捐的金額吧,狠狠點擊下面給點支持吧,站長非常感激您!手機微信長按不能支付解決辦法:請將微信支付二維碼保存到相冊,切換到微信,然后點擊微信右上角掃一掃功能,選擇支付二維碼完成支付。
【本文對您有幫助就好】元
