linux-kernel.vger.kernel.org archive mirror
 help / color / mirror / Atom feed
From: Andreas Dilger <adilger@clusterfs.com>
To: Dave Jones <davej@codemonkey.org.uk>,
	tytso@mit.edu, torvalds@transmeta.com,
	linux-kernel@vger.kernel.org
Subject: Re: [BK PATCH] Add ext3 indexed directory (htree) support
Date: Wed, 25 Sep 2002 15:08:24 -0600	[thread overview]
Message-ID: <20020925210824.GH22795@clusterfs.com> (raw)
In-Reply-To: <20020925204101.GA5420@suse.de>

On Sep 25, 2002  21:41 +0100, Dave Jones wrote:
> On Wed, Sep 25, 2002 at 04:03:44PM -0400, tytso@mit.edu wrote:
> 
>  > This patch significantly increases the speed of using large directories.
>  > Creating 100,000 files in a single directory took 38 minutes without
>  > directory indexing... and 11 seconds with the directory indexing turned on.
> 
> Just curious.. what measurable overhead (if any) is there of indexing
> dirs with smaller numbers of files vs non-indexed ?
> If so, where would be the break-even point ?

No overhead at all for directories 1 block in size.  The htree code uses
the existing "search leaf block" code for such a directory directly.
For directories > 1 block in size, you have the index (1 block
overhead), but also the benefit that you are only searching 1/N of the
blocks for an entry (the leaf block searching code remains the same,
just the "which block to search" code is activated.

So, in summary, htree is never slower than an un-indexed directory, so
there is never really a time when you wouldn't want to use it.

Cheers, Andreas
--
Andreas Dilger
http://www-mddsp.enel.ucalgary.ca/People/adilger/
http://sourceforge.net/projects/ext2resize/


  reply	other threads:[~2002-09-25 21:05 UTC|newest]

Thread overview: 47+ messages / expand[flat|nested]  mbox.gz  Atom feed  top
2002-09-25 20:03 [BK PATCH] Add ext3 indexed directory (htree) support tytso
2002-09-25 20:34 ` Andreas Dilger
2002-09-25 20:41 ` Dave Jones
2002-09-25 21:08   ` Andreas Dilger [this message]
2002-09-25 21:34   ` Theodore Ts'o
2002-09-25 22:54 ` Jeff Garzik
2002-09-25 23:29   ` Theodore Ts'o
2002-09-25 23:45     ` Ryan Cumming
2002-09-26  3:27       ` Theodore Ts'o
2002-09-26  5:23         ` Ryan Cumming
2002-09-26  5:57           ` Theodore Ts'o
2002-09-26  6:22             ` Ryan Cumming
2002-09-26 14:05               ` Theodore Ts'o
2002-09-26  6:25             ` Ryan Cumming
2002-09-26 11:25               ` Daniel Egger
2002-09-26  7:41             ` Ryan Cumming
2002-09-26 13:23               ` Theodore Ts'o
2002-09-26 15:42               ` Theodore Ts'o
2002-09-26 19:08                 ` Ryan Cumming
2002-09-26 19:51                   ` Horst von Brand
2002-09-26 19:59                     ` Ryan Cumming
2002-09-26 22:04                   ` Theodore Ts'o
2002-09-26 22:53                     ` Ryan Cumming
2002-09-26 23:57                       ` Theodore Ts'o
2002-09-27  1:00                         ` Ryan Cumming
2002-09-27  3:24                           ` Theodore Ts'o
2002-09-27  4:12                         ` Andreas Dilger
2002-09-27  7:55                           ` Ryan Cumming
2002-09-28  1:20                           ` Ryan Cumming
2002-09-28  1:46                             ` Ryan Cumming
2002-09-28 14:13                             ` Theodore Ts'o
2002-09-28 14:18                               ` Theodore Ts'o
2002-09-28 22:35                                 ` Ryan Cumming
2002-09-28 17:27                               ` [Ext2-devel] " Andreas Dilger
2002-09-28 18:43                                 ` chrisl
2002-09-28 19:45                                 ` chrisl
2002-09-28 22:30                               ` Ryan Cumming
2002-09-29  7:03                               ` [PATCH] fix htree dir corrupt after fsck -fD chrisl
2002-09-29  8:16                                 ` Ryan Cumming
2002-09-29  8:36                                   ` Ryan Cumming
2002-09-30  2:46                                   ` Ryan Cumming
2002-09-29 14:13                                 ` Theodore Ts'o
2002-09-25 23:31 ` [BK PATCH] Add ext3 indexed directory (htree) support Daniel Egger
2002-09-26  0:32   ` Randy.Dunlap
2002-09-26  0:50 ` Aaron Lehmann
2002-09-26  3:28   ` Theodore Ts'o
2002-10-02  9:11 tytso

Reply instructions:

You may reply publicly to this message via plain-text email
using any one of the following methods:

* Save the following mbox file, import it into your mail client,
  and reply-to-all from there: mbox

  Avoid top-posting and favor interleaved quoting:
  https://en.wikipedia.org/wiki/Posting_style#Interleaved_style

* Reply using the --to, --cc, and --in-reply-to
  switches of git-send-email(1):

  git send-email \
    --in-reply-to=20020925210824.GH22795@clusterfs.com \
    --to=adilger@clusterfs.com \
    --cc=davej@codemonkey.org.uk \
    --cc=linux-kernel@vger.kernel.org \
    --cc=torvalds@transmeta.com \
    --cc=tytso@mit.edu \
    /path/to/YOUR_REPLY

  https://kernel.org/pub/software/scm/git/docs/git-send-email.html

* If your mail client supports setting the In-Reply-To header
  via mailto: links, try the mailto: link
Be sure your reply has a Subject: header at the top and a blank line before the message body.
This is a public inbox, see mirroring instructions
for how to clone and mirror all data and code used for this inbox;
as well as URLs for NNTP newsgroup(s).