Patent ID: 8346778

Claim:
A method comprising the steps of: storing a multi-level index that comprises a main index and one or more journal indexes; wherein the main index comprises at least a first branch node and a first plurality of leaf blocks, wherein the first branch node is associated with a first set of leaf blocks that are included in the first plurality of leaf blocks, wherein the first set of leaf blocks are stored sequentially and contiguously on a disk; receiving a plurality of updates to the multi-level index; for each update of the plurality of updates, applying said each update to one or more of the one or more journal indexes without applying the plurality of updates to the main index; applying, as part of a merge operation, the plurality of updates to the main index to (1) generate a second plurality of leaf blocks that are different than the first plurality of leaf blocks, wherein the second plurality of leaf blocks reflect at least a subset of the plurality of updates and (2) generate a second branch node, that is associated with a second set of leaf blocks that are included in the second plurality of leaf blocks, wherein the second set of leaf blocks are stored sequentially and contiguously on the disk; wherein the steps are performed on one or more computing devices.