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

Matthias Urlichs (
Fri, 26 Jul 1996 19:11:59 +0100


In, article <>,
Mike Black <> writes:
> I guess I may have to go back and re-do my study for query operations=
> My previous testing on skiplists vs b-trees showed skiplists outperfo=
> b-trees on inserts by a factor of 6 or so and several orders of magni=
> faster at large numbers of inserts.=20

Remember you've been doing your study on in-memory data, not on on-disk
data. You might want to add some heuristics to simulate accesses to dis=
storage (simpleminded approach: for each page, add a pseudorandom numbe=
to the access time. The number should grow with the time elapsed since =
page was accessed last).

If you have your test programs readily available, I'd like to have a co=

> B* trees are horrible at large numbers
> of inserts due to rebalancing (which is completely different cache
> behaviour).=20

Why would a rebalance operation be necessary after an insert?

> 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 remo=
> tens-of-thousand nodes. Somewhere in here we need to balance insert/=
> operations.

Hmm, you're right -- but at worst, that's writing two pages for each le=
we have. With skip lists you need to write once per level. My empirical
thinking says that with skip lists you'd need more levels than with a B=
tree of the same magnitude, but I didn't test that yet.

> P.S. What was the new mailing list for this subject??? I lost the ma=

Obviously, I don't know it either. :-/

Boy, n.:
A noise with dirt on it.
Matthias Urlichs \ noris network GmbH / Xlink-POP N=FCrnberg=
Schleiermacherstra=DFe 12 \ Linux+Internet / EMail: urlichs@nor=
90491 N=FCrnberg (Germany) \ Consulting+Programming+Networking+etc=
PGP: 1024/4F578875 1B 89 E2 1C 43 EA 80 44 15 D2 29 CF C6 C7 E0 D=
Click <A HREF=3D"">here</A>. =