B Tree, B+ Tree: definitions, algorithms, and analysis

A B-tree is a generalization of a self-balancing binary search tree in which each node can hold

more than one search key and have more than two children. The structure is designed to

allow more efficient self-balancing and offers particular advantages when the node data needs

to be kept in external storage such as disk drives. The standard (Knuth) definition is:

Definition. A B-tree of order m is a tree which satisfies the following conditions:

• Every node has at most m children.
• Every non-leaf node (except the root node) has at least m=2 children.
•  The root node, if it is not a leaf node, has at least two children.
•  A non-leaf node with c children contains c-1 search keys which act as separation values to divide its sub-trees.
•  All leaf nodes appear at the same level and carry information.