Compression and caching for logical-to-physical storage address mapping tables

A method for logical-to-physical address mapping, comprising:

• constructing a mapping table comprising a plurality of table entries, wherein the mapping table is indexed by logical addresses and each of the table entries comprises a corresponding physical address in a storage;
• replacing a first sequence of the plurality of table entries comprising sequential physical addresses with a first compressed mapping table entry in the mapping table to generate a compressed mapping table;
• storing the compressed mapping table in a memory;
• storing a plurality of uncompressed mapping table entries starting at a first location in a cache;
• and
• mapping a first logical address associated with a first uncompressed mapping table entry to the first location in the cache.

A non-transitory, computer-readable storage medium encoded with instructions adapted to be executed by a processor to implement:

• constructing a mapping table comprising a plurality of table entries, wherein the mapping table is indexed by logical addresses and each of the table entries comprises a corresponding physical address in a storage;
• replacing a first sequence of the plurality of table entries comprising sequential physical addresses with a first compressed mapping table entry in the mapping table to generate a compressed mapping table;
• storing the compressed mapping table in a memory, the compressed mapping table correlating logical addresses to locations in a storage;
• storing a plurality of uncompressed mapping table entries starting at a first location in a cache;
• and
• mapping a first logical address associated with a first uncompressed mapping table entry to the first location in the cache.