Re: [rfc] [LONG] Near-constant time directory index for Ext2

From: Andreas Dilger (
Date: Thu Feb 22 2001 - 03:31:16 EST

I just wrote:
> I just had a clever idea - on a single-level index you put the header
> and index data in block 0, and put the directory data in the first
> indirect block (11 sparse blocks, instead of 511).

To clarify (with wonderful ASCII art), an un-indexed directory would have
data blocks like:

<d0> <d1> <d2> <d3> (wherever we decide the cutoff is for indexing)

When we start with a single level index, it looks like:

<index header > 0 0 0 0 0 0 0 0 0 0 0 <indirect0>
                                      / | | \
                                  <d0> <d1> ... <dN>

> If you need to go to a second-level index, you can simply shift the
> indirect data block to be a double-indirect block, and start the level-2
> index in the first indirect block.

So it would look like:

<index header > 0 0 0 0 0 0 0 0 0 0 0 <index_indirect> <dindirect0>
                                      / | / \
                               <index0><index1> <indirect0> <indirect1>
                                                    / | | \
                                                <d0> <d1> ... <dN>

> If we ever need a third-level index, you basically do the same thing -
> move the double-indirect blocks to triple-indirect, and put the level-3
> index in the double-indirect block. The index blocks will always fit,
> because the index branching level is 1/2 of the indirect block
> branching because the index has the extra 4-byte hash values.

The benefit is that you don't need to do any copying of directory
block pointers (or contents) when you need to go to the next-level

Cheers, Andreas

Andreas Dilger  \ "If a man ate a pound of pasta and a pound of antipasto,
                 \  would they cancel out, leaving him still hungry?"               -- Dogbert
To unsubscribe from this list: send the line "unsubscribe linux-kernel" in
the body of a message to
More majordomo info at
Please read the FAQ at

This archive was generated by hypermail 2b29 : Fri Feb 23 2001 - 21:00:27 EST