Re: [rfc] Near-constant time directory index for Ext2

From: Martin Mares (mj@suse.cz)
Date: Wed Feb 21 2001 - 16:08:35 EST

Next message: Vojtech Pavlik: "Re: [patch] VIA 4.2x driver for 2.2 kernels"
Previous message: Thomas Lau: "Looking for linux sponser:"
In reply to: Davide Libenzi: "RE: [rfc] Near-constant time directory index for Ext2"
Next in thread: Davide Libenzi: "Re: [rfc] Near-constant time directory index for Ext2"
Reply: Davide Libenzi: "Re: [rfc] Near-constant time directory index for Ext2"
Messages sorted by: [ date ] [ thread ] [ subject ] [ author ]

Hello!

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

Skip list search/insert/delete is O(log N) in average as skip lists are just a
dynamic version of interval bisection. Good hashing is O(1).

Have a nice fortnight

-- 
Martin `MJ' Mares <mj@ucw.cz> <mj@suse.cz> http://atrey.karlin.mff.cuni.cz/~mj/
Entropy isn't what it used to be.
-
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/

Next message: Vojtech Pavlik: "Re: [patch] VIA 4.2x driver for 2.2 kernels"
Previous message: Thomas Lau: "Looking for linux sponser:"
In reply to: Davide Libenzi: "RE: [rfc] Near-constant time directory index for Ext2"
Next in thread: Davide Libenzi: "Re: [rfc] Near-constant time directory index for Ext2"
Reply: Davide Libenzi: "Re: [rfc] Near-constant time directory index for Ext2"
Messages sorted by: [ date ] [ thread ] [ subject ] [ author ]

This archive was generated by hypermail 2b29 : Fri Feb 23 2001 - 21:00:25 EST