Re: B trees vs. B+ trees

From: Larry Coon <lmcoon_at_nospam_cox.net>
Date: Sun, 01 Jun 2003 21:36:07 -0700
Message-ID: <3EDAD437.5886@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 Sun Jun 01 2003 - 23:36:07 CDT