Example methods, apparatus, and articles of manufacture to access data are disclosed. A disclosed example method involves generating a key-value association table in a non-volatile memory to store physical addresses of a data cache storing data previously retrieved from a data structure. The example method also involves storing recovery metadata in the non-volatile memory. The recovery metadata includes a first address of the key-value association table in the non-volatile memory. In addition, following a re-boot process, the locations of the key-value association table and the data cache are retrieved using the recovery metadata without needing to access the data structure to re-generate the key-value association table and the data cache.