
A Btree of order n is a generalisation of
[23trees],
[234trees]
(and sorttrees) in which each
node has at least ceiling(n/2) elements
and at most n elements.
A Btree is heightbalanced and search, insert and delete
times are O(log_{n}N).
This decreases as n increases.
The Btree is often used in database applications where
the dominant cost is that of reading forks into main memory; once
in main memory, operations are (relatively) fast.
Often, n is determined by the size of elements (or keys)
and the size of one disc block, there being one node per block.
fork: [,k1,,k2,, ..., kn,]
   
   
  v v
 v c2 cn
v c1
c0
k_{i} is the least key in c_{i},
k_{i} < k_{i+1}
leaf: k1,k2, ..., kn
As for the 23tree, if a node is partially full a new child
can be added easily, while maintaining the sortedness property.
If a node should overflow, it is split. A new node is created and
half of the full node copied into it. The new node is
now inserted into the original node's parent; this may cause
further splits. If the root is split then a new root
is created and the Btree grows one level taller.
[,10,,,/,,/,,/]
 
 
 [10,11,12,13]

1,2,,
add 14:
[,10,,13,,,/,,/]
  
  
  [13,14,,]
 
 [10,11,12,]

[1,2,,]
Notes
 Many variations are possible, e.g.
 Data entries "proper"
(i.e. key plus associated information)
can all be placed in external leaf nodes only,
as in the examples above,
in which case the tree is an index into the data proper, or
 data entries can be placed in internal nodes also.
 Splitting of overfull nodes can propagate backwards
up the Btree as far as necessary
(as above, and natural with recursion), or
 nodes that are exactly full can be split on
the way down the tree in case they
would otherwise have had to be split later.
 See
 N. Wirth, Algorithms + DataStructures = Programs,
Prentice Hall 1976, p245, and also
Algorithms and Data Structures,
Prentice Hall 1986, p241.
 R. Sedgewick. Algorithms in C (1st edn),
Addison Wesly 1990, ch18, p262.
 M. A. Weiss. Data Structures and Algorithm Analysis in C,
sec4.7 p133, Addison Wesley, 1997.
 Search for Btree in the
[bibliography].
L. A. 1986,
Department of Computer Science, Monash University, 1984,
and (HTML)
School of Comp Sci and Software Engineering, 1999.

window on the wide world:

