Each storage device's data starts at address "0"
with a table of contents, listing all files
and directories that are stored on it.
For each item, the table of contents lists:
- the ID of its parent directory ("0" = root)
- the directory ID (starting at "1"), if not a file
- its name (with an optional type extension)
- the start address of a file's data
- the length (size) of a file in bytes
and, depending on the operating system:
- a read-only protection flag
- user-group access flags (or "system", "hidden", etc)
- date/time records for "last changed" and
maybe also "created", "last opened", and so on.
To minimize access times, energy consumption
and mechanical stress for physical drives,
the table of contents may be segmented and contain
fast-lookup data, depending on the operating system.
It also records the overall sum of all the bytes
used by all files together, so it is always known
how much free memory spae is still available.
When your computer lists the contents of the root,
it reads the table of contents and scans it for
all items that have the parent ID set to "0".
When it lists the contents of another directory,
it scans the table of contents for all items that
have its directory ID set as their parent ID.
When you delete a file, the operating system will
typically just remove its entry in the table of contents,
while the file data remains untouched on the
storage device until overwritten by a new file.
This is why lost files can sometimes still be
recovered by software that scans for file data
that has no table-of-contents entry.
When you move a file within the same storage device,
only its parent ID gets changed in the table of contents,
which is why moving happens instantly in this case.
But when you copy a file, the whole file data
needs to be scanned and copied,
which may take a bit for huge files.
Moving a file from one storage device to another
first copies the file (slow) and then deletes it (fast)
from the original location.
The operating system may partition storage devices
into various "virtual" storage devices which then each
get their own table of contents. Moving files from
one partition to another then is as slow as with
physical drives, as it likewise has to copy and delete.
When files get deleted, unused "holes" of storage space
are the result. A smaller hole is created when a file is
updated (save changes) with a reduced size.
And when a file is updated with an increased size,
the operating system may write it all new to an unused
region of the storage device and set its start address
to that, leaving the old file data location as a hole.
The user can run a utility program to defragment
the file system, which re-arranges all file data so that
no holes are left after — which with all the copying of
file data and updating tthe table of contents takes
a very long time, of course.
The file system may even fragment individual files
by storing them as part-blocks that each may
rest in different regions on the storage device
(adding another layer of structure information
on top of the table of contents), which is
also unwoven by defragmenting.