Search code examples
b-treeb-plus-tree

What is a B* tree and how does it differ from a B tree and a B+ tree?


I can't seem to find a solid answer of what B* tree is. I am aware that a B tree stores both keys and data in its internal and leaf nodes and B+ tree stores keys in its interior nodes and data in its leaf nodes but how is B* tree different?


Solution

  • Straight from Wikipedia:

    The B*-tree balances more neighboring internal nodes to keep the internal nodes more densely packed (Comer 1979, p. 129). This variant requires non-root nodes to be at least 2/3 full instead of 1/2 (Knuth 1998, p. 488). To maintain this, instead of immediately splitting up a node when it gets full, its keys are shared with a node next to it. When both nodes are full, then the two nodes are split into three. The act of deleting nodes is somewhat more complex than inserting however.