PUBLIC DOMAIN RELAT. DB ? (addendum)

[Marcus J. Ranum]

Martin Boening writes:
>[...] I once saw a system of management
>routines (b+tree) posted on the net which implements a library for building
>DB systems. So you'd have to program you own DB system but you could use 
>the b+tree library to do it.

	Yeah, I wrote that a while back. The B+tree code is oK, and there was
a lame attempt at record management code I wrapped with it that should not be
used if you need speedy updates (I didn't when I wrote it). The B+tree code
doesn't have built-in support for multiple keys (you don't want that anyhow)
and allows you to just store a long value, presumably a disk offset or record
(or indirect record block) number. There are a few changes that could be made
to the B+tree code to speed it up slightly - I had a few revelations after I
wrote it and don't want to attack it again :(    (the current version is
already re-write #4).

	You can get pretty decent access by taking a B+tree (or some other
ordered search tree) that stores a record #, *and* a dbm database, and you
store the key in both, with the record pointer being the dbm datum. You have
to update them both, then, but it's plenty quick, believe me. The B+tree
does at least support variable length keys and user-defined key types.

	The main reason I'd *NOT* recommend my code for writing a "real"
DBMS is because there's no support built into the B+tree code for allowing
concurrent update, or access while the tree is being updated, because of
the way the code recurses down the tree (using an in-memory stack). Doing
that kind of thing "right" is hard, and if you don't do it right, you've
only succeeded in re-writing DBaseIII

mjr.
-- 
"When choosing between two evils, give preference to the council of your
tummy over that of your testes. The history of mankind is full of disasters
that could have been averted by a good meal, followed by a nap on the couch."
		-Me, as explained to me by my wife's cat Strummer.