Re: B trees vs. B+ trees
Date: Sun, 01 Jun 2003 21:36:07 -0700
Message-ID: <3EDAD437.5886_at_nospam_cox.net>
Jerry Gitomer wrote:
> If I remember correctly B trees are balanced trees and B+trees are trees
> with balanced indexes.
B-trees are paged trees that are built from the bottom-up (i.e., rather than choosing the root keys first, and then needing to rearrange the tree when the root turned out to be inappropriate, the root emerges from the data). A page has an "order," or maximum number of entries. Except for the root node, each page also has a minumum number of entries, which is usually half the order. There are then algorithms for splitting and combining pages which keep everything at O(logN) efficiency.
A B+tree facilitates processing the file sequentially by arranging the leaf nodes of the tree into a linked list, which elimiates the need for tree traversals.
Larry Coon
University of California
larry_at_assist.org
and lmcoon_at_home.com
Received on Mon Jun 02 2003 - 06:36:07 CEST