Patent ID: 8495111

Claim:
A storage system comprising: one or more storage devices including a plurality of storage entities; memory storing program instructions; and one or more processors, wherein the program instructions are executable by the one or more processors to create a hierarchical entry tree comprising a plurality of levels describing the plurality of storage entities, wherein at a given level of the plurality of levels of the tree above a bottom level, storage entity metadata entries indicate where contiguous, unallocated storage entities available for allocation are located at each level below the given level; wherein the program instructions are further executable by the one or more processors to: receive a request to store data of a target size at a target location within the plurality of storage entities corresponding to a first portion of the entry tree; scan the entry tree to determine if contiguous, unallocated storage entities of the target size are available at the target location; determine that contiguous, unallocated storage entities of the target size are not available at the target location; and in response to said determining that contiguous, unallocated storage entities of the target size are not available at the target location: scan portions of the entry tree outside the first portion to identify contiguous, unallocated storage entities of the target size; and store the data in the identified storage entities.