Patent ID: 7127465

Claim:
A method for operating a data storage system, the method comprising: storing data in one or more cache slots of a random access memory of the data storage system; storing metadata entries in a tree structure in the random access memory of the data storage system, wherein the metadata tree structure includes a plurality of slabs, each slab comprising a metadata table including a plurality of metadata entries representing a contiguous range of block addresses, each entry including a cache pointer to one of the caches slots storing a data block corresponding to a block address within the contiguous range of block addresses; storing a block address range indicator in the metadata table of each slab to indicate the contiguous range of block addresses associated with the metadata entries in the slab; and forming the metadata tree structure by storing at least one slab pointer in the metadata table of each slab, each slab pointer pointing to a parent slab or a child slab in the metadata tree structure.