Relay-Version: version B 2.10 5/3/83; site utzoo.UUCP
Path: utzoo!watmath!clyde!caip!ut-sally!ark
From: ark@ut-sally.UUCP (Arthur M. Keller)
Newsgroups: net.database
Subject: Re: Btree Question...
Message-ID: <5303@ut-sally.UUCP>
Date: Sat, 12-Jul-86 05:16:59 EDT
Article-I.D.: ut-sally.5303
Posted: Sat Jul 12 05:16:59 1986
Date-Received: Sun, 13-Jul-86 04:00:53 EDT
References: <151@itcatl.UUCP>
Reply-To: ark@sally.UUCP (Arthur M. Keller)
Organization: U. Texas CS Dept., Austin, Texas
Lines: 39

In article <151@itcatl.UUCP> parris@itcatl.UUCP (Parris Hughes) writes:
>I am building a database manager which uses B-Trees.  My references on
>B-Trees are "Algorithms + Data Structures = Programs" by Wirth, and
>"Searching & Sorting" by Knuth.  I am having problems understanding the
>B-Tree deletion alogrithm.  Given the following 2nd Order B-Tree:

I suggest that the answer is only of `academic' interest.  Because of
fanout considerations (increasing fanout decreases tree height), all
internal (non-leaf) nodes contain keys only for the purposes of
navigation.  All actual database keys appear only in the leaves of the
B-tree (this is technically called a B+-tree (the + is a superscript,
the - is a hyphen)).  This means that internal node keys need not be
actual database keys, and hence are not affected by deletion.  Also,
right end key compression is appropriate to save space (and can even
be a factor when deciding to split a node!).

If you intend your database manager support a relational database, you
probably want multiple B-trees referring to the same collection of
records (presumably one relation).  I have a paper submitted for
publication containing algorithms and data structures for a multiple
B-tree structure that is crash-proof and deadlock-free (for disk block
locks but not for logical record locks) and would be relatively
efficient if coupled with a block cacheing scheme with write-through.
I would be willing to send out advance copies to people who mail me a
message containing their physical (snail) mail address and agree to
send me comments.  I'd especially be interested in hearing from anyone
who plans to implement such algorithms, and I might be persuaded to
spend some time explaining it to such people under some appropriate
circumstances.  An earlier version of these algorithms was prototyped
and the lessons learned were used in developing the approach described
in my paper.

Arthur


-- 
------------------------------------------------------------------------------
Arpanet: ARK@SALLY.UTEXAS.EDU
UUCP:    {gatech,harvard,ihnp4,pyramid,seismo}!ut-sally!ark