A storage device that maps logical addresses to physical addresses includes a memory that stores machine instructions and a processor coupled to the memory that executes the machine instructions to store a compressed mapping table in the memory. The compressed mapping table correlates logical addresses to locations in a storage. The storage device also stores a bundle of uncompressed mapping table entries starting at a first location in a cache and maps a first logical address associated with the uncompressed mapping table entry to the first location.