Characteristics:
- Root may have 0 or 1 element to MAX, other nodes have at least MIN elements
- Space in one node: maximum = 2 * minimum
- Elements in a node are stored in a sorted array, from the smallest to the largest
- Number of subtrees = number of elements in parent + 1
- Every leaf has the same depth
Operations:
Add a new node: ascend the middle node to its parent when reach maximum limit of a node
Remove from a B-Tree: replace with the smallest node from its right subtree or the largest node from its left subtree. Merge siblings and rotate if necessary, making sure each node has minimum number of elements
Number of values contained: maximum * (1 - (maximum + 1) ^ (height + 1)) / 1 - (maximum + 1) Example: a B tree with minimum of 10, height of two can store 9260 values
When split a leaf, we copy the middle key up:
When split an internal node or root, we move the middle key up:
Because there’s no need to redundantly store the association for internal nodes.
Adding is the same as B tree except for the leaf node, where you need to leave a copy behind.
Removing from a B+ tree:
-> remove 70 ->
-> remove 80 ->
