In a mostly unrelated article
(seen via Planet Sysadmin) I recently
noticed the following:
readdir(3) just returns the directory entries in the order they are
linked together, which is also not related to inode numbering but as
best as I can tell is from outer leaf inwards (since the most recently
created file is listed first).
On most systems,
readdir(3) is a modestly warmed over
version of the underlying 'read directory entries'
system call, and returns directory entries in the same order that the
system call does. In theory a Unix kernel can return directory entries
in whatever order it wants (including, say, sorted alphabetically). In
practice kernels almost always give you directory entries in what I will
call 'traversal order', whatever the natural order is for entries in the
on-disk data structures that represent a directory.
For a very long time, Unix directories on disk were simple linear
arrays (first with fixed-size entries and then
with variable sized ones when BSD introduced long filenames). When
a new entry was added, it was generally put in the first spot where
there was room; at the end if none of the directory's entries had been
deleted, and perhaps earlier if a filename of a suitable length had
been deleted earlier. The kernel read directories in forward linear
order, starting at the first block of the directory and going up, and so
returned entries in this order.
(In the original simple Unix filesystems, inode numbers were also
allocated in a straightforward 'first free number' order, so the order
of directory entry creation could correspond quite well to inode order.
The Berkeley FFS changed this somewhat by
allocating inodes in a more scattered manner.)
Modern Unix systems commonly use some sort of non-linear directories under at least some circumstances
(a linear data structure may still be more efficient for small
directories); generally these are some variant of balanced trees. The
natural traversal order is tree order, but what that is is very
implementation dependent. I believe it's common to hash filenames and
then insert entries into the tree in hash order, but hashes (and thus
the hash order) vary tremendously between filesystems, and I'm sure that
somewhere there is a filesystem that doesn't hash names and just inserts
them straight in some order.
(Because this is a per-filesystem thing, it follows that the traversal
order can be different for different directories on the same system even
if they have the same entries created in the same order, either because
the directories are using different filesystem types or just because
some parameters were set differently on the different filesystems.)