Your post is very reasonable and covers things I've been thinking of too.

My idea for s-s fs was to build it all on the `map` datastructure. Key 0 would store all file pointer (the key of the file metadata).
The metadata entry would contain maybe file name and more, but most importantly which keys (and their order) are used to make up the data of the file.

This would all be very slow, just like you calculated in your post, but it might just be doable with my KeyPointersCache...