Re: Is any file system on Linux appropriate for very large directories?

Michael J. Micek (
Wed, 24 Jul 1996 12:57:50 -0700 (PDT)


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


> 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

> A paper with more detail is at

Copious information about skiplists is to be found at

Michael J. Micek, peripatetic philosopher. (currently)