python xapian storage structure

In order to support the search service in the project, we use xapian as the back-end search engine. It is popular for its good performance and ease of use. The following is the basic code:

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']))

Although it is very simple to use, I have always been concerned about its storage The engine was a little curious, so I took a look at the implementation of the latest storage engine brass. The following is the hierarchy of the entire data directory:
/tmp/user_index
flintlock
iamchert
postlist.baseA
postlist.baseB
postlist.DB //Storage all Term to docid mapping.
record.baseA
record.baseB
record.DB //Storage all docid to corresponding data mapping
termlist.baseA
termlist.baseB
termlist.DB //Storage all docid to corresponding term Mapping. The data structure used by the

brass storage engine is BTree. So each *.DB above stores a BTree. *.baseA/B stores the meta information of the corresponding .DB. Including this large data Which data blocks of the file have been used, which free bitmaps, and version numbers and other related information.
BTree is represented as N Level in xapian. Each level corresponds to a layer of BTree. And maintains a cursor of this layer .Used to point to a certain data block currently being accessed, and a certain position in the data block. The data structure of each data block is as follows:

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.

The above comments from xapian have clearly explained each block The data composition. In addition to the data element information, it is a small data unit composed of items. Each small item includes I (the length of the entire data unit), K (the length of the data unit key + x (key identifier)) , C (indicates how many items the corresponding key consists of, because if the value corresponding to a certain key is too large, value segmentation will be performed. So C means how many points there are in total. And the previous x means that this unit is Which piece of data, if you need to read the entire large value of this key, you can merge it according to the serial number x.), tag is the value corresponding to the key we just mentioned, but xapian defines it as tag. Because it is a Universal storage structure, so this definition makes sense. For example, the non-leaf node tag of a BTree stores the address of the next layer of data blocks. For leaf nodes, related data is stored. Now the entire tree The storage structure has been clearly displayed.

There is an interesting problem here, which is the storage of postlist. Imagine that a certain hot word contains many docids, for example, 1 million. Then when we perform incremental updates Sometimes, if you want to delete a certain docid from this term, how can you find out which data block this docid is in as soon as possible? The author uses term+docid as the key of BTree to solve this problem. The value is all docids larger than this docid. And each block is set to a size. This allows us to locate a docid as quickly as possible. block, instead of reading all blocks and then searching.

xapian also supports multiple readers and single-threaded writers for incremental updates. It adopts a method similar to MVCC in the database, so that there will be no The update blocks the read operation.

Currently, the author is developing the replication method, which can support incremental updates to other machines. This can achieve data reliability (no data loss due to single-machine disk damage) and high availability (single-machine disk damage) Unavailable, the application layer can be switched to a backup machine).

BTW: I have read the xapian devel mailing list in the past two days. Although I have not submitted any questions, I have seen that the author (Olly Betts) will give answers to every question. He is really nice for his patient and detailed reply. I admire him very much.