A B-tree of order n is a generalisation of
(and sort-trees) in which each
node has at least
and at most n elements.
A B-tree is height-balanced and search, insert and delete
times are O(lognN).
This decreases as n increases.
The B-tree is often used in data-base 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
ki is the least key in ci,
ki < ki+1
leaf: k1,k2, ..., kn
As for the 2-3-tree, 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 B-tree grows one level taller.
| | |
| | |
| | [13,14,-,-]
- 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 over-full nodes can propagate backwards
up the B-tree 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.
- N. Wirth, Algorithms + Data-Structures = 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
L. A. 1986,
Department of Computer Science, Monash University, 1984,
School of Comp Sci and Software Engineering, 1999.