The key difference between lexicographically keyed flat hierarchies, and directory-nested filesystem hierarchies, becomes clear based on this example:
dir1/a/000000
dir1/a/...
dir1/a/999999
dir1/b
On a proper hierarchical file file system with directories as tree interior nodes, `ls dir1/` needs to traverse and return only 2 entries ("a" and "b").
A flat string-indexed KV store that only supports lexicographic order, without special handling of delimters, needs to traverse 1 million dirents ("a/00000" throuh "a/999999") before arriving at "b".
Thus, simple flat hierarchies are much slower at listing the contents of a single dir:
O(all recursive children), vs. O(immediate children) on a "proper" filesystem.
Lexicographic strings cannot model multi-level tree structures with the same complexities; this may give it the reputation of "listing files is slow".
UNLESS you tell the listing algorithm what the delimter character is (e.g. `/`).
Then a lexicographical prefix tree can efficiently skip over all subtrees at the next `/`.
S3 has no rename or move operation.
Renaming is CopyObject and then DeleteObject.
CopyObject takes linear time to the size of the file(s).
This comes up fairly often when someone has written a lot of files
to the wrong place - moving the files back is very slow.
This is right:
In a normal file system, renaming a directory is fast O(1), in S3 it's slow O(all recursive children).
And Amazon S3 has not added a delimiter-based function to reduce its complexity, even though that would be easily possible in a lexicographic prefix tree (re-rooting the subtree).
So here the original post has indeed found a case where S3 is much slower than a normal file system.
A flat string-indexed KV store that only supports lexicographic order, without special handling of delimters, needs to traverse 1 million dirents ("a/00000" throuh "a/999999") before arriving at "b".
Thus, simple flat hierarchies are much slower at listing the contents of a single dir: O(all recursive children), vs. O(immediate children) on a "proper" filesystem.
Lexicographic strings cannot model multi-level tree structures with the same complexities; this may give it the reputation of "listing files is slow".
UNLESS you tell the listing algorithm what the delimter character is (e.g. `/`). Then a lexicographical prefix tree can efficiently skip over all subtrees at the next `/`.
Amazon S3 supports that, with the docs explicitly mentioning "skipping over and summarizing the (possibly millions of) keys nested at deeper levels" in the `CommonPrefixes` field: https://docs.aws.amazon.com/AmazonS3/latest/userguide/using-...
I have not tested whether Amazon's implemented actually saves the traversal (or whether it traverses and just returns less results), but I'd hope so.