Method for maintaining an index

• US 5,765,168 A
• Filed: 08/09/1996
• Issued: 06/09/1998
• Est. Priority Date: 08/09/1996
• Status: Expired due to Term

• Current Assignee: R2 Solutions LLC (Acacia Research Corporation)
• Original Assignee: Digital Equipment Corporation (HP Inc.)
• Inventors: Burrows, Michael
• Primary Examiner(s): Black, Thomas G.
• Assistant Examiner(s): HO, RUAY L
• Application Number:
  US08/696,816
• Time in Patent Office: 669 Days
• Field of Search: 395/601, 395/602, 395/603, 395/607, 395/608, 395/610, 395/611, 395/612, 395/613, 395/614, 395/615, 395/616, 395/617, 395/760, 395/336, 395/674, 380/4, 380/25, 707/100, 707/200, 707/201
• US Class Current: 1/1
• CPC Class Codes: G06F 16/319 Inverted lists

Abstract

A computer implemented method maintains an index of a database. The database stores information as a plurality of records. Batches of records are indexed by storing index entries in a memory. Each index entry includes a word entry for each unique portion of information of the database, and one or more location entries pointing at occurrences of the portions of information. The index entries are organized according to a collating order of the word entries. The location entries are stored sequentially for each word entry. The index entries are organized into a plurality of tiers of files. There is one tier of files for each batch of records indexed. A merged tier of files is periodically produced by merging a subsequently produced tier of files with a previously produced tier of files. The index entries of the merged tier of files are a logical union of the index entries of the subsequently and previous produced tiers of files. The location entries of deleted records are expunged while merging the tiers of files.

Claims

1. A computer implemented method for maintaining an index of a database, the database storing information as a plurality of records, comprising:

indexing batches of the records by storing index entries in a memory, each index entry including a word entry for each unique portion of information of the database, and one or more location entries pointing at occurrences of the portions of information;

collating the index entries according to the order of the word entries, and sequentially according to the locations of each word entry;

organizing the index entries in a plurality of tiers of files, there at least initially being one tier of files for each batch of records indexed; and

periodically merging a subsequently produced tier of files with a previously produced tier of files to produce a merged tier of files, the index entries being a logical union of the index entries of the subsequently and previous produced tiers of files.

2. The method of claim 1 further comprising:

writing a deleted location entry in an index entry having a word entry indicating a deleted status of a deleted record identified by the deleted location entry;

deleting the location entries of the deleted record substantially simultaneous with merging the tiers of files.

3. A computer implemented method for maintaining an index of a database, the database storing information as a plurality of records, comprising the steps of:

indexing batches of the records by storing index entries in a memory;

organizing the index entries into a plurality of tiers, including a first tier and a second tier, wherein the first tier includes a first bucket and the second tier includes a second bucket, the first bucket and the second bucket each including at least one of the index entries; and

merging the first tier with the second tier to merge the first bucket with the second bucket.

4. The computer implemented method of claim 3, wherein the first bucket is an extension of the second bucket.

5. The computer implemented method of claim 4, wherein the first bucket is a logical extension of the second bucket.

6. The computer implemented method of claim 3, further comprising the step of:

responsive to the merging, decreasing a number of tiers within the plurality of tiers.

7. The computer implemented method of claim 3, further comprising the steps of:

attaching a delete flag to a particular index entry responsive to the deletion of one of the plurality of records; and

responsive to the delete flag, expunging at least a portion of the particular index entry from the plurality of tiers.

8. A computer system for maintaining a database storing information as a plurality of records, the computer system comprising:

a memory configured to store a first and a second section of data, the first section having a first storage area configured to store a first entry and the second section having a second storage area configured to store a second entry, wherein the second storage area is a logical extension of the first storage area; and

a processor configured to merge the second storage area with the first storage area.

9. The computer system of claim 8, wherein the processor is further configured to merge the second section with the first section such that the first entry and the second entry are merged to form a logical union.

10. The computer system of claim 8, wherein the processor is further configured to index one of the plurality of records by storing an index record in the memory, wherein the index record includes a word entry and a location entry.

11. The computer system of claim 10, wherein the index record is stored in one of the first and the second entries.

12. The computer system of claim 10, wherein the word entry is indicative of a portion of information stored in the database and the location entry is indicative of occurrences of the portion of information within the database.

13. The computer system of claim 8, wherein the processor is further configured to expunge at least a portion of the second entry from the second storage area responsive to the merger.

14. The computer system of claim 8, wherein the processor is further configured to attach a delete flag to one of the first and the second entries which corresponds, at least partially, to one of the plurality of records that has been deleted.

15. The computer system of claim 14, wherein the browser is further configured to identify the deleted record.