A storage device includes a nonvolatile memory, a cache memory, and a processor configured to load, from the nonvolatile memory into the cache memory, a fragment of each layer of an address mapping corresponding to a target logical address, and access the nonvolatile memory at a physical address mapped from the target logical address, by referring to the fragments of the layers of the address mapping loaded into the cache memory. The layers are arranged in a hierarchy and each layer of the address mapping except for the lowermost layer indicates correspondence between each of segmented logical address ranges mapped in the layer and a physical location of an immediately-lower layer in which said each segmented logical address range is further mapped in a narrower range. The lowermost layer indicates correspondence between each logical address mapped therein and a physical location of the nonvolatile memory associated therewith.