Methods and apparatus for efficiently tracking the usage of physical blocks of non-volatile memory are disclosed. According to one aspect of the present invention, a method for maintaining a data structure that stores contents relating to the usage of physical blocks includes determining when to update the contents stored in the data structure, and obtaining a first differential erase count from the data structure when the contents are to be updated. The first differential erase count provides information on a number of times a first physical block has been erased. The method also includes determining a first actual erase count when the contents are to be updated. The first actual erase count is associated with a second physical block, and provides a number of times the second physical block has been erased. Finally, the method includes updating the first differential erase count when the contents are to be updated.