B-Trees
- The ultimate balanced tree. The balance factor throughout the tree is ALWAYS 0.
- New concept: Nodes that hold multiple values.
  * A node with n values will have n+1 children.
  * The tree invariant holds.
- For a node with max degree M, max m-1 values (keys).
- Non-root nodes have between m/2 and m-1 values.
  * The root has betwen 1 and m-1 keys.
- Splitting of a node on insertion pushes a value upward

- why m should be odd?
  * When a split occurs there will be a middle item

- A root can initially hold m-1 values before any split occurs.
  * A split only occurs when required. There isn't any choosing ==>
    + A split occurs when a node exceeeds the capacity of values, 
       i.e. it would have m keys (and thus m+1 children)
    + A split cuts a node with one over the maximum in half, 
        creating two nodes containing the minimum number of values.

- Insertion is still always in a leaf. 
   Note: There could be other algorithms that handle this differently. 

If l is the level in a tree (root level is 0) then the max number of children on any level is m**(l+1)
- ** == ^ == exponentiation
- The number of keys on any level is (m-1)*m**l
- Max total keys in B-Tree sum (i=0 to heighth) of [(m-1)*m**l]

- Removal always results in a value being removed from a leaf 
  * Not always the value being removed.
  * Some leaf will lose a value; it may be by deletion, OR promotion.
  * If a value to be removed is not in a leaf, a value from a leaf will be promted into its place.
    + This may cause a chain reaction, as we saw when a 3rd level was created via insertion.
  * Where insertion could cause split and promotion, deletion can cause recombination and demotion