This functionality does not exist to my knowledge.
ext4 and XFS return directory entries in pseudo-random order (due to hashing), not lexicographically.
For an example, see e.g. https://righteousit.wordpress.com/2022/01/13/xfs-part-6-btre...
If you know a way to return lexicographical order directly from the file system, without the need to sort, please link it.
You can maybe use “d_off” with readdir in some way, but that’s specific to the filesystem. There’s no portable way to do this with POSIX.
Regardless of if you can do it with a single directory, you can’t do it for all files recursively under a given prefix. You can’t just ignore directories, or say that “for this list request, ‘-‘ is my directory separator”.
The use of b-trees in file systems is completely beside the point.
But as you say, there are filesystem-specific methods or operating-system specific methods to reach the true performance of the filesystem.
It is likely that for maximum performance one would have to write custom directory search functions using directly the Linux syscalls, instead of using the standard libc functions, but I would rather do that instead of paying for S3 or something like it.
The question isn’t if it’s possible, because of course it is, the question is if it’s portable and well supported with the POSIX interface. Because if it’s not, then…
Where did this goalpost come from? S3 is not portable or POSIX compliant.
Therefore they do not get slower proportional to the number of entries and listing based on file prefixes is extremely fast.