In linux.dev.kernel, article <1.5.4.32.19960726100547.008d9cbc@picard.c=
sihq.com>,
Mike Black <mblack@csihq.com> writes:
>=20
> 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 outperfo=
rmed
> b-trees on inserts by a factor of 6 or so and several orders of magni=
tude
> 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=
k
storage (simpleminded approach: for each page, add a pseudorandom numbe=
r
to the access time. The number should grow with the time elapsed since =
that
page was accessed last).
If you have your test programs readily available, I'd like to have a co=
py.
> 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=
ving
> tens-of-thousand nodes. Somewhere in here we need to balance insert/=
query
> operations.
Hmm, you're right -- but at worst, that's writing two pages for each le=
vel
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=
il...
Obviously, I don't know it either. :-/
--=20
Boy, n.:
A noise with dirt on it.
--=20
Matthias Urlichs \ noris network GmbH / Xlink-POP N=FCrnberg=
=20
Schleiermacherstra=DFe 12 \ Linux+Internet / EMail: urlichs@nor=
is.de
90491 N=FCrnberg (Germany) \ Consulting+Programming+Networking+etc=
'ing
PGP: 1024/4F578875 1B 89 E2 1C 43 EA 80 44 15 D2 29 CF C6 C7 E0 D=
E
Click <A HREF=3D"http://info.noris.de/~smurf/finger">here</A>. =
42