Article View: net.database
Article #224Btree Question...
From: Parris Hughes
Date: Wed, 09 Jul 1986 13:13
Date: Wed, 09 Jul 1986 13:13
23 lines
1618 bytes
1618 bytes
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
Technical Details
Message-ID:
<151@itcatl.UUCP>Path:
arc1-ca.pugleaf.net!utzoo!watmath!clyde!cbatt!cbosgd!gatech!itcatl!parrisShow Full Headers
Complete Article Headers
Relay-Version: version B 2.10 5/3/83; site utzoo.UUCP Path: arc1-ca.pugleaf.net!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