Quickie file school:
There is an index and there is a file storage area. You put a file(picture, doc whatever) in the storage area and note in the index it uses from spot 1 to 62, then you put another file in and note that uses 63 to 106, etc. as you add files. When you delete the second file the system just changes the first letter of the index entry to a symbol and that frees up spaces 63 to 106 for another use. This process goes on and on as you use the memory card or Hard drive. It gets messy and files start to get broken apart to fill in empty spaces.
When you do a FORMAT however all of that clutter is wiped clean and a new empty index is made so that the miss-mash can start over again.
Software that recovers deleted files just looks for the changed first character in the index and changes it back. IF the memory, in this case 63 to 106, has not been used in the mean time, then the file is recovered.
Total recovery software looks at each and every sector of the memory.