Patent ID: 7315862

Claim:
A system providing lock-free access to records in a database, the system comprising: computer memory storing a plurality of records organized according to a first search data structure and according to a second search data structure, the first search data structure organizing the plurality of records according to the same ranking of records used by the second search data structure to organize the plurality of records; and a processor executing a computer program to search the computer memory for a particular record in the plurality of records, the computer program searching for the particular record by accessing one or more records in an order determined by the first search data structure until a record is accessed that indicates that the first search data structure is in an intermediate state, and, in response to the record that indicates that the first search data structure is in an intermediate state, switching to use of the second search data structure to search for the particular record by accessing one or more records in an order determined by the second search data structure, wherein use of the second search data structure to search for the particular record commences at the record that indicates the first search data structure is in the intermediate state.