轉(zhuǎn)載地址：https://www.cnblogs.com/luxiaoxun/p/5452502.html
MySQL和Lucene都可以對(duì)數(shù)據(jù)構(gòu)建索引并通過索引查詢數(shù)據(jù)檩淋，一個(gè)是關(guān)系型數(shù)據(jù)庫锈拨，一個(gè)是構(gòu)建搜索引擎（Solr、ElasticSearch）的核心類庫。兩者的索引（index）有什么區(qū)別呢脆烟？以前寫過一篇《Solr與MySQL查詢性能對(duì)比》呐芥，只是簡(jiǎn)單的對(duì)比了下查詢性能，對(duì)于內(nèi)部原理卻沒有解釋圈膏，本文簡(jiǎn)單分析下兩者的索引區(qū)別。
MySQL索引實(shí)現(xiàn)
在MySQL中篙骡，索引屬于存儲(chǔ)引擎級(jí)別的概念稽坤，不同存儲(chǔ)引擎對(duì)索引的實(shí)現(xiàn)方式是不同的，本文主要討論MyISAM和InnoDB兩個(gè)存儲(chǔ)引擎的索引實(shí)現(xiàn)方式糯俗。
MyISAM索引實(shí)現(xiàn)
MyISAM引擎使用B+Tree作為索引結(jié)構(gòu)尿褪，葉節(jié)點(diǎn)的data域存放的是數(shù)據(jù)記錄的地址。下圖是MyISAM索引的原理圖：
圖1是一個(gè)MyISAM表的主索引（Primary key）示意得湘≌攘幔可以看出MyISAM的索引文件僅僅保存數(shù)據(jù)記錄的地址。在MyISAM中淘正，主索引和輔助索引（Secondary key）在結(jié)構(gòu)上沒有任何區(qū)別摆马，只是主索引要求key是唯一的，而輔助索引的key可以重復(fù)鸿吆。B+Tree的所有葉子節(jié)點(diǎn)包含所有關(guān)鍵字且是按照升序排列的囤采。
MyISAM表的索引和數(shù)據(jù)是分離的，索引保存在”表名.MYI”文件內(nèi)惩淳，而數(shù)據(jù)保存在“表名.MYD”文件內(nèi)斑唬。
MyISAM的索引方式也叫做“非聚集”的，之所以這么稱呼是為了與InnoDB的聚集索引區(qū)分黎泣。
InnoDB索引實(shí)現(xiàn)
雖然InnoDB也使用B+Tree作為索引結(jié)構(gòu)恕刘，但具體實(shí)現(xiàn)方式卻與MyISAM截然不同。
第一個(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ù)文件本身就是主索引娘侍。
圖2是InnoDB主索引（同時(shí)也是數(shù)據(jù)文件）的示意圖着降，可以看到葉節(jié)點(diǎn)包含了完整的數(shù)據(jù)記錄差油。這種索引叫做聚集索引。因?yàn)镮nnoDB的數(shù)據(jù)文件本身要按主鍵聚集，所以InnoDB要求表必須有主鍵（MyISAM可以沒有）蓄喇，如果沒有顯式指定发侵，則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)整形钱骂。
第二個(gè)與MyISAM索引的不同是InnoDB的輔助索引data域存儲(chǔ)相應(yīng)記錄主鍵的值而不是地址叔锐。換句話說，InnoDB的所有輔助索引都引用主鍵作為data域见秽。例如掌腰，圖3為定義在Col3上的一個(gè)輔助索引：
這里以英文字符的ASCII碼作為比較準(zhǔn)則。聚集索引這種實(shí)現(xiàn)方式使得按主鍵的搜索十分高效张吉，但是輔助索引搜索需要檢索兩遍索引：首先檢索輔助索引獲得主鍵，然后用主鍵到主索引中檢索獲得記錄催植。
了解不同存儲(chǔ)引擎的索引實(shí)現(xiàn)方式對(duì)于正確使用和優(yōu)化索引都非常有幫助肮蛹，例如知道了InnoDB的索引實(shí)現(xiàn)后，就很容易明白為什么不建議使用過長(zhǎng)的字段作為主鍵创南，因?yàn)樗休o助索引都引用主索引伦忠，過長(zhǎng)的主索引會(huì)令輔助索引變得過大。再例如稿辙，用非單調(diào)的字段作為主鍵在InnoDB中不是個(gè)好主意昆码，因?yàn)镮nnoDB數(shù)據(jù)文件本身是一顆B+Tree，非單調(diào)的主鍵會(huì)造成在插入新記錄時(shí)數(shù)據(jù)文件為了維持B+Tree的特性而頻繁的分裂調(diào)整邻储，十分低效赋咽，而使用自增字段作為主鍵則是一個(gè)很好的選擇。
講MySQL索引的實(shí)現(xiàn)的文章很多吨娜，以上也是參考了《MySQL索引背后的數(shù)據(jù)結(jié)構(gòu)及算法原理》脓匿，現(xiàn)在來看看Lucene的索引原理。
Lucene索引實(shí)現(xiàn)
Lucene的索引不是B+Tree組織的宦赠，而是倒排索引陪毡，Lucene的倒排索引由Term index，Team Dictionary和Posting List組成勾扭。
有倒排索引（invertedindex）就有正排索引（forwardindex）毡琉，正排索引就是文檔（Document）和它的字段Fields正向?qū)?yīng)的關(guān)系：
DocIDnamesexage
1jack男18
2lucy女17
3peter男17
倒排索引是字段Field和擁有這個(gè)Field的文檔對(duì)應(yīng)的關(guān)系:
Sex字段：
男[1,3]
女[2]
Age字段：
18[1]
17[2，3]
Jack妙色，lucy或者17,18這些叫做term桅滋，而[1,3]就是posting list。Posting list就是一個(gè)int型的數(shù)組身辨，存儲(chǔ)了所有符合某個(gè)term的文檔id虱歪。那么什么是Term index和Term dictionary蜂绎？
如上，假設(shè)name字段有很多個(gè)term笋鄙，比如：Carla,Sara,Elin,Ada,Patty,Kate,Selena
如果按照這樣的順序排列师枣，找出某個(gè)特定的term一定很慢，因?yàn)閠erm沒有排序萧落，需要全部過濾一遍才能找出特定的term践美。排序之后就變成了：Ada,Carla,Elin,Kate,Patty,Sara,Selena
這樣就可以用二分查找的方式，比全遍歷更快地找出目標(biāo)的term找岖。如何組織這些term的方式就是 Term dictionary陨倡，意思就是term的字典。有了Term dictionary之后许布，就可以用比較少的比較次數(shù)和磁盤讀次數(shù)查找目標(biāo)兴革。但是磁盤的隨機(jī)讀操作仍然是非常昂貴的，所以盡量少的讀磁盤蜜唾，有必要把一些數(shù)據(jù)緩存到內(nèi)存里杂曲。但是整個(gè)Term dictionary本身又太大了，無法完整地放到內(nèi)存里袁余。于是就有了Term index擎勘。Term index有點(diǎn)像一本字典的大的章節(jié)表。比如：
A開頭的term ……………. Xxx頁
C開頭的term ……………. Xxx頁
E開頭的term ……………. Xxx頁
如果所有的term都是英文字符的話颖榜，可能這個(gè)term index就真的是26個(gè)英文字符表構(gòu)成的了棚饵。但是實(shí)際的情況是，term未必都是英文字符掩完，term可以是任意的byte數(shù)組噪漾。而且26個(gè)英文字符也未必是每一個(gè)字符都有均等的term，比如x字符開頭的term可能一個(gè)都沒有且蓬，而s開頭的term又特別多怪与。實(shí)際的term index是一棵trie 樹：
上圖例子是一個(gè)包含 "A", "to", "tea", "ted", "ten", "i", "in", 和 "inn" 的trie樹。這棵樹不會(huì)包含所有的term缅疟，它包含的是term的一些前綴分别。通過term index可以快速地定位到term dictionary的某個(gè)offset，然后從這個(gè)位置再往后順序查找存淫。再加上一些壓縮技術(shù)（想了解更多耘斩，搜索 Lucene Finite State Transducers），Term index的尺寸可以只有所有term的尺寸的幾十分之一桅咆，使得用內(nèi)存緩存整個(gè)term index變成可能括授。整體上來說就是這樣的效果:
由Term index到Term Dictionary，再到Posting List，通過某個(gè)字段的關(guān)鍵字去查詢結(jié)果的過程就比較清楚了荚虚，通過多個(gè)關(guān)鍵字的Posting List進(jìn)行AND或者OR進(jìn)行交集或者并集的查詢也簡(jiǎn)單了薛夜。
對(duì)比MySQL的B+Tree索引原理，可以發(fā)現(xiàn)：
1）Lucene的Term index和Term Dictionary其實(shí)對(duì)應(yīng)的就是MySQL的B+Tree的功能版述，為關(guān)鍵字key提供索引梯澜。Lucene的inverted index可以比MySQL的b-tree檢索更快。
2）Term index在內(nèi)存中是以FST（finite state transducers）的形式保存的渴析，其特點(diǎn)是非常節(jié)省內(nèi)存晚伙。所以Lucene搜索一個(gè)關(guān)鍵字key的速度是非常快的俭茧，而MySQL的B+Tree需要讀磁盤比較咆疗。
3）Term dictionary在磁盤上是以分block的方式保存的，一個(gè)block內(nèi)部利用公共前綴壓縮母债，比如都是Ab開頭的單詞就可以把Ab省去午磁。這樣Term dictionary可以比B-tree更節(jié)約磁盤空間。
4）Lucene對(duì)不同的數(shù)據(jù)類型采用了不同的索引方式毡们，上面分析是針對(duì)field為字符串的迅皇，比如針對(duì)int，有TrieIntField類型漏隐，針對(duì)經(jīng)緯度，就可以用GeoHash編碼奴迅。
5）在 Mysql中給兩個(gè)字段獨(dú)立建立的索引無法聯(lián)合起來使用青责，必須對(duì)聯(lián)合查詢的場(chǎng)景建立復(fù)合索引，而Lucene可以任何AND或者OR組合使用索引進(jìn)行檢索取具。
參考：
《MySQL索引背后的數(shù)據(jù)結(jié)構(gòu)及算法原理》:?http://blog.codinglabs.org/articles/theory-of-mysql-index.html
http://stackoverflow.com/questions/4628571/solr-date-field-tdate-vs-date
http://lucene.apache.org/core/
