lkml.org 
[lkml]   [1996]   [Jul]   [26]   [last100]   RSS Feed
Views: [wrap][no wrap]   [headers]  [forward] 
 
Messages in this thread
/
Date
From
SubjectRe: Is any file system on Linux appropriate for very large directories?
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 |
\----------------------------------------------------------/



\
 
 \ /
  Last update: 2005-03-22 13:37    [W:0.102 / U:2.344 seconds]
©2003-2020 Jasper Spaans|hosted at Digital Ocean and TransIP|Read the blog|Advertise on this site