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

[Andreas Dilger <adilger@turbolinux.com>]

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
index.

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?"
http://www-mddsp.enel.ucalgary.ca/People/adilger/               -- Dogbert