Dunno how it happens these days, but in the past deleting a file in x86 meant changing the first character of the file name by DOS and thus mark that space for furtehr writing. And no you cant simply do it yourself. If you were to diskedit the disk you'd see the same. So what the undelete s/w back then did was to ask you for the first char and then, iff the file hadn't been overwritten (ie all the clusters are there) it would simply write the new char.
Formatting is a little different, it recreates the file structure (FAT). Here for safety purposes there's a second copy of the FAT. All this is under DOS (x86).
Dunno abt the rest. Any takes guys?