lkml.org 
[lkml]   [1996]   [Jul]   [25]   [last100]   RSS Feed
Views: [wrap][no wrap]   [headers]  [forward] 
 
Messages in this thread
/
From
SubjectRe: Is any file system on Linux appropriate for very large directories?
Date

Torvalds:

> >What makes especially insert so non-trivial is not so much the actual
> >operations themselves, but the fact that you no longer operate on a local
> >scale: one modification may modify a noticeable amount of the directory.

Black:

> have found skip lists to be immensedly (order of magnitude or so) faster
> than B-Trees. Skip lists are easy-to-write and operate on a local scale.

Uh... local-ish... you still have to update all the pointers
(cardinality of which set being the level of the new entry)
that point to the new record. Of course, maybe I don't
understand what's meant exactly by "local".

Still, they look pretty simple to implement. (And the fact
that the new level is random would have interesting effects...
it can be determined ahead of time; it can be reduced to
fit...)

> A paper with more detail is at http://www.csihq.com/analysis/skiplist.html

Copious information about skiplists is to be found at

ftp://ftp.cs.umd.edu/pub/skipLists

--
Michael J. Micek, peripatetic philosopher. (currently) mmicek@muddcs.cs.hmc.edu


\
 
 \ /
  Last update: 2005-03-22 13:37    [from the cache]
©2003-2011 Jasper Spaans