Described embodiments provide reconstruction of logical-to-physical address mapping data for one or more sectors of a storage device at startup of a media controller. The sectors of the storage device are organized into blocks and superblocks and the address mapping data is stored in a volatile memory. At a startup condition of the media controller, a buffer layer module of the media controller allocates space in the volatile memory for one or more logical-to-physical address mapping data structures. A media layer module of the media controller determines a block type of each block of the storage device and places each block of the storage device into corresponding groups based on the determined block type of each block. The one or more blocks of each group are processed, and one or more address mapping data structures for the storage device are constructed in the allocated space in the volatile memory.