US Patent 7783671 Deletion and compaction using versioned nodes

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, a method is provided that can include initially assigning version numbers to disk blocks, wherein the disk blocks are associated with nodes in a B-Tree data structure, and then performing an allocate operation whereby a handle identifying a disk block is returned along with the disk block's version number.