摘要：介紹如何優(yōu)化數(shù)值類范圍查詢。查詢過程在中查詢是基于。在中為了查詢的這樣一個(gè)條件，會(huì)建立基于的倒排鏈。在單查詢上可能相比并沒有明顯優(yōu)勢(shì)，甚至?xí)恍Ｋ詾榱酥С指咝У臄?shù)值類或者多維度查詢，引入類。

Lucene 是一個(gè)基于 Java 的全文信息檢索工具包，目前主流的搜索系統(tǒng)Elasticsearch和solr都是基于lucene的索引和搜索能力進(jìn)行。想要理解搜索系統(tǒng)的實(shí)現(xiàn)原理，就需要深入lucene這一層，看看lucene是如何存儲(chǔ)需要檢索的數(shù)據(jù)，以及如何完成高效的數(shù)據(jù)檢索。

在數(shù)據(jù)庫中因?yàn)橛兴饕拇嬖冢部梢灾С趾芏喔咝У牟樵儾僮鳌２贿^對(duì)比lucene，數(shù)據(jù)庫的查詢能力還是會(huì)弱很多，本文就將探索下lucene支持哪些查詢，并會(huì)重點(diǎn)選取幾類查詢分析lucene內(nèi)部是如何實(shí)現(xiàn)的。為了方便大家理解，我們會(huì)先簡(jiǎn)單介紹下lucene里面的一些基本概念，然后展開lucene中的幾種數(shù)據(jù)存儲(chǔ)結(jié)構(gòu)，理解了他們的存儲(chǔ)原理后就可以方便知道如何基于這些存儲(chǔ)結(jié)構(gòu)來實(shí)現(xiàn)高效的搜索。本文重點(diǎn)關(guān)注是lucene如何做到傳統(tǒng)數(shù)據(jù)庫較難做到的查詢，對(duì)于分詞，打分等功能不會(huì)展開介紹。

本文具體會(huì)分以下幾部分：

介紹lucene的數(shù)據(jù)模型，細(xì)節(jié)可以參閱lucene數(shù)據(jù)模型一文。

介紹lucene中如何存儲(chǔ)需要搜索的term。

介紹lucene的倒排鏈的如何存儲(chǔ)以及如何實(shí)現(xiàn)docid的快速查找。

介紹lucene如何實(shí)現(xiàn)倒排鏈合并。

介紹lucene如何做范圍查詢和前綴匹配。

介紹lucene如何優(yōu)化數(shù)值類范圍查詢。

Lucene中包含了四種基本數(shù)據(jù)類型，分別是：

Index：索引，由很多的Document組成。

Document：由很多的Field組成，是Index和Search的最小單位。

Field：由很多的Term組成，包括Field Name和Field Value。

Term：由很多的字節(jié)組成。一般將Text類型的Field Value分詞之后的每個(gè)最小單元叫做Term。

在lucene中，讀寫路徑是分離的。寫入的時(shí)候創(chuàng)建一個(gè)IndexWriter，而讀的時(shí)候會(huì)創(chuàng)建一個(gè)IndexSearcher，
下面是一個(gè)簡(jiǎn)單的代碼示例，如何使用lucene的IndexWriter建索引以及如何使用indexSearch進(jìn)行搜索查詢。

  Analyzer analyzer = new StandardAnalyzer();
    // Store the index in memory:
    Directory directory = new RAMDirectory();
    // To store an index on disk, use this instead:
    //Directory directory = FSDirectory.open("/tmp/testindex");
    IndexWriterConfig config = new IndexWriterConfig(analyzer);
    IndexWriter iwriter = new IndexWriter(directory, config);
    Document doc = new Document();
    String text = "This is the text to be indexed.";
    doc.add(new Field("fieldname", text, TextField.TYPE_STORED));
    iwriter.addDocument(doc);
    iwriter.close();

    // Now search the index:
    DirectoryReader ireader = DirectoryReader.open(directory);
    IndexSearcher isearcher = new IndexSearcher(ireader);
    // Parse a simple query that searches for "text":
    QueryParser parser = new QueryParser("fieldname", analyzer);
    Query query = parser.parse("text");
    ScoreDoc[] hits = isearcher.search(query, 1000).scoreDocs;
    //assertEquals(1, hits.length);
    // Iterate through the results:
    for (int i = 0; i < hits.length; i++) {
         Document hitDoc = isearcher.doc(hits[i].doc);
         System.out.println(hitDoc.get("fieldname"));
    }
    ireader.close();
    directory.close();

從這個(gè)示例中可以看出，lucene的讀寫有各自的操作類。本文重點(diǎn)關(guān)注讀邏輯，在使用IndexSearcher類的時(shí)候，需要一個(gè)DirectoryReader和QueryParser，其中DirectoryReader需要對(duì)應(yīng)寫入時(shí)候的Directory實(shí)現(xiàn)。QueryParser主要用來解析你的查詢語句，例如你想查 “A and B"，lucene內(nèi)部會(huì)有機(jī)制解析出是term A和term B的交集查詢。在具體執(zhí)行Search的時(shí)候指定一個(gè)最大返回的文檔數(shù)目，因?yàn)榭赡軙?huì)有過多命中，我們可以限制單詞返回的最大文檔數(shù)，以及做分頁返回。

下面會(huì)詳細(xì)介紹一個(gè)索引查詢會(huì)經(jīng)過幾步，每一步lucene分別做了哪些優(yōu)化實(shí)現(xiàn)。

在lucene中查詢是基于segment。每個(gè)segment可以看做是一個(gè)獨(dú)立的subindex，在建立索引的過程中，lucene會(huì)不斷的flush內(nèi)存中的數(shù)據(jù)持久化形成新的segment。多個(gè)segment也會(huì)不斷的被merge成一個(gè)大的segment，在老的segment還有查詢?cè)谧x取的時(shí)候，不會(huì)被刪除，沒有被讀取且被merge的segement會(huì)被刪除。這個(gè)過程類似于LSM數(shù)據(jù)庫的merge過程。下面我們主要看在一個(gè)segment內(nèi)部如何實(shí)現(xiàn)高效的查詢。為了方便大家理解，我們以人名字，年齡，學(xué)號(hào)為例，如何實(shí)現(xiàn)查某個(gè)名字（有重名）的列表。

在lucene中為了查詢name=XXX的這樣一個(gè)條件，會(huì)建立基于name的倒排鏈。以上面的數(shù)據(jù)為例，倒排鏈如下：
姓名

Alice | [1,2,3]
---- | --- |
Alan | [4,5]
如果我們還希望按照年齡查詢，例如想查年齡=18的列表，我們還可以建立另一個(gè)倒排鏈：

18 | [1,5]
---| --- |
20 | [2]
21 | [3,4]

在這里，Alice，Alan，18，這些都是term。所以倒排本質(zhì)上就是基于term的反向列表，方便進(jìn)行屬性查找。到這里我們有個(gè)很自然的問題，如果term非常多，如何快速拿到這個(gè)倒排鏈呢？在lucene里面就引入了term dictonary的概念，也就是term的字典。term字典里我們可以按照term進(jìn)行排序，那么用一個(gè)二分查找就可以定為這個(gè)term所在的地址。這樣的復(fù)雜度是logN，在term很多，內(nèi)存放不下的時(shí)候，效率還是需要進(jìn)一步提升。可以用一個(gè)hashmap，當(dāng)有一個(gè)term進(jìn)入，hash繼續(xù)查找倒排鏈。這里hashmap的方式可以看做是term dictionary的一個(gè)index。 從lucene4開始，為了方便實(shí)現(xiàn)rangequery或者前綴，后綴等復(fù)雜的查詢語句，lucene使用FST數(shù)據(jù)結(jié)構(gòu)來存儲(chǔ)term字典，下面就詳細(xì)介紹下FST的存儲(chǔ)結(jié)構(gòu)。

FST
我們就用Alice和Alan這兩個(gè)單詞為例，來看下FST的構(gòu)造過程。首先對(duì)所有的單詞做一下排序?yàn)椤癆lice”，“Alan”。

插入“Alan”

插入“Alice”

這樣你就得到了一個(gè)有向無環(huán)圖，有這樣一個(gè)數(shù)據(jù)結(jié)構(gòu)，就可以很快查找某個(gè)人名是否存在。FST在單term查詢上可能相比hashmap并沒有明顯優(yōu)勢(shì)，甚至?xí)恍５窃诜秶熬Y搜索以及壓縮率上都有明顯的優(yōu)勢(shì)。

在通過FST定位到倒排鏈后，有一件事情需要做，就是倒排鏈的合并。因?yàn)椴樵儣l件可能不止一個(gè)，例如上面我們想找name="alan" and age="18"的列表。lucene是如何實(shí)現(xiàn)倒排鏈的合并呢。這里就需要看一下倒排鏈存儲(chǔ)的數(shù)據(jù)結(jié)構(gòu)

SkipList
為了能夠快速查找docid，lucene采用了SkipList這一數(shù)據(jù)結(jié)構(gòu)。SkipList有以下幾個(gè)特征：

元素排序的，對(duì)應(yīng)到我們的倒排鏈，lucene是按照docid進(jìn)行排序，從小到大。

跳躍有一個(gè)固定的間隔，這個(gè)是需要建立SkipList的時(shí)候指定好，例如下圖以間隔是3

SkipList的層次，這個(gè)是指整個(gè)SkipList有幾層

有了這個(gè)SkipList以后比如我們要查找docid=12，原來可能需要一個(gè)個(gè)掃原始鏈表，1，2，3，5，7，8，10，12。有了SkipList以后先訪問第一層看到是然后大于12，進(jìn)入第0層走到3，8，發(fā)現(xiàn)15大于12，然后進(jìn)入原鏈表的8繼續(xù)向下經(jīng)過10和12。
有了FST和SkipList的介紹以后，我們大體上可以畫一個(gè)下面的圖來說明lucene是如何實(shí)現(xiàn)整個(gè)倒排結(jié)構(gòu)的：

有了這張圖，我們可以理解為什么基于lucene可以快速進(jìn)行倒排鏈的查找和docid查找，下面就來看一下有了這些后如何進(jìn)行倒排鏈合并返回最后的結(jié)果。

倒排合并
假如我們的查詢條件是name = “Alice”，那么按照之前的介紹，首先在term字典中定位是否存在這個(gè)term，如果存在的話進(jìn)入這個(gè)term的倒排鏈，并根據(jù)參數(shù)設(shè)定返回分頁返回結(jié)果即可。這類查詢，在數(shù)據(jù)庫中使用二級(jí)索引也是可以滿足，那lucene的優(yōu)勢(shì)在哪呢。假如我們有多個(gè)條件，例如我們需要按名字或者年齡多帶帶查詢，也需要進(jìn)行組合 name = "Alice" and age = "18"的查詢，那么使用傳統(tǒng)二級(jí)索引方案，你可能需要建立兩張索引表，然后分別查詢結(jié)果后進(jìn)行合并，這樣如果age = 18的結(jié)果過多的話，查詢合并會(huì)很耗時(shí)。那么在lucene這兩個(gè)倒排鏈?zhǔn)窃趺春喜⒛亍?br>假如我們有下面三個(gè)倒排鏈需要進(jìn)行合并。

在lucene中會(huì)采用下列順序進(jìn)行合并：

在termA開始遍歷，得到第一個(gè)元素docId=1

Set currentDocId=1

在termB中 search(currentDocId) = 1 (返回大于等于currentDocId的一個(gè)doc),

因?yàn)閏urrentDocId ==1，繼續(xù)
如果currentDocId 和返回的不相等，執(zhí)行2，然后繼續(xù)

到termC后依然符合，返回結(jié)果

currentDocId = termC的nextItem

然后繼續(xù)步驟3 依次循環(huán)。直到某個(gè)倒排鏈到末尾。

整個(gè)合并步驟我可以發(fā)現(xiàn)，如果某個(gè)鏈很短，會(huì)大幅減少比對(duì)次數(shù)，并且由于SkipList結(jié)構(gòu)的存在，在某個(gè)倒排中定位某個(gè)docid的速度會(huì)比較快不需要一個(gè)個(gè)遍歷。可以很快的返回最終的結(jié)果。從倒排的定位，查詢，合并整個(gè)流程組成了lucene的查詢過程，和傳統(tǒng)數(shù)據(jù)庫的索引相比，lucene合并過程中的優(yōu)化減少了讀取數(shù)據(jù)的IO，倒排合并的靈活性也解決了傳統(tǒng)索引較難支持多條件查詢的問題。

BKDTree
在lucene中如果想做范圍查找，根據(jù)上面的FST模型可以看出來，需要遍歷FST找到包含這個(gè)range的一個(gè)點(diǎn)然后進(jìn)入對(duì)應(yīng)的倒排鏈，然后進(jìn)行求并集操作。但是如果是數(shù)值類型，比如是浮點(diǎn)數(shù)，那么潛在的term可能會(huì)非常多，這樣查詢起來效率會(huì)很低。所以為了支持高效的數(shù)值類或者多維度查詢，lucene引入類BKDTree。BKDTree是基于KDTree，對(duì)數(shù)據(jù)進(jìn)行按照維度劃分建立一棵二叉樹確保樹兩邊節(jié)點(diǎn)數(shù)目平衡。在一維的場(chǎng)景下，KDTree就會(huì)退化成一個(gè)二叉搜索樹，在二叉搜索樹中如果我們想查找一個(gè)區(qū)間，logN的復(fù)雜度就會(huì)訪問到葉子結(jié)點(diǎn)得到對(duì)應(yīng)的倒排鏈。如下圖所示：

如果是多維，kdtree的建立流程會(huì)發(fā)生一些變化。
比如我們以二維為例，建立過程如下：

確定切分維度，這里維度的選取順序是數(shù)據(jù)在這個(gè)維度方法最大的維度優(yōu)先。一個(gè)直接的理解就是，數(shù)據(jù)分散越開的維度，我們優(yōu)先切分。

切分點(diǎn)的選這個(gè)維度最中間的點(diǎn)。

遞歸進(jìn)行步驟1，2，我們可以設(shè)置一個(gè)閾值，點(diǎn)的數(shù)目少于多少后就不再切分，直到所有的點(diǎn)都切分好停止。

下圖是一個(gè)建立例子：

BKDTree是KDTree的變種，因?yàn)榭梢钥闯鰜恚琄DTree如果有新的節(jié)點(diǎn)加入，或者節(jié)點(diǎn)修改起來，消耗還是比較大。類似于LSM的merge思路，BKD也是多個(gè)KDTREE，然后持續(xù)merge最終合并成一個(gè)。不過我們可以看到如果你某個(gè)term類型使用了BKDTree的索引類型，那么在和普通倒排鏈merge的時(shí)候就沒那么高效了所以這里要做一個(gè)平衡，一種思路是把另一類term也作為一個(gè)維度加入BKDTree索引中。

通過之前介紹可以看出lucene通過倒排的存儲(chǔ)模型實(shí)現(xiàn)term的搜索，那對(duì)于有時(shí)候我們需要拿到另一個(gè)屬性的值進(jìn)行聚合，或者希望返回結(jié)果按照另一個(gè)屬性進(jìn)行排序。在lucene4之前需要把結(jié)果全部拿到再讀取原文進(jìn)行排序，這樣效率較低，還比較占用內(nèi)存，為了加速lucene實(shí)現(xiàn)了fieldcache，把讀過的field放進(jìn)內(nèi)存中。這樣可以減少重復(fù)的IO，但是也會(huì)帶來新的問題，就是占用較多內(nèi)存。新版本的lucene中引入了DocValues，DocValues是一個(gè)基于docid的列式存儲(chǔ)。當(dāng)我們拿到一系列的docid后，進(jìn)行排序就可以使用這個(gè)列式存儲(chǔ)，結(jié)合一個(gè)堆排序進(jìn)行。當(dāng)然額外的列式存儲(chǔ)會(huì)占用額外的空間，lucene在建索引的時(shí)候可以自行選擇是否需要DocValue存儲(chǔ)和哪些字段需要存儲(chǔ)。

介紹了lucene中幾個(gè)主要的數(shù)據(jù)結(jié)構(gòu)和查找原理后，我們?cè)趤砜聪耹ucene的代碼結(jié)構(gòu)，后續(xù)可以深入代碼理解細(xì)節(jié)。lucene的主要有下面幾個(gè)目錄：

analysis模塊主要負(fù)責(zé)詞法分析及語言處理而形成Term。

codecs模塊主要負(fù)責(zé)之前提到的一些數(shù)據(jù)結(jié)構(gòu)的實(shí)現(xiàn)，和一些編碼壓縮算法。包括skiplist，docvalue等。

document模塊主要包括了lucene各類數(shù)據(jù)類型的定義實(shí)現(xiàn)。

index模塊主要負(fù)責(zé)索引的創(chuàng)建，里面有IndexWriter。

store模塊主要負(fù)責(zé)索引的讀寫。

search模塊主要負(fù)責(zé)對(duì)索引的搜索。

geo模塊主要為geo查詢相關(guān)的類實(shí)現(xiàn)

util模塊是bkd，fst等數(shù)據(jù)結(jié)構(gòu)實(shí)現(xiàn)。

本文介紹了lucene中的一些主要數(shù)據(jù)結(jié)構(gòu)，以及如何利用這些數(shù)據(jù)結(jié)構(gòu)實(shí)現(xiàn)高效的查找。我們希望通過這些介紹可以加深理解倒排索引和傳統(tǒng)數(shù)據(jù)庫索引的區(qū)別，數(shù)據(jù)庫有時(shí)候也可以借助于搜索引擎實(shí)現(xiàn)更豐富的查詢語意。除此之外，做為一個(gè)搜索庫，如何進(jìn)行打分，query語句如何進(jìn)行parse這些我們沒有展開介紹，有興趣的同學(xué)可以深入lucene的源碼進(jìn)一步了解。

詳情請(qǐng)閱讀原文