怎樣解析Lucene查詢原理

這篇文章將為大家詳細講解有關怎樣解析Lucene查詢原理，文章內容質量較高，因此小編分享給大家做個參考，希望大家閱讀完這篇文章后對相關知識有一定的了解。

前言

Lucene 是一個基于 Java 的全文信息檢索工具包，目前主流的搜索系統Elasticsearch和solr都是基于lucene的索引和搜索能力進行。想要理解搜索系統的實現原理，就需要深入lucene這一層，看看lucene是如何存儲需要檢索的數據，以及如何完成高效的數據檢索。

在數據庫中因為有索引的存在，也可以支持很多高效的查詢操作。不過對比lucene，數據庫的查詢能力還是會弱很多，本文就將探索下lucene支持哪些查詢，并會重點選取幾類查詢分析lucene內部是如何實現的。為了方便大家理解，我們會先簡單介紹下lucene里面的一些基本概念，然后展開lucene中的幾種數據存儲結構，理解了他們的存儲原理后就可以方便知道如何基于這些存儲結構來實現高效的搜索。本文重點關注是lucene如何做到傳統數據庫較難做到的查詢，對于分詞，打分等功能不會展開介紹。

Lucene數據模型

Lucene中包含了四種基本數據類型，分別是：

Index：索引，由很多的Document組成。
Document：由很多的Field組成，是Index和Search的最小單位。
Field：由很多的Term組成，包括Field Name和Field Value。
Term：由很多的字節組成。一般將Text類型的Field Value分詞之后的每個最小單元叫做Term。

在lucene中，讀寫路徑是分離的。寫入的時候創建一個IndexWriter，而讀的時候會創建一個IndexSearcher，
下面是一個簡單的代碼示例，如何使用lucene的IndexWriter建索引以及如何使用indexSearch進行搜索查詢。

    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();

從這個示例中可以看出，lucene的讀寫有各自的操作類。本文重點關注讀邏輯，在使用IndexSearcher類的時候，需要一個DirectoryReader和QueryParser，其中DirectoryReader需要對應寫入時候的Directory實現。QueryParser主要用來解析你的查詢語句，例如你想查 “A and B"，lucene內部會有機制解析出是term A和term B的交集查詢。在具體執行Search的時候指定一個最大返回的文檔數目，因為可能會有過多命中，我們可以限制單詞返回的最大文檔數，以及做分頁返回。

下面會詳細介紹一個索引查詢會經過幾步，每一步lucene分別做了哪些優化實現。

Lucene 查詢過程

在lucene中查詢是基于segment。每個segment可以看做是一個獨立的subindex，在建立索引的過程中，lucene會不斷的flush內存中的數據持久化形成新的segment。多個segment也會不斷的被merge成一個大的segment，在老的segment還有查詢在讀取的時候，不會被刪除，沒有被讀取且被merge的segement會被刪除。這個過程類似于LSM數據庫的merge過程。下面我們主要看在一個segment內部如何實現高效的查詢。

為了方便大家理解，我們以人名字，年齡，學號為例，如何實現查某個名字（有重名）的列表。

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

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

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

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

FST

我們就用Alice和Alan這兩個單詞為例，來看下FST的構造過程。首先對所有的單詞做一下排序為“Alice”，“Alan”。

1. 插入“Alan”
   

2. 插入“Alice”
   

有了這個SkipList以后比如我們要查找docid=12，原來可能需要一個個掃原始鏈表，1，2，3，5，7，8，10，12。有了SkipList以后先訪問第一層看到是然后大于12，進入第0層走到3，8，發現15大于12，然后進入原鏈表的8繼續向下經過10和12。
有了FST和SkipList的介紹以后，我們大體上可以畫一個下面的圖來說明lucene是如何實現整個倒排結構的：

在lucene中會采用下列順序進行合并：

1. 在termA開始遍歷，得到第一個元素docId=1

2. Set currentDocId=1

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

1. 因為currentDocId ==1，繼續

2. 如果currentDocId 和返回的不相等，執行2，然后繼續

4. 到termC后依然符合，返回結果

5. currentDocId = termC的nextItem

6. 然后繼續步驟3 依次循環。直到某個倒排鏈到末尾。

整個合并步驟我可以發現，如果某個鏈很短，會大幅減少比對次數，并且由于SkipList結構的存在，在某個倒排中定位某個docid的速度會比較快不需要一個個遍歷。可以很快的返回最終的結果。從倒排的定位，查詢，合并整個流程組成了lucene的查詢過程，和傳統數據庫的索引相比，lucene合并過程中的優化減少了讀取數據的IO，倒排合并的靈活性也解決了傳統索引較難支持多條件查詢的問題。

BKDTree

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

BKDTree是KDTree的變種，因為可以看出來，KDTree如果有新的節點加入，或者節點修改起來，消耗還是比較大。類似于LSM的merge思路，BKD也是多個KDTREE，然后持續merge最終合并成一個。不過我們可以看到如果你某個term類型使用了BKDTree的索引類型，那么在和普通倒排鏈merge的時候就沒那么高效了所以這里要做一個平衡，一種思路是把另一類term也作為一個維度加入BKDTree索引中。

如何實現返回結果進行排序聚合

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

關于怎樣解析Lucene查詢原理就分享到這里了，希望以上內容可以對大家有一定的幫助，可以學到更多知識。如果覺得文章不錯，可以把它分享出去讓更多的人看到。