Messages in this thread | | | Date | Thu, 22 Feb 2001 04:08:57 +0100 | From | Daniel Phillips <> | Subject | Re: [rfc] Near-constant time directory index for Ext2 |
| |
Andreas Dilger wrote: > > Daniel Phillips writes: > > Easy, with average dirent reclen of 16 bytes each directory leaf block > > can holds up to 256 entries. Each index block indexes 512 directory > > blocks and the root indexes 511 index blocks. Assuming the leaves are > > on average 75% full this gives: > > > > (4096 / 16) * 512 * 511 * .75 = 50,233,344 > > > > I practice I'm getting a little more than 90,000 entries indexed by a > > *single* index block (the root) so I'm not just making this up. > > I was just doing the math for 1k ext2 filesystems, and the numbers aren't > nearly as nice. We get: > > (1024 / 16) * 127 * .75 = 6096 # 1 level > (1024 / 16) * 128 * 127 * .75 = 780288 # 2 levels > > Basically (IMHO) we will not really get any noticable benefit with 1 level > index blocks for a 1k filesystem - my estimates at least are that the break > even point is about 5k files. We _should_ be OK with 780k files in a single > directory for a while. Looks like we will need 2-level indexes sooner than > you would think though. Note that tests on my workstation showed an average > filename length of 10 characters (excluding MP3s at 78 characters), so this > would give 20-byte (or 88-byte) dirents for ext3, reducing the files count > to 4857 and 621792 (or 78183 and 40029696 for 4k filesystems) at 75% full.
But you are getting over 3/4 million files in one directory on a 1K blocksize system, and you really shouldn't be using 1K blocks on a filesystem under that big a load. Is it just to reduce tail block fragmentation? That's what tail merging is for - it does a much better job than shrinking the block size.
But if you are *determined* to use 1K blocks and have more than 1/2 million files in one directory then I suppose a 3rd level is what you need. The uniform-depth tree still works just fine and still doesn't need to be rebalanced - it's never out of balance.
-- Daniel - To unsubscribe from this list: send the line "unsubscribe linux-kernel" in the body of a message to majordomo@vger.kernel.org More majordomo info at http://vger.kernel.org/majordomo-info.html Please read the FAQ at http://www.tux.org/lkml/
| |