Method for dynamic updating of an index, and a search engine implementing the same
View Patent ↗In a method for a dynamic updating of an index of a search engine, wherein the index is an inverted index comprising a dictionary, a posting file with a posting list for each keyword of the index and a database log, the documents are inserted in the index in small batches called update generations, a list of all occurrences of keywords in the documents of each update generation is generated, the occurrence list is inserted in the database log, and for each keyword entered in the database a reference to a previous entry of the same keyword is created. This previous entry has a reference stored in the mass storage device as the last added entry of all recently keywords.—A search engine performing the method may be implemented on one or more servers with a mass storage device, and comprises a core search engine with a search subsystem and an indexing subsystem for creating a keyword index stored on the mass storage device and with the index realized as a dynamically updateable index.
1. A method for dynamic updating of an index of a search engine, comprising:
storing the index on a mass storage device of a search engine that is implemented on one or more servers, the index being an inverted index, the index comprising a dictionary that maps words to word identifiers, a posting file, and a database log that stores changes to the dictionary as the changes occur, the posting file having posting lists for each keyword of the index;
generating a position list for a keyword, wherein the position list gives all locations of the keyword in the documents;
inserting a record in the database log in response to each change made to the dictionary, the record including the keyword, the position list and a reference to a previous record of the same keyword in the database log, said previous entry having a reference stored in the mass storage device as the last added entry of all recently added keywords;
retrieving a dictionary entry from the dictionary that corresponds to a keyword;
using data indicated by the dictionary entry to read a given position list and a given delta list from the posting file, the given position list indicating positions of the given keyword, the given delta list containing changes to the given occurrence list;
merging into a single position list the given position list, updates from the given delta list and given entries in the database log, the given entries in the database log indicating modifications to the given position list; and
using the single position list for further processing of a search query.
2. The method according to claim 1 , further comprising:
grouping all updates of the database log together at specified intervals moving the grouped updates to the posting file; and
storing each keyword respectively in an occurrence list in the form of occurrences of the keyword older than a determined update generation and in a delta list in the form of a set of smaller updates more recent than the same update generation, such that the dictionary contains one entry for each keyword in the posting file and a reference to the occurrence list and the delta list.
3. The method according to claim 2 , further comprising storing the occurrence list and the delta list in the posting file.
4. The method according to claim 2 , wherein the dictionary is implemented as a B-tree.
5. The method according to claim 4 , further comprising:
storing the occurrence list and the delta list in the B-tree when the occurrence list and the delta list are below a specific size.
6. The method according to claim 2 , further comprising:
forcing the database log to the mass storage device at the end of each update generation; and
recovering the index after a failure or stoppage of the search engine by replaying the database log and recreating the keyword entries in the main memory up to the last update in the database log for each keyword.
7. The method according to claim 2 , further comprising:
organizing the posting file as a circular file;
reclaiming unused space at a tail of the posting file; and
moving existing keyword entries to a head of the posting file.
8. The method according to claim 7 , further comprising adding a keyword entry to the end of the posting file if no space to move an existing entry or to add a new keyword entry is present.
9. The method according to claim 1 , wherein merging of the given position list and the given delta list is performed without including any update generation more recent than a specified generation, such that the search query can be processed for occurrences of the keyword existing at the end of the specific generation.
10. A disk memory storing instructions that when executed perform operations for dynamic updating of an index of a search engine, comprising:
storing the index on a mass storage device of a search engine that is implemented on one or more servers, the index being an inverted index, the index comprising a dictionary that maps words to word identifiers, a posting file, and a database log that stores changes to the dictionary as the changes occur, the posting file having posting lists for each keyword of the index;
generating a position list for a keyword, wherein the position list gives all locations of the keyword in the documents;
inserting a record in the database log in response to each change made to the dictionary, the record including the keyword, the position list and a reference to a previous record of the same keyword in the database log, said previous entry having a reference stored in the mass storage device as the last added entry of all recently added keywords;
retrieving a dictionary entry from the dictionary that corresponds to a keyword, using data indicated by the dictionary entry to read a given position list and a given delta list from the posting file, the given position list indicating positions of the given keyword, the given delta list containing changes to the given occurrence list,
merging into a single position list the given position list, updates from the given delta list and given entries in the database log, the given entries in the database log indicating modifications to the given position list; and
using the single position list for further processing of a search query.
11. The disk memory according to claim 10 , further comprising:
grouping updates of the database log together at specified intervals moving the grouped updates to the posting file; and storing each keyword respectively in an occurrence list in the form of occurrences of the keyword older than a determined update generation and in a delta list in the form of a set of smaller updates more recent than the same update generation, such that the dictionary contains one entry for each keyword in the posting file and a reference to the occurrence list and the delta list.
12. The disk memory according to claim 11 , wherein the dictionary is implemented as a B-tree and storing the occurrence list and the delta list in the B-tree when the occurrence list and the delta list are below a specific size.
13. The disk memory according to claim 11 , further comprising:
forcing the database log to the mass storage device at the end of each update generation; and recovering the index after a failure or stoppage of the search engine by replaying the database log and recreating the keyword entries in the main memory up to the last update in the database log for each keyword.
14. The disk memory according to claim 11 , further comprising:
organizing the posting file as a circular file; reclaiming unused space at a tail of the posting file; and moving existing keyword entries to a head of the posting file.