Editing B-tree (section)

===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}}