Methods and arrangements are provided that significantly reduce or otherwise minimize the amount of NVRAM required within a given computing device. For example, a novel data structure and management scheme are provided in a manner that allows an NVRAM sector-based memory to appear as providing significantly more storage space than it physically has. This is accomplished by mapping a higher number of virtual sectors to a fewer number of physical sectors. Data written to a plurality of virtual sectors is compressed and written to physical sector(s). The information needed to associate the virtual and physical sectors can be maintained in a virtual sector table within less expensive RAM. If power is lost and the virtual sector table is no longer available in the RAM, then on power-up the virtual sector table is recreated based in information that is imbedded within the stored data structure in physical sectors of the NVRAM. The scheme promotes data integrity by carefully controlling the compression and decompression processes and providing data and operational step backup information to insure that data within the NVRAM is not lost by a sudden power loss, etc.