Theodore Tso [off-list ref] writes:

Certainly one of the things that we could consider is for small
directories to do an in-memory sort of all of the directory entries at
opendir() time, and keeping that list until it is closed.  We can't do
this for really big directories, but we could easily do it for
directories under 32k or 64k.

I assume you mean sort by inode, because sort by htree key would
be as bad as htrees.

But wouldn't that break parallel readdir for a directory that just grows
from <32/64K to over it?  e.g. if the sort moves already read 
entries to after the  cursor readdir would return some entries twice.

I suspect you would need to keep it always sorted after that no matter
how big it gets. So the 32/64k boundary seems useless and you would
need a sorted potentially partial in memory rbtree anyways.

-Andi