For systems that store information using segments that are deduplicated, an index is used to identified whether the segment has been previously stored and where a given segment is stored. However, as the storage systems increase in the number of segments that are stored, the index also increases in size, and it becomes more and more time consuming to locate a received segment's entry or not in the index.