Patent ID: 8244691

Claim:
A method of de-duplicating a volume of data, the method comprising: for each of a plurality of input segments within the volume of data, traversing nodes of a search tree within a storage medium in accordance with the value of a fixed-size portion of the input segment to determine if the search tree contains a pointer to a matching fixed-sized portion of a segment within a dictionary; and if the search tree contains the pointer: comparing the input segment with the segment within the dictionary pointed to by the pointer; substituting a token representative of the segment within the dictionary for at least part of the input segment determined to match the segment within the dictionary; wherein traversing the nodes of a search tree comprises traversing the nodes of a first search tree to obtain a plurality of codes that correspond respectively to a plurality of units of data within the fixed-size portion of data; wherein traversing the nodes of a search tree further comprises concatenating at least two of the codes that correspond to the plurality of units of data to synthesize a first search value and traversing the nodes of a second search tree to obtain a value that indicates a storage location of the matching fixed-size portion of the segment within the dictionary; and wherein traversing the nodes of a second tree to obtain a value that indicates a storage location of the matching fixed-size portion of the segment within the dictionary comprises traversing the nodes of the second tree to obtain an additional plurality of codes that correspond to plurality of units of data.