1. A method performed on a computing device, the method comprising: allocating, by the computing device, portions of storage space on a storage device according to levels of a hierarchy and nodes of the levels, where each level represents a different granularity of the storage space, where each level comprises its corresponding nodes, where each node represents a region of the storage space, and where each node indicates: a size of the region, a number of allocation units in the region, a size of each allocation unit, and a largest contiguous size of non-allocated space in the region.