Python-Xapian-Speicherstruktur

Um den Suchdienst im Projekt zu unterstützen, verwenden wir xapian als Back-End-Suchmaschine. Es ist wegen seiner guten Leistung und Benutzerfreundlichkeit beliebt. Das Folgende ist der Basiscode:

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

Obwohl es sehr einfach zu bedienen ist, war ich schon immer neugierig auf seine Speicher-Engine, deshalb habe ich mir die Implementierung der neuesten Speicher-Engine Brass angesehen. Das Folgende ist die hierarchische Struktur des gesamten Datenverzeichnisses:
/tmp/user_index
flintlock
iamchert
postlist.baseA
postlist.baseB
postlist.DB //Alle Term-zu-Docid-Zuordnungen speichern record.baseB
record.DB //Speichert alle Dokumente zu entsprechenden Datenzuordnungen
termlist.baseA
termlist.baseB
termlist.DB //Speichert die Zuordnung aller Dokumente zu entsprechenden Begriffen >
Die von der Brass-Speicher-Engine verwendete Datenstruktur ist BTree. Jede der oben genannten *.DB speichert also eine BTree *.baseA/B, einschließlich der Datenblöcke dieser großen Datendatei verwendet wurde und welche kostenlosen Bitmaps sowie Versionsnummer und andere zugehörige Informationen
BTree wird als N-Ebene in Xapian dargestellt und ein Cursor dieser Ebene wird beibehalten. Dies wird verwendet, um auf einen bestimmten Datenblock zu verweisen, auf den gerade zugegriffen wird, und auf eine bestimmte Position im Datenblock. Die Datenstruktur jedes Datenblocks ist wie folgt:


Die obigen Kommentare von xapian Die Datenstruktur jedes Blocks ist klar erklärt. Zusätzlich zu den Daten besteht die Metainformation aus einer kleinen Dateneinheit, die aus Elementen wie I (der Länge der gesamten Dateneinheit) und K (der Länge des Dateneinheitsschlüssels) besteht x (Schlüsselkennung)) und C (repräsentiert das entsprechende Wie viele Elemente besteht dieser Schlüssel? Denn wenn der einem bestimmten Schlüssel entsprechende Wert zu groß ist, wird eine Wertsegmentierung durchgeführt. C stellt also die Gesamtzahl der Punkte dar. Und das vorherige x stellt dar, um welches Datenelement es sich bei dieser Einheit handelt. Wenn Sie den gesamten großen Wert dieses Schlüssels lesen müssen, können Sie ihn entsprechend der Seriennummer x zusammenführen.) Tag ist der Wert, der dem Schlüssel entspricht, den wir gerade haben erwähnt, aber xapian definiert es als Tag. Daher ist die Definition auch relativ sinnvoll. Beispielsweise speichert das Nicht-Blattknoten-Tag eines BTree die Adresse der nächsten Datenblockschicht Blattknoten, es speichert die Speicherstruktur des gesamten Baums klar.

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.

Hier gibt es ein interessantes Problem, nämlich die Speicherung von Postlisten Das Wort enthält viele, viele Dokumente, zum Beispiel 1 Million. Wenn wir dann inkrementelle Aktualisierungen durchführen, wie können Sie schnellstmöglich herausfinden, in welchem ​​Datenblock sich dieses Dokument befindet? Der Autor verwendet term+docid als Schlüssel von BTree, um dieses Problem zu lösen. Jeder Block ist auf eine bestimmte Größe festgelegt Lesen aller Blöcke und anschließendes Durchsuchen .

Derzeit entwickelt der Autor die Replikationsmethode, die inkrementelle Aktualisierungen auf anderen Maschinen unterstützen kann. Auf diese Weise können die Daten zuverlässig sein (es wird nicht durch Datenverluste auf der Festplatte einer einzelnen Maschine verursacht). und hohe Verfügbarkeit (eine einzelne Maschine ist nicht verfügbar, die Anwendungsschicht kann auf eine Backup-Maschine umgestellt werden).

Übrigens: Ich habe die Mailingliste von xapian devel in den letzten zwei Tagen gelesen, obwohl ich keine eingereicht habe Fragen, die ich gelesen habe. Der Autor (Olly Betts) wird auf jede Frage geduldig und ausführlich antworten. Er ist wirklich nett