Deletion and compaction using versioned nodes

Abstract

An information management system includes a database comprising a B-Tree data structure. The B-Tree includes a plurality of nodes associated with disk blocks, handles stored in the nodes, and version numbers attached to each of the handles and disk blocks. In addition, the system includes a mechanism for initially assigning each disk block a first prescribed version number (e.g., version number 0), and a mechanism for performing an allocate operation whereby a handle identifying a disk block is returned along with the disk block's version number. The system may also include a mechanism for performing a deallocate operation that increments the disk block's version number, as well as a mechanism for performing a read operation that returns a disk block's version number in addition to the node stored at that disk block. Moreover, a caller of the read operation checks whether the version number returned by the read operation matches the version number of the handle that was read. The caller is preferably restarted if the version numbers do not match, thus indicating that the node has been deleted and subsequently deallocated by a different thread. The caller may be a lookup operation, an insert operation, or a delete operation.

Dependencies are inferred from the claim text.