Why do we need directories on disk? Just prefix all filenames with the directories they reside in. Make '/' just a legitimate filename character. :)
Applied to code, it's really a matter of how you look up names. Prefixing is just the situation where there's no language assistance in looking up names. Namespacing is just prefixes plus some automatic help in looking up partial names.
Yes. With true directories, you can implement directory rename() with O(a+b) time complexity, where a and b are the depths of the paths to the directories. With a flat key/value store, directory rename() requires at least O(n) time complexity for n directory children, since each child must be renamed.
* rename all descendants on directory rename (expensive--takes O(n) time for n descendants).
* log each rename() and translate a key with a new directory name into a key with the original directory name (requires O(k) space for k renames and O(d) time in the worst case for translating a path of depth d whose directories have all been renamed; introduces the need to garbage-collect log records when all descendants of a renamed directory get deleted).
Granted, this is a more nuanced than what I said before about rename() requiring O(n) time complexity when implemented on top of a key/value store, but the second option is still more costly than rename() with true directories. I'm not sure (but cannot prove at this time) that we can do better than the second option above, but would love to hear your thoughts.
Instead of a flat list of file names for each directory, you store the file names in a trie, so that files with a shared prefix in their name have a shared ancestor node in the trie. To do a directory rename, you just have to find the node in the trie that corresponds to the directory, move that node to a different location in the trie and change the portion of the name that is stored in that node.
But then, if they behave like directories, and the software treats them like directories, aren't you effectively implementing directories in everything but name? (I mean, of course current software doesn't actually treat directory names this way; but it seems like changing the data structure is going a long way to maintain a directory-less fiction.)
I think that
$ mkdir -p a/bc; touch a/bc/{d,e}
$ cd a; mv bc Bc
If there are files with names bc, bd and be, `mv b B` now renames all of those to Bc, Bd and Be. With normal directories, there is no way to do that as one operation.
foo.subbar
foo.subduh
foo.submeh
S3 works closer to a key/value store than to a file system.
To be honest my comment was based on OpenStack Object Storage and I can't say if S3 works exactly like that, but being OpenStack kind of a clone I suspect it does.