🚀 go-pugleaf

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

           _________________25_______________
          /                                  \
    ___ 10,20 ___                        _ 30,40 __
   /      |      \                      /    |     \
5,7,8  13,15,18  22,24             26,27  32,35,38  42,45,46

 


25 deleted:

           _________________24________________
          /                                   \
    ___ 10,18 ___                         _ 30,40 __
   /      |      \                       /    |     \
5,7,8   13,15  20,22                26,27  32,35,38  42,45,46




45 deleted:

           _________________24________________
          /                                   \
    ___ 10,18 ___                         _ 30,40 __
   /      |      \                       /    |     \
5,7,8   13,15  20,22                26,27  32,35,38  42,46
     



24 deleted:

           _________________22_________________
          /                                    \
    ___ 10,18 ___                          _ 30,40 __
   /      |      \                        /    |     \
5,7,8   13,15   ----                 26,27  32,35,38  42,46
                |20|
                ----
underflow _____/  



           _________________22_________________
          /                                    \
        ----                               _ 30,40 __
        |10| <----- underflow             /    |     \
    ___ ---- __                          /     |      \
   /     |     \                        /      |       \
5,7,8  13,15  18,20                  26,27  32,35,38  42,46



           _____________10,22,30,40____________
          /               /  |  \              \
         /               /   |   \              \
        /               /    |    \              \
   5,7,8      13,15,18,20  26,27  32,35,38        42,46

In article <5303@ut-sally.UUCP> ark@sally.UUCP (Arthur M. Keller) writes:
>In article <151@itcatl.UUCP> parris@itcatl.UUCP (Parris Hughes) writes:
>>... I am having problems understanding the B-Tree deletion alogrithm.
>
>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!).

Not necessarily.  For one thing, you shouldn't assume that all useful
B-trees are really indices into data stored external to the B-tree.  If
your records are fairly small, and if there is one key that is the
predominant access path, it makes perfect sense to put the actual records
into the B-tree.  If you need secondary indices, they would be B-trees
which map the secondary key into the primary key which you could then look
up.  This scheme sacrifices secondary index lookup time for primary index
lookup time, which may be what you want.

The other point is that if you don't delete stale records from the B-tree,
the nice logarithmic access time property of B-trees no longer holds.  I
find this particularly insidious when the keys in question are things like
dates of pending orders in a file, so that the file tends to shrink at the
back and grow at the front.  Delete your stale records, you'll be glad you did.

Both left and right hand key compression are useful ways to cram more entries
into a tree node, and there's no argument that in the usual case that it's
more expensive to fetch a node from the disk than to process it once it's read
in, they're a big win.  On the other hand, I have this blindingly fast Eagle
disk drive lashed up to a very sluggish IBM PC, and the tradeoffs are not
always what you'd assume.
-- 
John R. Levine, Javelin Software Corp., Cambridge MA +1 617 494 1400
{ ihnp4 | decvax | cbosgd | harvard | yale }!ima!johnl, Levine@YALE.EDU
The opinions expressed herein are solely those of a 12-year-old hacker
who has broken into my account and not those of any person or organization.

In article <164@ima.UUCP>, johnl@ima.UUCP (John R. Levine) writes:
> Both left and right hand key compression are useful ways to cram more entries
> into a tree node, and there's no argument that in the usual case that it's
> more expensive to fetch a node from the disk than to process it once it's read
> in, they're a big win.  On the other hand, I have this blindingly fast Eagle
> disk drive lashed up to a very sluggish IBM PC, and the tradeoffs are not
> always what you'd assume.

	Actually, I have talked to a couple of different relational
database companies, and their studies indicate that key compression is
not a win. The reason for this is that yes, a disk access is normally
longer than the time necessary to uncompress, but since most of the
bigger systems try to cache the indices, there may not be a disk
access. Then the compression is a straight loss. Of course, compression
would mean you can get more index into the cache, but their studies
seem to argue that compression just does not speed up access time.


-- 

					eric
					...!seismo!umcp-cs!aplcen!osiris!eric