python xapian儲存結構

在專案中為了支持搜尋服務,我們使用xapian作為後端的搜尋引擎.其因性能良好以及易用受到大家歡迎.下面是基本代碼: 

import xapian
import posixpath
def get_db_path():
    XAPIAN_ROOT = '/tmp/'
    xapian_user_database_path = posixpath.join(XAPIAN_ROOT, u'user_index')
    return xapian_user_database_path
def add_document(database, words):
    doc = xapian.Document()
    for w in words:
        doc.add_term(w)
    database.add_document(doc)
def build_index():
    user_database = xapian.WritableDatabase(get_db_path(), xapian.DB_CREATE_OR_OPEN)
    words = ['a', 'b', 'c']
    add_document(user_database, words)
def search(words, offset=0, length=10):
    user_database = xapian.Database(get_db_path())
    enquire = xapian.Enquire(user_database)
    query = xapian.Query(xapian.Query.OP_AND, words)
    enquire.set_query(query)
    return enquire.get_mset(int(offset), int(length))
def _show_q_results(matches):
    print '%i results found.' % matches.get_matches_estimated()
    print 'Results 1 - %i:' % matches.size()
    for match in matches:
        print '%i: %i%% docid=%i [%s]' % (match.rank + 1,
                                          match.percent,
                                          match.docid,
                                          match.document.get_data()
                                          )
if __name__ == '__main__':
    #index 
    build_index()
    
    #search
    _show_q_results(search(['a','b']))

雖然使用起來很簡單,但是我一直對於他的存儲引擎有點好奇,所以看了一下最新的儲存引擎brass的實現.下面是整個資料目錄的層次結構: 
/tmp/user_index 
flintlock 
iamchert 
postlist.baseA 
postlist.baseB t 
postlist.baseA 
postlist.baseB 
所有post term 到docid的映射. 
record.baseA 
record.baseB 
record.DB //儲存所有docid 到對應的資料的對應 
termlist.baseA 
termlist.baseB termlist.baseB 
termlist.baseA 
termlist.baseB termlist的映射. 

brass存儲引擎採用的數據結構是BTree.所以上面每個*.DB都是存儲一個BTree的.*.baseA/B則是存儲相應的.DB的meta信息.包括這個大的數據文件有哪些資料塊已經被使用,哪些空閒的bitmap,以及版本號等等相關信息. 
BTree在xapian中表示為N Level.每個level對應於BTree的一層.並且維護這一層的一個cursor .用於指向目前正在存取的某一個資料區塊,以及資料區塊中的某一個位置.其中每個資料區塊的資料結構如下: 

from @brass_table.cc
/* A B-tree comprises (a) a base file, containing essential information (Block
   size, number of the B-tree root block etc), (b) a bitmap, the Nth bit of the
   bitmap being set if the Nth block of the B-tree file is in use, and (c) a
   file DB containing the B-tree proper. The DB file is divided into a sequence
   of equal sized blocks, numbered 0, 1, 2 ... some of which are free, some in
   use. Those in use are arranged in a tree.
   Each block, b, has a structure like this:
     R L M T D o1 o2 o3 ... oN <gap> [item] .. [item] .. [item] ...
     <---------- D ----------> <-M->
   And then,
   R = REVISION(b)  is the revision number the B-tree had when the block was
                    written into the DB file.
   L = GET_LEVEL(b) is the level of the block, which is the number of levels
                    towards the root of the B-tree structure. So leaf blocks
                    have level 0 and the one root block has the highest level
                    equal to the number of levels in the B-tree.
   M = MAX_FREE(b)  is the size of the gap between the end of the directory and
                    the first item of data. (It is not necessarily the maximum
                    size among the bits of space that are free, but I can&#39;t
                    think of a better name.)
   T = TOTAL_FREE(b)is the total amount of free space left in b.
   D = DIR_END(b)   gives the offset to the end of the directory.
   o1, o2 ... oN are a directory of offsets to the N items held in the block.
   The items are key-tag pairs, and as they occur in the directory are ordered
   by the keys.
   An item has this form:
           I K key x C tag
             <--K-->
           <------I------>
   A long tag presented through the API is split up into C tags small enough to
   be accommodated in the blocks of the B-tree. The key is extended to include
   a counter, x, which runs from 1 to C. The key is preceded by a length, K,
   and the whole item with a length, I, as depicted above.

上面來自於xapian的註解已經很清楚的說明了每個block的資料構成.除了資料元資訊,就是由item組成的小的資料單元。其中每個小的item包括I(整個資料單元的長度),K(資料單元key的長度+x(key標示)) ,C(表示對應的這個key有多少個item組成,因為某一個key對應的value太大的話,會進行value切分.所以C就表示總計有多少分.而之前的那個x則表示這個單元是第幾份資料,這個如果需要讀取這個key的整個大value就可以根據序號x進行合併.),tag就是我們剛才說的key對應的value,只不過xapian把它定義為tag.因為他是一個通用儲存結構,所以這樣定義也比較說的通.比如說在一顆BTree的非葉子節點tag存儲的是下一層數據塊的地址.對於葉子節點來說則存儲相關的數據.現在整個樹的儲存結構已經清晰的展示出來了. 

這裡面有一個問題比較有意思的是postlist的存儲,設想某一個熱點詞包含有很多很多的docid,比如說有100w個.那麼當我們進行增量更新的時候,想要把某個docid從這個term刪除掉,那麼怎麼才能盡快查找到這個docid在哪個資料塊中呢？作者採用了term+docid作為BTree的key的方式來解決這個問題.value則是所有的大於這個docid的docid.並且每個塊設定一個大小.這樣就能讓我們能盡快的定位一個docid在哪個block中,而不用讀取所有的block然後再去查找了. 

xapian還支持多個reader,單線程writer的方式進行增量更新.採用的類似數據庫中的MVCC的方式,這樣就不會因為更新把讀取操作阻塞住了. 

目前作者正在開發replication方式,可以支援增量更新到其他機器.這樣就能做到資料可靠(不會應為單機磁碟損壞導致資料遺失)以及高可用性(單機不可用,應用層可以切換到備用機器上)了. 🎜🎜BTW:我這兩天看了xapian devel的郵件列表,雖然沒有提交問題,但是看了作者(Olly Betts)對於每個問題都會給出耐心又詳盡的答覆,他人真的是很好.很是佩服.🎜