Patent ID: 8504792

Claim:
A computer implemented method for implementing a file system, the method comprising: selecting, in response to a request to allocate space for a file within at least one storage device, one of a plurality of tree representations of a bitmap, wherein each bit in the bitmap indicates availability of a block in the at least one storage device; searching one or more nodes of the selected tree representation for a first node whose corresponding set of consecutive bits has a size that matches a number of blocks specified by the request; determining that the first node is not included in the one or more nodes of the selected tree representation; in response to determining, searching the one or more nodes of the selected tree representation for a second node whose corresponding set of consecutive bits has a size that is different from the number of blocks specified by the request, wherein the difference is within a predefined threshold; updating the bitmap to allocate the blocks that correspond to the second node; and synchronizing each tree in the plurality of trees with the updated bitmap.