Patent ID: 8356021

Claim:
A method for controlling a reduced redundancy storage system to index data in the reduced redundancy storage system, by indexing one or more unique blocks of data processed by the reduced redundancy storage system, the method comprising: creating an index on the reduced redundancy storage system, the index comprising a digital search tree having non-leaf nodes and descendant-free leaf nodes, the digital search tree having keys derived from the unique blocks; where a descendent-free leaf node of the tree comprises a hash table configured to store an index value for a key that falls within the descendent-free leaf node; where the hash table has a fullness splitting threshold, where the threshold for the hash table has a random component; where the non-leaf nodes are stored in a computer random access memory, where an index value comprises the location of a unique block in a unique block pool of the reduced redundancy storage system; where the keys derived from the unique blocks are separate from the index values; and performing a leaf hash table lookup at the end of a binary tree root to leaf traversal of the digital search tree in a single random access disk seek.