B*-tree
From Free net encyclopedia
A B*-tree is a tree data structure, a variety of B-tree, which requires nonroot 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. The term is not in general use today; 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 form of a linked list. That is efficient for searching at the cost of a more expensive insertion.
Template:Compu-sci-stubde:B*-Baum
[edit]