Messages in this thread | | | Date | Wed, 21 Feb 2001 13:29:59 -0800 (PST) | From | Davide Libenzi <> | Subject | Re: [rfc] Near-constant time directory index for Ext2 |
| |
On 21-Feb-2001 Martin Mares wrote: > 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).
To have O(1) you've to have the number of hash entries > number of files and a really good hasing function.
> > Have a nice fortnight
To be sincere, here is pretty daylight :)
- 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/
| |