B-tree

Last updated Nov 8, 2022 Edit Source

A self balancing tree data structure.

Consider a B-Tree of order n (here we use example of ):

• Each orange box is a key
• Each blue line is a pointer to subtree

This also means that each internal node has at least $\lfloor{n/2}\rfloor$ +1 children

a.

1. Interior node min keys: $\lfloor(n/2)\rfloor=5$ Min pointers: $min\\ key + 1 = 5+1=6$
2. Leaf node min key: $\lfloor(n+1/2)\rfloor=5$ Min pointers: $min\\ key + 1 = 5+1=6$ b.
3. Interior node min key: 5 Min pointers: 5+1 =6
4. Leaf node min key: 6 Min pointers: $min\\ key + 1 = 6+1=7$