Patent ID: 8335907

Claim:
A method of maintaining an address table in a memory device, the address table comprising a plurality of main address maps and an update address map, the method comprising: (A) selecting a first main address map from the plurality of main address maps, the first main address map relating to a first logical address range; (B) reading valid main mapping entries from the first main address map and valid update mapping entries from the update address map, where: the valid main mapping entries and the valid update mapping entries specify an address mapping of logical address runs to physical address runs in the memory device; and the valid update mapping entries supersede corresponding invalid main mapping entries; (C) constructing a main mapping set, the main mapping set comprising the valid main mapping entries and the valid update mapping entries; (D) writing the main mapping set to a second main address map of the plurality of main address maps; compacting the update address map when the update address map meets a compaction criterion; calculating an average length of the valid update mapping entries based on a predetermined number of previous executions of the compacting step; comparing the average length to a target length; and performing steps (A)-(D) for a range of logical addresses based on the comparison.