Robust index storage for non-volatile memory

A method of updating a hierarchal address translation data structure containing two or more Tables/data structures arranged in a hierarchal data tree and storing address translation data entries used to translate a logical address to a physical address, comprising:

• traversing up the hierarchal address translation data structure, starting with a Table storing a changed address translation data entry, the traversing further comprising:
• checking if update space remains in a current Table/data structure of a current level of the hierarchal address translation data structure;
• updating the changed address translation data entry when update space is available, and ending the update of the hierarchal address translation data structure;
• creating a new Table/data structure when the changed address translation data entry cannot be updated in the current Table/data structure;
• copying the most-current address translation data entries to the new Table/data structure;
• ending the update of the hierarchal address translation data structure if the current Table/data structure is at a top level of the hierarchal address translation data structure;
• traversing up to a next level of the hierarchal address translation data structure when the current Table/data structure is not at the top level of the hierarchal address translation data structure;
• and
• repeating updating on a parent Table/data structure of the next level to change an address translation data entry in the parent Table/data structure from the current to the new Table/data structure.

A method of abstracting logical addresses to physical addresses of a memory device utilizing an address translation layer, comprising:

• looking up a logical address with an address translation table and translating the logical address to a logical erase block ID;
• translating the logical erase block ID to a physical erase block ID utilizing a Logical to Physical Erase Block Translation Table;
• and
• updating the Logical to Physical Erase Block Translation Table due to moving or reclaiming an erase block where updating the Logical to Physical Erase Block Translation Table comprises checking if update space remains in a changed erase block translation data entry of the Logical to Physical Erase Block Translation Table, updating the changed data entry when update space is available and ending the update of the Logical to Physical Erase Block Translation Table, creating a new Logical to Physical Erase Block Translation Table when the changed data entry cannot be updated in the current Logical to Physical Erase Block Translation Table, and copying the most-current data entries to the new Logical to Physical Erase Block Translation Table.