B*-tree

From Wikipedia, the free encyclopedia

It has been suggested that this article or section be merged into B-tree. (Discuss)

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]

[edit] Variants

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]

[edit] References

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. http://ieeexplore.ieee.org/xpls/abs_all.jsp?arnumber=315364. Retrieved 2007-02-17. 

[edit] External links

• Dictionary of Algorithms and Data Structures entry for B*-tree

v • d • e Trees in Computer Science Binary trees Binary search tree (BST) · Van Emde Boas tree · Cartesian tree · Top Tree · T-tree Self-balancing binary search trees Red-black tree · AVL tree · AA tree · Splay tree · Scapegoat tree · Treap B-trees B+ tree · B*-tree · UB-tree · 2-3 tree · 2-3-4 tree · (a,b)-tree · Dancing tree · Htree · Bx-tree Tries Suffix tree · Radix tree · Ternary search tree Binary space partitioning (BSP) trees Quadtree · Octree · kd-tree (implicit) · VP-tree Non-binary trees Exponential tree · Fusion tree · Interval tree · PQ tree · Range tree · SPQR tree Trees used in computer graphics R-tree · X-tree · Segment tree Other trees Heap · Hash tree · Finger tree · Metric tree · Cover tree · BK-tree · Doubly-chained tree · Expectiminimax tree · iDistance

This data structure-related article is a stub. You can help Wikipedia by expanding it. v • d • e