B*-tree

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.

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.^[1]