《Mysql必讀淺談MySQL和Lucene索引的對(duì)比分析》要點(diǎn)：
本文介紹了Mysql必讀淺談MySQL和Lucene索引的對(duì)比分析，希望對(duì)您有用。如果有疑問(wèn)，可以聯(lián)系我們。

MYSQL數(shù)據(jù)庫(kù)MySQL和Lucene都可以對(duì)數(shù)據(jù)構(gòu)建索引并通過(guò)索引查詢數(shù)據(jù),一個(gè)是關(guān)系型數(shù)據(jù)庫(kù),一個(gè)是構(gòu)建搜索引擎(Solr、ElasticSearch)的核心類庫(kù).兩者的索引(index)有什么區(qū)別呢?以前寫過(guò)一篇《Solr與MySQL查詢性能對(duì)比》,只是簡(jiǎn)單的對(duì)比了下查詢性能,對(duì)于內(nèi)部原理卻沒(méi)有解釋,本文簡(jiǎn)單分析下兩者的索引區(qū)別.

MYSQL數(shù)據(jù)庫(kù)MySQL索引實(shí)現(xiàn)

MYSQL數(shù)據(jù)庫(kù)在MySQL中,索引屬于存儲(chǔ)引擎級(jí)別的概念,不同存儲(chǔ)引擎對(duì)索引的實(shí)現(xiàn)方式是不同的,本文主要討論MyISAM和InnoDB兩個(gè)存儲(chǔ)引擎的索引實(shí)現(xiàn)方式.

MYSQL數(shù)據(jù)庫(kù)MyISAM索引實(shí)現(xiàn)

MYSQL數(shù)據(jù)庫(kù)MyISAM引擎使用B+Tree作為索引結(jié)構(gòu),葉節(jié)點(diǎn)的data域存放的是數(shù)據(jù)記錄的地址.下圖是MyISAM索引的原理圖：

MYSQL數(shù)據(jù)庫(kù)

MYSQL數(shù)據(jù)庫(kù)圖1是一個(gè)MyISAM表的主索引(Primary key)示意.可以看出MyISAM的索引文件僅僅保存數(shù)據(jù)記錄的地址.在MyISAM中,主索引和輔助索引(Secondary key)在結(jié)構(gòu)上沒(méi)有任何區(qū)別,只是主索引要求key是唯一的,而輔助索引的key可以重復(fù).B+Tree的所有葉子節(jié)點(diǎn)包含所有關(guān)鍵字且是按照升序排列的.

MYSQL數(shù)據(jù)庫(kù)MyISAM表的索引和數(shù)據(jù)是分離的,索引保存在”表名.MYI”文件內(nèi),而數(shù)據(jù)保存在“表名.MYD”文件內(nèi).

MYSQL數(shù)據(jù)庫(kù)MyISAM的索引方式也叫做“非聚集”的,之所以這么稱呼是為了與InnoDB的聚集索引區(qū)分.

MYSQL數(shù)據(jù)庫(kù)InnoDB索引實(shí)現(xiàn)

MYSQL數(shù)據(jù)庫(kù)雖然InnoDB也使用B+Tree作為索引結(jié)構(gòu),但具體實(shí)現(xiàn)方式卻與MyISAM截然不同.

MYSQL數(shù)據(jù)庫(kù)第一個(gè)重大區(qū)別是InnoDB的數(shù)據(jù)文件本身就是索引文件.從上文知道,MyISAM索引文件和數(shù)據(jù)文件是分離的,索引文件僅保存數(shù)據(jù)記錄的地址.而在InnoDB中,表數(shù)據(jù)文件本身就是按B+Tree組織的一個(gè)索引結(jié)構(gòu),這棵樹的葉節(jié)點(diǎn)data域保存了完整的數(shù)據(jù)記錄.這個(gè)索引的key是數(shù)據(jù)表的主鍵,因此InnoDB表數(shù)據(jù)文件本身就是主索引.

MYSQL數(shù)據(jù)庫(kù)

MYSQL數(shù)據(jù)庫(kù)圖2是InnoDB主索引(同時(shí)也是數(shù)據(jù)文件)的示意圖,可以看到葉節(jié)點(diǎn)包含了完整的數(shù)據(jù)記錄.這種索引叫做聚集索引.因?yàn)镮nnoDB的數(shù)據(jù)文件本身要按主鍵聚集,所以InnoDB要求表必須有主鍵(MyISAM可以沒(méi)有),如果沒(méi)有顯式指定,則MySQL系統(tǒng)會(huì)自動(dòng)選擇一個(gè)可以唯一標(biāo)識(shí)數(shù)據(jù)記錄的列作為主鍵,如果不存在這種列,則MySQL自動(dòng)為InnoDB表生成一個(gè)隱含字段作為主鍵,這個(gè)字段長(zhǎng)度為6個(gè)字節(jié),類型為長(zhǎng)整形.

MYSQL數(shù)據(jù)庫(kù)第二個(gè)與MyISAM索引的不同是InnoDB的輔助索引data域存儲(chǔ)相應(yīng)記錄主鍵的值而不是地址.換句話說(shuō),InnoDB的所有輔助索引都引用主鍵作為data域.例如,圖3為定義在Col3上的一個(gè)輔助索引：

MYSQL數(shù)據(jù)庫(kù)

MYSQL數(shù)據(jù)庫(kù)這里以英文字符的ASCII碼作為比較準(zhǔn)則.聚集索引這種實(shí)現(xiàn)方式使得按主鍵的搜索十分高效,但是輔助索引搜索需要檢索兩遍索引：首先檢索輔助索引獲得主鍵,然后用主鍵到主索引中檢索獲得記錄.

MYSQL數(shù)據(jù)庫(kù)了解不同存儲(chǔ)引擎的索引實(shí)現(xiàn)方式對(duì)于正確使用和優(yōu)化索引都非常有幫助,例如知道了InnoDB的索引實(shí)現(xiàn)后,就很容易明白為什么不建議使用過(guò)長(zhǎng)的字段作為主鍵,因?yàn)樗休o助索引都引用主索引,過(guò)長(zhǎng)的主索引會(huì)令輔助索引變得過(guò)大.再例如,用非單調(diào)的字段作為主鍵在InnoDB中不是個(gè)好主意,因?yàn)镮nnoDB數(shù)據(jù)文件本身是一顆B+Tree,非單調(diào)的主鍵會(huì)造成在插入新記錄時(shí)數(shù)據(jù)文件為了維持B+Tree的特性而頻繁的分裂調(diào)整,十分低效,而使用自增字段作為主鍵則是一個(gè)很好的選擇.

MYSQL數(shù)據(jù)庫(kù)講MySQL索引的實(shí)現(xiàn)的文章很多,以上也是參考了《MySQL索引背后的數(shù)據(jù)結(jié)構(gòu)及算法原理》,現(xiàn)在來(lái)看看Lucene的索引原理.

MYSQL數(shù)據(jù)庫(kù)Lucene索引實(shí)現(xiàn)

MYSQL數(shù)據(jù)庫(kù)Lucene的索引不是B+Tree組織的,而是倒排索引,Lucene的倒排索引由Term index,Team Dictionary和Posting List組成.

MYSQL數(shù)據(jù)庫(kù)

MYSQL數(shù)據(jù)庫(kù)有倒排索引(invertedindex)就有正排索引(forwardindex),正排索引就是文檔(Document)和它的字段Fields正向?qū)?yīng)的關(guān)系：

MYSQL數(shù)據(jù)庫(kù)DocID

MYSQL數(shù)據(jù)庫(kù)name

MYSQL數(shù)據(jù)庫(kù)sex

MYSQL數(shù)據(jù)庫(kù)age

MYSQL數(shù)據(jù)庫(kù)1

MYSQL數(shù)據(jù)庫(kù)jack

MYSQL數(shù)據(jù)庫(kù)男

MYSQL數(shù)據(jù)庫(kù)18

MYSQL數(shù)據(jù)庫(kù)2

MYSQL數(shù)據(jù)庫(kù)lucy

MYSQL數(shù)據(jù)庫(kù)女

MYSQL數(shù)據(jù)庫(kù)17

MYSQL數(shù)據(jù)庫(kù)3

MYSQL數(shù)據(jù)庫(kù)peter

MYSQL數(shù)據(jù)庫(kù)男

MYSQL數(shù)據(jù)庫(kù)17

MYSQL數(shù)據(jù)庫(kù)倒排索引是字段Field和擁有這個(gè)Field的文檔對(duì)應(yīng)的關(guān)系:

MYSQL數(shù)據(jù)庫(kù)Sex字段：

MYSQL數(shù)據(jù)庫(kù)男

MYSQL數(shù)據(jù)庫(kù)[1,3]

MYSQL數(shù)據(jù)庫(kù)女

MYSQL數(shù)據(jù)庫(kù)[2]

MYSQL數(shù)據(jù)庫(kù)Age字段：

MYSQL數(shù)據(jù)庫(kù)18

MYSQL數(shù)據(jù)庫(kù)[1]

MYSQL數(shù)據(jù)庫(kù)17

MYSQL數(shù)據(jù)庫(kù)[2,3]

MYSQL數(shù)據(jù)庫(kù)Jack,lucy或者17,18這些叫做term,而[1,3]就是posting list.Posting list就是一個(gè)int型的數(shù)組,存儲(chǔ)了所有符合某個(gè)term的文檔id.那么什么是Term index和Term dictionary?

MYSQL數(shù)據(jù)庫(kù)如上,假設(shè)name字段有很多個(gè)term,比如：Carla,Sara,Elin,Ada,Patty,Kate,Selena

MYSQL數(shù)據(jù)庫(kù)如果按照這樣的順序排列,找出某個(gè)特定的term一定很慢,因?yàn)閠erm沒(méi)有排序,需要全部過(guò)濾一遍才能找出特定的term.排序之后就變成了：Ada,Carla,Elin,Kate,Patty,Sara,Selena

MYSQL數(shù)據(jù)庫(kù)這樣就可以用二分查找的方式,比全遍歷更快地找出目標(biāo)的term.如何組織這些term的方式就是 Term dictionary,意思就是term的字典.有了Term dictionary之后,就可以用比較少的比較次數(shù)和磁盤讀次數(shù)查找目標(biāo).但是磁盤的隨機(jī)讀操作仍然是非常昂貴的,所以盡量少的讀磁盤,有必要把一些數(shù)據(jù)緩存到內(nèi)存里.但是整個(gè)Term dictionary本身又太大了,無(wú)法完整地放到內(nèi)存里.于是就有了Term index.Term index有點(diǎn)像一本字典的大的章節(jié)表.比如：

MYSQL數(shù)據(jù)庫(kù)A開(kāi)頭的term ……………. Xxx頁(yè)

MYSQL數(shù)據(jù)庫(kù)C開(kāi)頭的term ……………. Xxx頁(yè)

MYSQL數(shù)據(jù)庫(kù)E開(kāi)頭的term ……………. Xxx頁(yè)

MYSQL數(shù)據(jù)庫(kù)如果所有的term都是英文字符的話,可能這個(gè)term index就真的是26個(gè)英文字符表構(gòu)成的了.但是實(shí)際的情況是,term未必都是英文字符,term可以是任意的byte數(shù)組.而且26個(gè)英文字符也未必是每一個(gè)字符都有均等的term,比如x字符開(kāi)頭的term可能一個(gè)都沒(méi)有,而s開(kāi)頭的term又特別多.實(shí)際的term index是一棵trie 樹：

MYSQL數(shù)據(jù)庫(kù)

MYSQL數(shù)據(jù)庫(kù)上圖例子是一個(gè)包含 "A", "to", "tea", "ted", "ten", "i", "in", 和 "inn" 的trie樹.這棵樹不會(huì)包含所有的term,它包含的是term的一些前綴.通過(guò)term index可以快速地定位到term dictionary的某個(gè)offset,然后從這個(gè)位置再往后順序查找.再加上一些壓縮技術(shù)(想了解更多,搜索 Lucene Finite State Transducers),Term index的尺寸可以只有所有term的尺寸的幾十分之一,使得用內(nèi)存緩存整個(gè)term index變成可能.

MYSQL數(shù)據(jù)庫(kù)整體上來(lái)說(shuō)就是這樣的效果：

MYSQL數(shù)據(jù)庫(kù)

MYSQL數(shù)據(jù)庫(kù)由Term index到Term Dictionary,再到Posting List,通過(guò)某個(gè)字段的關(guān)鍵字去查詢結(jié)果的過(guò)程就比較清楚了,通過(guò)多個(gè)關(guān)鍵字的Posting List進(jìn)行AND或者OR進(jìn)行交集或者并集的查詢也簡(jiǎn)單了.

MYSQL數(shù)據(jù)庫(kù)對(duì)比MySQL的B+Tree索引原理,可以發(fā)現(xiàn)：

MYSQL數(shù)據(jù)庫(kù)1)Lucene的Term index和Term Dictionary其實(shí)對(duì)應(yīng)的就是MySQL的B+Tree的功能,為關(guān)鍵字key提供索引.Lucene的inverted index可以比MySQL的b-tree檢索更快.

MYSQL數(shù)據(jù)庫(kù)2)Term index在內(nèi)存中是以FST(finite state transducers)的形式保存的,其特點(diǎn)是非常節(jié)省內(nèi)存.所以Lucene搜索一個(gè)關(guān)鍵字key的速度是非常快的,而MySQL的B+Tree需要讀磁盤比較.

MYSQL數(shù)據(jù)庫(kù)3)Term dictionary在磁盤上是以分block的方式保存的,一個(gè)block內(nèi)部利用公共前綴壓縮,比如都是Ab開(kāi)頭的單詞就可以把Ab省去.這樣Term dictionary可以比B-tree更節(jié)約磁盤空間.

MYSQL數(shù)據(jù)庫(kù)4)Lucene對(duì)不同的數(shù)據(jù)類型采用了不同的索引方式,上面分析是針對(duì)field為字符串的,比如針對(duì)int,有TrieIntField類型,針對(duì)經(jīng)緯度,就可以用GeoHash編碼.

MYSQL數(shù)據(jù)庫(kù)5)在 Mysql中給兩個(gè)字段獨(dú)立建立的索引無(wú)法聯(lián)合起來(lái)使用,必須對(duì)聯(lián)合查詢的場(chǎng)景建立復(fù)合索引,而Lucene可以任何AND或者OR組合使用索引進(jìn)行檢索.

MYSQL數(shù)據(jù)庫(kù)以上就是小編為大家?guī)?lái)的淺談MySQL和Lucene索引的對(duì)比分析的全部?jī)?nèi)容了,希望對(duì)大家有所幫助,多多支持維易PHP~

轉(zhuǎn)載請(qǐng)注明本頁(yè)網(wǎng)址：
http://www.fzlkiss.com/jiaocheng/4756.html