Patent Document ID: 5560007
Application ID: 08544679
Patent Flag: 1

Claim One:
1. In a system for processing data records, each record including at least one field for storing information, the system including means for logically ordering the records by an index, said index comprising a tree structure storing key values derived from values stored by said at least one field of each record, said index including a plurality of leaf nodes, each leaf node comprising a particular key value together with a record identifier for indicating a particular record which stores said particular key value, said leaf nodes being sorted by the key values stored thereat according to a user-specified sort order, said leaf nodes being linked via pointers, a method for identifying from said index records of interest to a user comprising: (a) receiving a query expression specifying at least one condition for selecting particular records of interest to the user; (b) with the index that logically orders the records according to key values, locating first and second leaf nodes of said plurality of leaf nodes which store a bottom and a top key value of the index, respectively, which satisfies said at least one condition, said bottom key value identifying a first record of interest and said top key value identifying a second record of interest, said method locating said first and second leaf nodes before attempting to locate other leaf nodes storing key values which satisfy said at least one condition; and (c) after locating said first and second leaf nodes, identifying others of said records of interest without reading key values stored at leaf nodes by traversing pointers of leaf nodes which lie between said first and second leaf nodes, for locating all nodes storing key values of the index which logically lie between said bottom and top key values, wherein each located key value occurs at a leaf node storing a record identifier which identifies a record satisfying said at least one condition.