Using structures is definitely a good idea. Losing data is not ideal as the data just before a power loss is probably the most important - however I have worked around this to ensure that when the mains power goes off there is a backup supply that will be able to power the logger for a few seconds (enough to detect a power failure and close the file on sd).
At this stage I am not using interrupts but just sampling as quick as it will let me inside a loop with analogreads. I will need to use interrupts to sample pulses from my digital sensors. Not entirely sure how I go about using interrupts to sample analog channels (timer interrupts?)