Re: [PATCH] fstests: generic: Add test of seek in directories

["Theodore Tso" <tytso@mit.edu>]

On Mon, Aug 31, 2026 at 08:22:01AM -0500, NeilBrown wrote:
> Given that the requirements predates the htree design, isn't this "pain
> and performance hit" a deliberate design choice?  Or maybe an
> unfortunate design omission?  Such things can be fixed.

The requirements assumed that the directory was a linear structure,
much like the V7 and BSD FFS structure.  That's why
telldir()/seekdir() interface used a 32-biit cookie --- e.g., a seek
offset.  This doesn't deal well with a b-tree or equivalent structure
where when you insert an item into the tree, the tree might require a
node to be split or the tree to be rebalanced.

> ext4 already has two indexing schemes - indirect and extent-based.  How
> hard would it be to add a third that effectively moved the current
> directory index blocks out of the "file" and into the "file-index"?
> Obviously the 32 block address in dx_entry would need to become a 48 bit
> device address etc, and there are bound to be details I've glossed over,
> but this approach would amortise all metadata access of a lot data
> access, and would allow read-ahead.

The primary detail that you've glossed over is that the tree would
have to be a B-tree.  Ext4 currently uses a b+tree which means that we
don't need to store the file name (key) in the index nodes.  The index
node in the htree is a fixed size, and compact, and this allows for a
much greater fanout (340 nodes in each node).  This makes the tree
much shallower, and reduces the number of seeks when doing lookups.

Switching to a b-tree would almost double the size of the overhead of
the tree, and the tree would be deeper, and thus require more seeks
when doing a lookup.

So it's a tradeoff, and it depends on whether you think readdir or
directory lookups are more frequent.

Cheers,

						- Ted