Patent ID: 8140806

Claim:
A method for storing data on a data storage device, the method comprising: providing a non-volatile data storage device comprising a plurality of allocation units for storing data, wherein the non-volatile data storage device employs an indirect addressing scheme to address the plurality of allocation units; receiving a request to store a first data chunk on the non-volatile data storage device; allocating, with a Buddy-Tree algorithm, a first set of allocation units in which to store the first data chunk; storing the first data chunk in the first set of allocation units; receiving a request to store a second data chunk on the non-volatile data storage device; identifying, within the plurality of allocation units, a second set of allocation units sufficient to store the second data chunk; determining that the second set of allocation units comprises at least a portion of the first set of allocation units; identifying, within the plurality of allocation units, a third set of allocation units sufficient to store the first data chunk, wherein the third set of allocation units is exclusive of the second set of allocation units; allocating, with a Buddy-Tree algorithm, the third set of allocation units to hold the first data chunk; relocating the first data chunk to the third set of allocation units; allocating, with a Buddy-Tree algorithm, the second set of allocation units to hold the second data chunk; and storing the second data chunk in the second set of allocation units.