The Full Wiki

More info on B*-tree

B*-tree: Wikis


Note: Many of our articles have direct quotes from sources you can cite, within the Wikipedia article! This article doesn't yet, but we're working on it! See more info or our list of citable articles.


From Wikipedia, the free encyclopedia

A B*-tree is a tree data structure, a variety of B-tree used in the HFS and Reiser4 file systems, which requires non-root nodes to be at least 2/3 full instead of 1/2. To maintain this, instead of immediately splitting up a node when it gets full, its keys are shared with the node next to it. When both are full, then the two of them are split into three. It also requires the 'leftmost' key never to be used.

The term is not in general use today as the implementation was never looked on positively by the computer science community-at-large; most people use "B-tree" generically to refer to all the variations and refinements of the basic data structure.

Some modern uses for B*-trees are in floorplanning problems for ICs.[1]


A B*-tree should not be confused with a B+ tree, which is one where the leaf nodes of the tree are chained together in the form of a linked list. That is efficient for searching at the cost of a more expensive insertion.

There is also a B**-tree defined by an academic professor listed in the IEEE 0-8186-4212-2 1993.[2]


  1. ^ [1] Y. Chang, Y. Chang, G. Wu, and S. Wu, "B•-Trees: a new representation for non-slicing floorplans," Proceedings of the 37th conference on Design automation, ACM New York, NY, USA, 2000, p. 458–463.
  2. ^ Anestis A. Toptsis (1993-05-27). "B**-tree: a data organization method for high storage utilization". Computing and Information, 1993. Proceedings ICCI '93.. Sudbury, Ontaro, Canada. pp. 277–281. ISBN 0-8186-4212-2. Retrieved 2007-02-17.  

External links



Got something to say? Make a comment.
Your name
Your email address