A “grain” is a unit of space allocation in a virtual disk. Grains are represented in physical storage only when used, that is, when they contain data. Grains may be located in storage using an in-memory grain-range table. The grain-range table is derived from a grain table in storage. A grain-range table includes entries for the starting grains of incrementing and or decrementing ranges; grain-table entries that do not start a range are omitted in the grain-range table. Accordingly, a grain-range table can serve as a compressed form of a grain table. This compression makes it feasible to store large numbers of grain-range tables in memory in cases where it would not be feasible to store the corresponding grain tables in memory. As a result, one rather than two storage accesses are require per storage access request, resulting in a substantial performance improvement.