System and method for efficiently indexing and storing a large database

Abstract

A database index file is maintained by a computer system having primary random access memory and secondary memory. A record for each item added to the database is stored in a sequential file in secondary memory (disk storage) and an indexed pointer to the new record is stored in a small B-tree stored in primary random access memory. The full index file for the database is a second, large B-tree stored in secondary memory. Leaf-nodes of the full index file are stored in indexed order. Periodically, a portion of the memory resident small B-tree is merged with a corresponding portion of the large B-tree by selecting a range of index values and retrieving from secondary memory all indexed pointers in the selected range of index values. The indexed pointers in the first B-tree in the selected range of index values are merged into the retrieved records, the resulting merged set of indexed pointers are stored in secondary memory in indexed order in a contiguous area of secondary memory. As a result, the indexed pointers for newly added database records are written to secondary memory in batches, thereby accessing secondary memory very efficiently.