Patent ID: 8595248

Claim:
A method comprising the steps of: in response to receiving a query, determining whether a particular key value exists in one or more journal indexes that are part of a multi-level index (a) that indexes one or more objects and (b) that comprises a plurality of index levels that includes the one or more journal indexes and a main index; wherein the main index comprises a set of one or more branch nodes and a plurality of leaf nodes that each comprises multiple key values that are associated with data from the one or more objects; wherein the main index is associated with a particular data structure that is separate from the main index; using the particular data structure to determine whether the particular key value does not exist in the main index; wherein determining whether the particular key value does not exist in the main index is performed without analyzing any key value in any branch node or leaf node of the main index; accessing a leaf node of the plurality of leaf nodes only if it is determined that the particular key value might exist in the main index; receiving a plurality of updates that affect the multi-level index; applying the plurality of updates to one or more of the one or more journal indexes without applying any of the plurality of updates to the main index and without updating the particular data structure; in response to determining that one or more criteria are satisfied, applying the plurality of updates to the main index; in response to applying the plurality of updates to the main index, generating a new data structure to replace the particular data structure; wherein the steps are performed on one or more computing devices.