Relay-Version: version B 2.10 5/3/83; site utzoo.UUCP
Path: utzoo!watmath!clyde!cbatt!cbosgd!gatech!itcatl!parris
From: parris@itcatl.UUCP (Parris Hughes)
Newsgroups: net.database
Subject: Btree Question...
Message-ID: <151@itcatl.UUCP>
Date: Wed, 9-Jul-86 09:13:31 EDT
Article-I.D.: itcatl.151
Posted: Wed Jul  9 09:13:31 1986
Date-Received: Thu, 10-Jul-86 05:05:36 EDT
Organization: Interactive Technology Corporation,  Atlanta, Georgia
Lines: 23

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:
		   ____________ 25 ______________
		  /                              \
	    ___ 10,20 ___		      _ 30,40 __
           /      |      \                   /    |     \
      5,7,8   13,15,18  22,24		26,27  32,35,38  42,45,46

delete keys 25, 45, and 24.  According to Wirth, the resultant B-Tree should
be:
	       ________________	10,22,30,40 __________________
              /            ______/   |  \______               \
             /            /          |         \               \
	5,7,8	13,15,18,20	   26,27	32,35,38	42,46

Could someone please email me the intervening forms the tree takes (i.e.,
after deleting 25, then after deleting 45)?  My result looks totally
different (still three levels;  don't want to waste resources posting it).
Any help would be most appreciated.  Thanks for reading this far.

Parris			....gatech!itcatl!parris