What is B Tree

content

Note

B Tree means balanced tree;
balanced means that the path the all leaves is the same length.
That’s how it keeps log search

gist of B Tree

allowing more children under a node, hence reducing the height of the tree
- by keeping tree height low, we reduce disk I/O
it’s balance tree, meaning that all leaves are on the same level

some rules for B-Tree

source: wikipedia
every leaf node should be on the same level, otherwise it’s imbalanced
the min number of keys a node can have is half of the max keys (round down if needed)
each node has at least two keys, root node can have only 1
a key is always added to the leaves
when a leaf is full, it’s gonna split up, and the middle key will be move up to the root
- in the image above, say the b-tree has a max of 4 keys, min of 2, per node
- when 3 is added to the tree, it goes to the leftmost leaf
- the leaf then splits up:
  - 1, 2 becomes another node, 5, 6 becomes another node
  - 3 becomes the first key of the root node
- what happens when the root is full?
  - the root node splits up as well, see visualization here