Patent ID: 8806143

Claim:
A storage system for queuing received write blocks prior to storing the write blocks to a storage device, the storage system comprising: at least one storage device for storing write blocks; and an operating system configured for: receiving a plurality of file block numbers (FBNs) of write blocks for a file; and providing a queuing data structure for representing the received FBNs of the write blocks for the file and queuing the received FBNs prior to storing write blocks corresponding to the received FBNs to the at least one storage device, the queuing data structure comprising at least one node, each node comprising a range field representing an FBN range of at least two FBNs, the range field indicating whether one or more FBNs in the FBN range is in the plurality of received FBNs; and using the queuing data structure, processing the received FBNs of the write blocks for assigning a logical block number (LBN) for each received FBN, the LBN indicating a storage location on a storage device, wherein: the range field comprises X bits, X comprising an integer greater than 1; the number of FBNs represented by the range field is equal to X; each bit in the range field corresponds to an FBN in the FBN range for indicating whether the corresponding FBN is in the plurality of received FBNs; each node in the queuing data structure further comprises a base field for storing a base FBN, the base FBN being within the FBN range; and the values of the FBN range represented by the node are based on the base FBN.