MySQL和Lucene(Elasticsearch)索引對比分析

點擊上方藍(lán)色字體，選擇“設(shè)為星標(biāo)”

回復(fù)”資源“獲取更多資源

大數(shù)據(jù)技術(shù)與架構(gòu)

點擊右側(cè)關(guān)注，大數(shù)據(jù)開發(fā)領(lǐng)域最強公眾號！

大數(shù)據(jù)真好玩

點擊右側(cè)關(guān)注，大數(shù)據(jù)真好玩！

本文是來自略速互聯(lián)網(wǎng)筆記的分享。

你可以在這里查看原文：http://www.lvesu.com/?uri=/blog/main/cms-611.html

前言

相比于大多數(shù)人熟悉的 MySQL 數(shù)據(jù)庫的索引，Elasticsearch 的索引機制是完全不同于 MySQL 的 B+Tree 結(jié)構(gòu)。索引會被壓縮放入內(nèi)存用于加速搜索過程，這一點在效率上是完爆 MySQL 數(shù)據(jù)庫的。但是 Elasticsearch 會對全部 text 字段進行索引，必然會消耗巨大的內(nèi)存，為此 Elasticsearch 針對索引進行了深度的優(yōu)化。在保證執(zhí)行效率的同時，盡量縮減內(nèi)存空間的占用。這篇文章就深度解析了 Elasticsearch 索引原理，揭開搜索的神秘面紗。

MySQL索引實現(xiàn)

在MySQL中，索引屬于存儲引擎級別的概念，不同存儲引擎對索引的實現(xiàn)方式是不同的，本文主要討論MyISAM和InnoDB兩個存儲引擎的索引實現(xiàn)方式。

MyISAM索引實現(xiàn)

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

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

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

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ù)文件本身就是主索引。

圖2是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域。例如，圖3為定義在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)整，十分低效，而使用自增字段作為主鍵則是一個很好的選擇。

Lucene索引實現(xiàn)

Lucene的索引不是B+Tree組織的，而是倒排索引，Lucene的倒排索引由Term index，Team Dictionary和Posting List組成。

有倒排索引（invertedindex）就有正排索引（forwardindex），正排索引就是文檔（Document）和它的字段Fields正向?qū)?yīng)的關(guān)系：

DocID	name	sex	age
1	jack	男	18
2	lucy	女	17
3	peter	男	17

倒排索引是字段Field和擁有這個Field的文檔對應(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就是一個int型的數(shù)組，存儲了所有符合某個term的文檔id。那么什么是Term index和Term dictionary？

如上，假設(shè)name字段有很多個term，比如：Carla,Sara,Elin,Ada,Patty,Kate,Selena

如果按照這樣的順序排列，找出某個特定的term一定很慢，因為term沒有排序，需要全部過濾一遍才能找出特定的term。排序之后就變成了：Ada,Carla,Elin,Kate,Patty,Sara,Selena

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

A開頭的term ……………. Xxx頁

C開頭的term ……………. Xxx頁

E開頭的term ……………. Xxx頁

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

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

由Term index到Term Dictionary，再到Posting List，通過某個字段的關(guān)鍵字去查詢結(jié)果的過程就比較清楚了，通過多個關(guān)鍵字的Posting List進行AND或者OR進行交集或者并集的查詢也簡單了。

對比MySQL的B+Tree索引原理，可以發(fā)現(xiàn)：

1）Lucene的Term index和Term Dictionary其實對應(yīng)的就是MySQL的B+Tree的功能，為關(guān)鍵字key提供索引。Lucene的inverted index可以比MySQL的b-tree檢索更快。

2）Term index在內(nèi)存中是以FST（finite state transducers）的形式保存的，其特點是非常節(jié)省內(nèi)存。所以Lucene搜索一個關(guān)鍵字key的速度是非常快的，而MySQL的B+Tree需要讀磁盤比較。

3）Term dictionary在磁盤上是以分block的方式保存的，一個block內(nèi)部利用公共前綴壓縮，比如都是Ab開頭的單詞就可以把Ab省去。這樣Term dictionary可以比B-tree更節(jié)約磁盤空間。

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

5）在 Mysql中給兩個字段獨立建立的索引無法聯(lián)合起來使用，必須對聯(lián)合查詢的場景建立復(fù)合索引，而Lucene可以任何AND或者OR組合使用索引進行檢索。

版權(quán)聲明：

本文為大數(shù)據(jù)技術(shù)與架構(gòu)整理，原作者獨家授權(quán)。未經(jīng)原作者允許轉(zhuǎn)載追究侵權(quán)責(zé)任。

編輯｜冷眼丶

微信公眾號｜import_bigdata

歡迎點贊+收藏+轉(zhuǎn)發(fā)朋友圈素質(zhì)三連

文章不錯？點個【在看】吧！??