Patent ID: 8051050

Claim:
A data de-duplication method for a data storage system, the data storage system having a data repository, the data repository storing data segments in a plurality of groups, the method comprising: providing a data segment to be stored in the data storage system in association with a write request, the write request identifying a virtual volume address; generating a group identifier in response to the data segment and a hash algorithm, each of a plurality of groups being identifiable by one of a corresponding plurality of group identifiers, each group comprising one or more indexes in the data repository, each index indicating a storage location for a data segment in the data repository; determining if a corresponding group in the data repository exists in response to the generated group identifier and a hash tree, each existing group corresponding to a leaf of the hash tree; if no corresponding group is determined to exist in the data repository in response to the generated group identifier, storing the data segment in the data repository in a new group; and if a corresponding group is determined to exist in the data repository in response to the generated group identifier, storing the data segment in the data repository in response to a search of the corresponding group for a stored data segment matching the data segment to be stored.