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

Mike Black (
Fri, 26 Jul 1996 06:05:47 -0400

At 05:00 PM 7/25/96 +0100, Matthias Urlichs wrote:
>In, article <>,
> "Michael J. Micek" <> writes:
>> Copious information about skiplists is to be found at
>There's a big problem with skip lists -- they distribute all their data all
>over the place. B*-trees have much better locality.
>Using a skip list, you have to follow the chain of entries on each level to
>find out whether you need to continue, or whether you can proceed to the
>next level. Each follow-the-link, including the last (where you read data
>you can't really use), is one disk read because the entries are rather
>unlikely to be colocated.
>With a B* tree, you need to do exactly one read operation per level, and
>the higher levels are likely to be in cache anyway.
>My conclusion, therefore, is that a skip list is a rather stupid idea when
>you try to apply it to the directory of an on-disk file system.

I guess I may have to go back and re-do my study for query operations too.
My previous testing on skiplists vs b-trees showed skiplists outperformed
b-trees on inserts by a factor of 6 or so and several orders of magnitude
faster at large numbers of inserts. B* trees are horrible at large numbers
of inserts due to rebalancing (which is completely different cache
behaviour). I would think on a news server that nightly cleanup would be a
real pain due to the number of rebalances that would occurr when removing
tens-of-thousand nodes. Somewhere in here we need to balance insert/query

P.S. What was the new mailing list for this subject??? I lost the mail...
| Mike Black 407-676-5118, x203 |
| Computer Science Innovations, Inc. 407-676-2355 FAX |
| Melbourne FL 32904-2314 |