allbery@ncoast.UUCP (Brandon S. Allbery) (06/10/87)
I have a question about B+trees. Since it's not about DBMS directly, it
doesn't belong in comp.databases; since it's not source, it doesn't belong
in comp.sources.d; I took a wild guess and set Followup-To: poster to
minimize the damage....
Anyway, I've been trying to figure out B+trees given an (inadequate)
description of how they work. I know how to insert items into a B+tree,
but I can't figure out how to delete them. (The reference is Appendix
B of Borland's Database Toolbox, for those interested. I couldn't figure out
the code and don't want to, to avoid license problems.)
As far as I can tell, one deletes an item from a B+tree by:
(1) If it's on a leaf page, delete the item. If not, follow the underflow
pointers on the page pointed to by the key to be deleted and its
descendants, until you hit a leaf page; then move the smallest key on that
page to replace the one being deleted. In eaithr case you end up on a
leaf page.
(2) If this page has (order) or more items in it, you are done. Otherwise,
I get confused; as far as I can tell, you do the following:
(3) Merge the page with the next/previous page, as appropriate. Then move
up to the parent, which now has one fewer page reference, and repeat
from (2).
(4) If there is no previous or next page, this page's parent is the root and
it has only one item in it. Merge the current page with the underflow
page for the root and delete the root.
This makes sense to me, but... Nowhere in this description does "balancing"
take place. The most it does is delete a page, moving its referencing item's
key and all its items into the next lower page, and then sort that page. I
therefore conclude that I am either missing something fundamental to B+trees,
or I'm on the wrong path altogether.
Can someone please mail me a description of the process of deleting a key
from a B+tree, using as few polysyllabic words as possible? (1/2 ;-}) (Things
like this justify my opinion of myself as a merely average programmer.)
Thanks in advance,
++Brandon
--
Copyright (C) 1987 Brandon S. Allbery. Redistribution permitted only if the
redistributor permits further redistribution.
---- Moderator for comp.sources.misc ----
Brandon S. Allbery {decvax,cbosgd}!cwruecmp!ncoast!allbery
aXcess Company {ames,mit-eddie,talcott}!necntc!ncoast!allbery
6615 Center St. #A1-105 necntc!ncoast!allbery@harvard.HARVARD.EDU
Mentor, OH 44060-4101 +01 216 974 9210 (also eddie.MIT.EDU)