Editing B-tree (section)

==Definition==
According to [[Donald Knuth|Knuth]]'s definition, a B-tree of order ''m'' is a tree which satisfies the following properties:{{sfn|Knuth|1998|p=483}}

# Every node has at most ''m'' children.
# Every node, except for the root and the leaves, has at least ⌈''m''/2⌉ children.
# The root node has at least two children unless it is a leaf.
# All leaves appear on the same level.
# A non-leaf node with ''k'' children contains ''k''&minus;1 keys.

Each internal node's keys act as separation values which divide its subtrees. For example, if an internal node has 3 child nodes (or subtrees) then it must have 2 keys: ''a''<sub>1</sub> and ''a''<sub>2</sub>. All values in the leftmost subtree will be less than ''a''<sub>1</sub>, all values in the middle subtree will be between ''a''<sub>1</sub> and ''a''<sub>2</sub>, and all values in the rightmost subtree will be greater than ''a''<sub>2</sub>.

;Internal nodes
: Internal nodes (also known as [[Tree (data structure)#Terminology|inner node]]s) are all nodes except for leaf nodes and the root node. They are usually represented as an ordered set of elements and child pointers. Every internal node contains a '''maximum''' of ''U'' children and a '''minimum''' of ''L'' children. Thus, the number of elements is always 1 less than the number of child pointers (the number of elements is between ''L''−1 and ''U''−1). ''U'' must be either 2''L'' or 2''L''−1; therefore each internal node is at least half full. The relationship between ''U'' and ''L'' implies that two half-full nodes can be joined to make a legal node, and one full node can be split into two legal nodes (if there's room to push one element up into the parent). These properties make it possible to delete and insert new values into a B-tree and adjust the tree to preserve the B-tree properties.
;The root node
: The root node's number of children has the same upper limit as internal nodes, but has no lower limit. For example, when there are fewer than ''L''−1 elements in the entire tree, the root will be the only node in the tree with no children at all.

;Leaf nodes
: In Knuth's terminology, the "leaf" nodes are the actual data objects/chunks. The internal nodes that are one level above these leaves are what would be called the "leaves" by other authors: these nodes only store keys (at most ''m''-1, and at least ''m''/2-1 if they are not the root) and pointers (one for each key) to nodes carrying the data objects/chunks.

A B-tree of depth ''n''+1 can hold about ''U'' times as many items as a B-tree of depth ''n'', but the cost of search, insert, and delete operations grows with the depth of the tree. As with any balanced tree, the cost grows much more slowly than the number of elements.

Some balanced trees store values only at leaf nodes and use different kinds of nodes for leaf nodes and internal nodes. B-trees keep values in every node in the tree except leaf nodes.

===Differences in terminology===
The literature on B-trees is not uniform in its terminology.{{sfn|Folk|Zoellick|1992|p=362}}

Bayer and McCreight (1972),{{sfn|Bayer|McCreight|1972}} Comer (1979),{{sfn|Comer|1979}} and others define the '''order''' of B-tree as the minimum number of keys in a non-root node. Folk and Zoellick{{sfn|Folk|Zoellick|1992|p=363}} points out that terminology is ambiguous because the maximum number of keys is not clear. An order 3 B-tree might hold a maximum of 6 keys or a maximum of 7 keys. Knuth (1998) avoids the problem by defining the '''order''' to be the maximum number of children (which is one more than the maximum number of keys).{{sfn|Knuth|1998|p=483}}

The term '''leaf''' is also inconsistent. Bayer and McCreight (1972){{sfn|Bayer|McCreight|1972}} considered the leaf level to be the lowest level of keys, but Knuth considered the leaf level to be one level below the lowest keys.{{sfn|Folk|Zoellick|1992|p=363}} There are many possible implementation choices. In some designs, the leaves may hold the entire data record; in other designs, the leaves may only hold pointers to the data record. Those choices are not fundamental to the idea of a B-tree.<ref>{{Harvtxt|Bayer|McCreight|1972}} avoided the issue by saying an index element is a (physically adjacent) pair of (''x'',&nbsp;''a'') where ''x'' is the key, and ''a'' is some associated information. The associated information might be a pointer to a record or records in a random access, but what it was didn't really matter. {{Harvtxt|Bayer|McCreight|1972}} states, "For this paper the associated information is of no further interest."</ref>

For simplicity, most authors assume there are a fixed number of keys that fit in a node. The basic assumption is the key size is fixed and the node size is fixed. In practice, variable-length keys may be employed.{{sfn|Folk|Zoellick|1992|p=379}}