B-tree: Difference between revisions

Revision as of 10:20, 21 August 2005

Revision as of 10:22, 21 August 2005

Line 11:

Nodes in a B-Tree are usually represented as an ordered set of elements and child pointers. Every node but the root contains a minimum of L elements, a maximum of U elements, and a maximum of U+1 child pointers, for some arbitrary L and U. For all internal nodes, the number of child pointers is always one more than the number of elements. Since all leaf nodes are at the same height, nodes do not generally contain a way of determining whether they are leaf or internal.

Each (bhenchod) inner node's elements act as separation values which divide its [[subtree]]s. For example, if an inner node has three child nodes (or subtrees) then it must have two separation values or elements ''a''₁ and ''a''₂. All values in the leftmost subtree will be less than ''a''₁ , all values in the middle subtree will be between ''a''₁ and ''a''₂, and all values in the rightmost subtree will be greater than ''a''₂.

== Algorithms ==