Re: Is any file system on Linux appropriate for very large
Mike Black (mblack@csihq.com)
Fri, 26 Jul 1996 06:05:47 -0400
At 05:00 PM 7/25/96 +0100, Matthias Urlichs wrote:
>In linux.dev.kernel, article <199607241957.MAA06475@muddcs.cs.hmc.edu>,
> "Michael J. Micek" <mmicek@muddcs.cs.hmc.edu> writes:
>>
>> Copious information about skiplists is to be found at
>>
>> ftp://ftp.cs.umd.edu/pub/skipLists
>>
>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
operations.
P.S. What was the new mailing list for this subject??? I lost the mail...
-
/----------------------------------------------------------\
| Mike Black mblack@csihq.com 407-676-5118, x203 |
| Computer Science Innovations, Inc. 407-676-2355 FAX |
| Melbourne FL 32904-2314 http://www.csihq.com |
\----------------------------------------------------------/