05204958 is referenced by 128 patents and cites 6 patents.

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.

Title
System and method for efficiently indexing and storing a large database with high data insertion frequency
Application Number
7/722007
Publication Number
5204958
Application Date
June 27, 1991
Publication Date
April 20, 1993
Inventor
Patrick E O Neil
Lexington
MA, US
Dieter Gawlick
Palo Alto
CA, US
Edward C Cheng
South San Francisco
CA, US
Agent
Flehr Hohbach Test Albritton & Herbert
Assignee
Digital Equipment Corporation
MA, US
IPC
G06F 15/413
View Original Source