B-TREES

12/1/2001

B+Trees are logical structures. A B+ tree is a balanced tree (B-tree) that allows terminal ("leaf") nodes to be reached by a series of accesses tracing down the tree. Balanced means that branches differ in "length" by no more than one reference. The plus sign indicates that links are maintained between leaf nodes so that complicated retracing up and down the tree is never required to get to adjacent nodes. Searching B+Trees is much faster than searching an unordered list. Searching B+trees may not be as fast as searching an ordered list. But neither does it require reordering the entire list when elements are added or removed. B+trees are popular because they offer relatively constant, predictable access times to data of known complexity.

Return To Index Copyright 1994-2002 by Donald Kenney.