Patent ID: 8457018

Claim:
A method for managing data commonality in a storage system using a Merkle tree having nodes with associated reference counts, comprising: deleting an object; determining the blocks of the object, wherein the blocks include deduplicated data blocks, wherein the deduplicated data blocks are deduplicated by applying a hash function to create signatures and the created signatures are stored in a hash index; determining a root node of the object based on the determined blocks, wherein the root node maps data commonality across multiple objects; decrementing the reference count of the root node, wherein decrementing the reference count of the root node includes decrementing the reference count of the root node to zero; removing the root node from the Merkle tree; decrementing the reference count of a child node of the removed root node; and removing the child node if the reference count of the decremented child node is zero; and decrementing the reference count of a child of the removed child node.