B Tree Basics - Slides

generated with: https://www.cs.usfca.edu/~galles/visualization/BPlusTree.html, please feel free to explore!

A simple 2-way B+ tree



Inserting, find target leaf and insert the keys 1 and 2 target == root.

[figure 1] init

When we insert key 3? we have our first overflow causing a split: split 2 is promoted and contents are split in two, we recurse from the bottom up.

[figure 2] What if we add key 4 our tree looks weird doesn’t it: balance

and now have to “rebalance” our tree with incoming key 5:

[figure 3] rebalance

searching is an Olog(N) operation!

just a reminder this is really powerful if n = 1 billion, dominance:

with a branching factor of 1001 and height 3 can store over one billion keys: num keys = branching factor ^ height - 1 * branching factor - 1

point and range queries follow the same logarithmic path.

[figure 4] search


Let’s remove 4.

First we find 4 using binary search, then re-arrange our pointers and rebalance: [figure 5] delete

Rebalancing involves restoring our ordered structure and keeping pointers valid and performing a merge or (*redistribution.)