Messages in this thread |  | | | Date | Wed, 21 Feb 2001 09:21:03 -0800 (PST) | | From | Davide Libenzi <> | | Subject | RE: [rfc] Near-constant time directory index for Ext2 |
| |
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/
|  |