Message-ID: <XFMail.20010221092103.davidel@xmailserver.org>
Content-Type: text/plain; charset=us-ascii
Content-Transfer-Encoding: 8bit
MIME-Version: 1.0
In-Reply-To: <01022020011905.18944@gimli>
Date: Wed, 21 Feb 2001 09:21:03 -0800 (PST)
From: Davide Libenzi <davidel@xmailserver.org>
To: Daniel Phillips <phillips@innominate.de>
Subject: RE: [rfc] Near-constant time directory index for Ext2
Cc: ext2-devel@lists.sourceforge.net, hch@ns.caldera.de,
        Andreas Dilger <adilger@turbolinux.com>, tytso@valinux.com,
        Linux-kernel@vger.kernel.org
Sender: linux-kernel-owner@vger.kernel.org


On 20-Feb-2001 Daniel Phillips wrote:
> Earlier this month a runaway installation script decided to mail all its
> problems to root.  After a couple of hours the script aborted, having
> created 65535 entries in Postfix's maildrop directory.  Removing those
> files took an awfully long time.  The problem is that Ext2 does each
> directory access using a simple, linear search though the entire
> directory file, resulting in n**2 behaviour to create/delete n files. 
> It's about time we fixed that.
> 
> Last fall in Miami, Ted Ts'o mentioned some ideas he was playing with
> for an Ext2 directory index, including the following points:
> 
>   - Fixed-size hash keys instead of names in the index
>   - Leaf blocks are normal ext2 directory blocks
>   - Leaf blocks are sequental, so readdir doesn't have to be changed

Have You tried to use skiplists ?
In 93 I've coded a skiplist based directory access for Minix and it gave very
interesting performances.
Skiplists have a link-list like performance when linear scanned, and overall
good performance in insertion/seek/delete.


- Davide

-
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/