A non-volatile memory data address translation scheme is described that utilizes a hierarchal address translation system that is stored in the non-volatile memory itself. Embodiments of the present invention utilize a hierarchal address data and translation system wherein the address translation data entries are stored in one or more data structures/tables in the hierarchy, one or more of which can be updated in-place multiple times without having to overwrite data. This hierarchal address translation data structure and multiple update of data entries in the individual tables/data structures allow the hierarchal address translation data structure to be efficiently stored in a non-volatile memory array without markedly inducing write fatigue or adversely affecting the lifetime of the part. The hierarchal address translation of embodiments of the present invention also allow for an address translation layer that does not have to be resident in system RAM for operation.