Near-constant time directory index for Ext2
Quoted 3 lines · I just
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>Quoted 3 lines
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>Quoted 5 lines
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
Signature · 3 lines
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