|
|
|
|
|
A <</SPAN>#61#>B-tree of order $m$ is a balanced search tree in which
- every node has at most $m$ children,
- every node, other than a root or leaf, has at least $m/2$ children,
- the root has at least 2 children if it is not a leaf,
- all leaf nodes appear on the same level
- a nonleaf node with $k$ children has $k-1$ keys.
If the tree has $n$ nodes its height is $O(log_2(n))$
|
"B-tree" is owned by Mathprof.
|
|
(view preamble | get metadata)
Cross-references: height, tree, keys, level, leaf, root, children, node, search tree
There are 23 references to this entry.
This is version 6 of B-tree, born on 2007-07-04, modified 2007-07-05.
Object id is 9730, canonical name is BTree.
Accessed 2764 times total.
Classification:
| AMS MSC: | 68P05 (Computer science :: Theory of data :: Data structures) | | | 68P10 (Computer science :: Theory of data :: Searching and sorting) |
|
|
|
|
|
|
Pending Errata and Addenda
|
|
|
|
|
|
|
|
|
|
|
