Patent ID: 8583598

Claim:
A method for locating a needed snapshot page mapping of a snapshot, comprising: a) locating a first snapshot mapping retained for a snapshot within a partition of a first level of a plurality of partitioned levels, wherein said levels are adapted for storing snapshot mappings of said snapshot, and wherein said snapshot mappings are stored when a page of said snapshot is copied from a database storage to a snapshot storage, and wherein at least one of said snapshot mappings is a first snapshot mapping retained for said snapshot, and wherein partitions of said first level are populated by said snapshot mappings, and wherein partitions of a subsequent level are populated by copies of said at least one first snapshot mapping from partitions of a previous level, and wherein a last mapping of a partition is linked to a first mapping of a subsequent partition of the same level, and, additionally, wherein said last mapping of a partition not of said last level is linked to a mapping in said subsequent level which immediately follows the last of said copies of said first mappings of said partition not of said last level; b) setting a current snapshot mapping to said first snapshot mapping retained for a snapshot; c) setting a current snapshot mapping to the next snapshot mapping in a current partition if said current snapshot mapping is not the needed snapshot page mapping and said current snapshot mapping is not the last snapshot mapping of said current partition; d) repeating step (c) until said current snapshot mapping is a last snapshot mapping of said current partition, if said current snapshot mapping is not the said needed snapshot page mapping; e) setting said current snapshot mapping to a snapshot mapping linked to in said subsequent level by said last snapshot mapping if said current snapshot mapping is said last snapshot mapping of a partition and said snapshot mapping is in a partition not of said last level; f) setting said current snapshot mapping to a snapshot mapping linked to in said last level by said last snapshot mapping if said current snapshot mapping is the last snapshot mapping of a partition and the snapshot mapping is in a partition of said last level; g) setting said current partition to a partition containing said current snapshot mapping linked to by said last snapshot mapping; h) repeating steps (c)-(g) until the needed snapshot page mapping is located; obtaining a plurality of said needed snapshot mappings for a plurality of said snapshots in a range by repeating steps (a)-(h) for each of said plurality of said snapshots; and obtaining a plurality of said snapshot mappings for said plurality of said snapshots in a range, by repeating steps (a)-(h) wherein in step (e) said first level is treated as said last level between the first mapping retained for the first snapshot in said snapshot range and the first mapping retained for the last snapshot in said snapshot range, then repeating steps (a)-(h), starting with the first mapping retained for the last snapshot of said snapshot range.