An improved non-volatile memory and logical block to physical block address translation method utilizing a cluster based addressing scheme is detailed. The translation of logical blocks/sectors to the physical blocks/sectors is necessary for a non-volatile memory to appear as a freely rewriteable device to a system or processor. Embodiments of the present invention utilize cluster based address translation to translate logical block addresses to physical block addresses, wherein each cluster contains a plurality of sequentially addressed logical blocks. This allows the use of a smaller RAM table for the address translation lookup and/or faster scanning of the memory device or memory subsystem for the matching cluster address. In one embodiment, a specially formatted cluster is utilized for frequently updated sectors/logical blocks, where the cluster stores a single logical block and a new sequential physical block of the cluster is written in turn with each update.