Provided are an apparatus, system and method for using a validity table indicating whether physical addresses have valid data to optimize write and defragmentation operations. A non-volatile memory storage device has non-volatile memory and a main memory. A memory controller reads and writes to the non-volatile memory and maintains in the main memory a logical-to-physical address table indicating, for each logical address of a plurality of logical addresses, a physical address in the non-volatile memory having data for the logical address. The main memory maintains a validity table indicating for each physical address of a plurality of physical addresses in the non-volatile memory whether the physical address has valid data.