B-Trees

Vocabulary/Concepts

Root node
leaf node - no children
Universe - all the data
Want to be able to jump efficiently to the data you want in a few jumps rather than searching all the data
B-Tree Order = Order 5 means a maximum of 4 keys and maximum of 5 children
keys = the values stored on a given node.

Left sub-tree has values that are smaller than parent, and right sub-tree of a node has values that are larger than a parent node.
Unbalanced/degenerate tree = Efficiency can depend on arrangement, can be poorly formed such that searches aren't binary. Worst case is linear O(n)

Used for reading from disk.
A version of a self-balancing tree
O(log(n)) for insert search and delete always
A B-Tree of order M:
- Every node has at least m children
- A non-leaf node with k children contains k-1 keys
- The root has at least two children if it is not a leaf
- Every non-leaf node (except root) has at least ceiling of m/2 children
- All leaves appear in the same level
To split a node, sometimes median keys are promoted up, possible to increase the height of the tree by one.