Messages in this thread |  | | | Date | Wed, 21 Feb 2001 22:08:35 +0100 | | From | Martin Mares <> | | Subject | Re: [rfc] Near-constant time directory index for Ext2 |
| |
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/
|  |