lkml.org 
[lkml]   [2001]   [Feb]   [21]   [last100]   RSS Feed
Views: [wrap][no wrap]   [headers]  [forward] 
 
Messages in this thread
    /
    Date
    From
    SubjectRe: [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/

    \
     
     \ /
      Last update: 2005-03-22 13:17    [W:5.255 / U:0.068 seconds]
    ©2003-2020 Jasper Spaans|hosted at Digital Ocean and TransIP|Read the blog|Advertise on this site