node split
The B-tree operation that breaks a full node into two half-full nodes and moves its middle key up into the parent.
In more detail
The course's insert splits any full node it meets on the way down, so there is always room when it reaches the leaf. When the root splits, a new root is created and the whole tree grows one level taller, which is how a B-tree keeps all leaves at equal depth.
Related terms
- B-tree — A balanced search tree whose nodes each hold many sorted keys and have many children, so the tree is very wide and very shallow.
- minimum degree — The parameter t of a B-tree that sets how full its nodes are: at least t minus one and at most 2t minus one keys, except at the root.
Taught in
- B-Trees: The Structure Behind Every Database Index — Algorithms & Data Structures for Working Engineers