mysql索引實作
在mysql中，索引屬于存儲引擎級别的概念，不同存儲引擎對索引的實作方式是不同的，本文主要讨論myisam和innodb兩個存儲引擎的索引實作方式。
myisam索引實作
myisam引擎使用b+tree作為索引結構，葉節點的data域存放的是資料記錄的位址。下圖是myisam索引的原理圖：
圖1是一個myisam表的主索引（primary key）示意。可以看出myisam的索引檔案僅僅儲存資料記錄的位址。在myisam中，主索引和輔助索引（secondary key）在結構上沒有任何差別，隻是主索引要求key是唯一的，而輔助索引的key可以重複。b+tree的所有葉子節點包含所有關鍵字且是按照升序排列的。
myisam表的索引和資料是分離的，索引儲存在”表名.myi”檔案内，而資料儲存在“表名.myd”檔案内。
myisam的索引方式也叫做“非聚集”的，之是以這麼稱呼是為了與innodb的聚集索引區分。
innodb索引實作
雖然innodb也使用b+tree作為索引結構，但具體實作方式卻與myisam截然不同。
第一個重大差別是innodb的資料檔案本身就是索引檔案。從上文知道，myisam索引檔案和資料檔案是分離的，索引檔案僅儲存資料記錄的位址。而在innodb中，表資料檔案本身就是按b+tree組織的一個索引結構，這棵樹的葉節點data域儲存了完整的資料記錄。這個索引的key是資料表的主鍵，是以innodb表資料檔案本身就是主索引。
圖2是innodb主索引（同時也是資料檔案）的示意圖，可以看到葉節點包含了完整的資料記錄。這種索引叫做聚集索引。因為innodb的資料檔案本身要按主鍵聚集，是以innodb要求表必須有主鍵（myisam可以沒有），如果沒有顯式指定，則mysql系統會自動選擇一個可以唯一辨別資料記錄的列作為主鍵，如果不存在這種列，則mysql自動為innodb表生成一個隐含字段作為主鍵，這個字段長度為6個位元組，類型為長整形。
第二個與myisam索引的不同是innodb的輔助索引data域存儲相應記錄主鍵的值而不是位址。換句話說，innodb的所有輔助索引都引用主鍵作為data域。例如，圖3為定義在col3上的一個輔助索引：
這裡以英文字元的ascii碼作為比較準則。聚集索引這種實作方式使得按主鍵的搜尋十分高效，但是輔助索引搜尋需要檢索兩遍索引：首先檢索輔助索引獲得主鍵，然後用主鍵到主索引中檢索獲得記錄。
了解不同存儲引擎的索引實作方式對于正确使用和優化索引都非常有幫助，例如知道了innodb的索引實作後，就很容易明白為什麼不建議使用過長的字段作為主鍵，因為所有輔助索引都引用主索引，過長的主索引會令輔助索引變得過大。再例如，用非單調的字段作為主鍵在innodb中不是個好主意，因為innodb資料檔案本身是一顆b+tree，非單調的主鍵會造成在插入新記錄時資料檔案為了維持b+tree的特性而頻繁的分裂調整，十分低效，而使用自增字段作為主鍵則是一個很好的選擇。
講mysql索引的實作的文章很多，以上也是參考了《mysql索引背後的資料結構及算法原理》，現在來看看lucene的索引原理。
lucene索引實作
lucene的索引不是b+tree組織的，而是反向索引，lucene的反向索引由term index，team dictionary和posting list組成。
有反向索引（invertedindex）就有正排索引（forwardindex），正排索引就是文檔（document）和它的字段fields正向對應的關系：
docid
name
sex
age
1
jack
男
18
2
lucy
女
17
3
peter
反向索引是字段field和擁有這個field的文檔對應的關系:
sex字段：
[1,3]
[2]
age字段：
[1]
[2，3]
jack，lucy或者17,18這些叫做term，而[1,3]就是posting list。posting list就是一個int型的數組，存儲了所有符合某個term的文檔id。那麼什麼是term index和term dictionary？
如上，假設name字段有很多個term，比如：carla,sara,elin,ada,patty,kate,selena
如果按照這樣的順序排列，找出某個特定的term一定很慢，因為term沒有排序，需要全部過濾一遍才能找出特定的term。排序之後就變成了：ada,carla,elin,kate,patty,sara,selena
這樣就可以用二分查找的方式，比全周遊更快地找出目标的term。如何組織這些term的方式就是 term dictionary，意思就是term的字典。有了term dictionary之後，就可以用比較少的比較次數和磁盤讀次數查找目标。但是磁盤的随機讀操作仍然是非常昂貴的，是以盡量少的讀磁盤，有必要把一些資料緩存到記憶體裡。但是整個term dictionary本身又太大了，無法完整地放到記憶體裡。于是就有了term index。term index有點像一本字典的大的章節表。比如：
a開頭的term ……………. xxx頁
c開頭的term ……………. xxx頁
e開頭的term ……………. xxx頁
如果所有的term都是英文字元的話，可能這個term index就真的是26個英文字元表構成的了。但是實際的情況是，term未必都是英文字元，term可以是任意的byte數組。而且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，然後從這個位置再往後順序查找。再加上一些壓縮技術（想了解更多，搜尋 lucene finite state transducers），term index的尺寸可以隻有所有term的尺寸的幾十分之一，使得用記憶體緩存整個term index變成可能。整體上來說就是這樣的效果:
由term index到term dictionary，再到posting list，通過某個字段的關鍵字去查詢結果的過程就比較清楚了，通過多個關鍵字的posting list進行and或者or進行交集或者并集的查詢也簡單了。
對比mysql的b+tree索引原理，可以發現：
1）lucene的term index和term dictionary其實對應的就是mysql的b+tree的功能，為關鍵字key提供索引。lucene的inverted index可以比mysql的b-tree檢索更快。
2）term index在記憶體中是以fst（finite state transducers）的形式儲存的，其特點是非常節省記憶體。是以lucene搜尋一個關鍵字key的速度是非常快的，而mysql的b+tree需要讀磁盤比較。
3）term dictionary在磁盤上是以分block的方式儲存的，一個block内部利用公共字首壓縮，比如都是ab開頭的單詞就可以把ab省去。這樣term dictionary可以比b-tree更節約磁盤空間。
4）lucene對不同的資料類型采用了不同的索引方式，上面分析是針對field為字元串的，比如針對int，有trieintfield類型，針對經緯度，就可以用geohash編碼。
5）在 mysql中給兩個字段獨立建立的索引無法聯合起來使用，必須對聯合查詢的場景建立複合索引，而lucene可以任何and或者or組合使用索引進行檢索。
參考：
http://stackoverflow.com/questions/4628571/solr-date-field-tdate-vs-date
http://lucene.apache.org/core/
本文版權歸作者和部落格園共有，歡迎轉載，但未經作者同意必須保留此段聲明，且在文章頁面明顯位置給出原文連接配接，否則保留追究法律責任的權利。
http://www.cnblogs.com/luxiaoxun/p/5452502.html