Patent ID: 8176013

Claim:
A method of merging a first storage device into a plurality of storage devices, the method comprising: querying, by a processor of a first storage device of a plurality of storage devices, the other storage devices for an indication as to the current version of one or more portions of a mirrored index data structure, the mirrored index data structure stored across the storage devices and comprising: a plurality of nodes comprising: a root node; at least one copy of the root node, wherein the root node and the copy of the root node are stored on different storage devices of the plurality of distributed storage devices; a plurality of child nodes beneath the root node in the hierarchy referencing one or more index nodes or indexed data; and at least one copy of each child node of the plurality of child nodes, wherein each child node of the plurality of child nodes and its respective copy are stored on different storage devices of the plurality of storage devices, wherein the root node and the plurality of child nodes form a first index tree and the at least one copy of the root node and the at least one copy of each child node form at least one mirror copy of the first index tree; determining, by a processor of the first storage device and based on the indication as to the current version, whether the first storage device is storing the current version of the one or more portions; if the first storage device is not storing the current version of the one or more portions, updating the first storage device to store the current version of the one or more portions; and removing from the first storage device one or more nodes of the plurality of nodes which are not referenced by the current version of the one or more portions but are stored on the first storage device.