B-tree Search

A B-tree is a search tree that lets each node hold several values instead of just one. The nodes you see here keep up to three keys in sorted order, which splits the children beneath them into as many as four ranges. To find a value you scan the keys in a node from left to right; match one and you are done, otherwise you drop into the child sitting in the gap where the value belongs and repeat. Because every leaf sits at exactly the same depth, the tree is always perfectly balanced — no special cases, no lopsided chains.

That shape is not an academic curiosity: it is what almost every database and filesystem reaches for when it builds an index. The reason is the cost of a read. An index lives on disk, and disks hand back data one page at a time, where a single page can hold hundreds or thousands of keys. Packing a whole page of keys into one node means each node you visit costs one read, and a short, wide tree only has a handful of levels even when it is holding millions of rows. Fewer levels means fewer reads, and the reads are the expensive part. This is the answer to the index question from the sorted-array searches: the database is not binary-searching one giant array, it is walking a tree exactly like this one.

Keeping every leaf on the same level takes a little work on the way in. When a node fills up it splits: the middle key is pushed up into the parent and the rest becomes two smaller nodes. A split can cascade all the way to the root, and when the root itself splits the tree grows one level taller — evenly, everywhere at once. That is the trick a plain binary search tree lacks, and it is why a B-tree never degrades into the spindly chain that an unbalanced tree can.

Watch a probe scan the keys inside each node before dropping into the child between them, and notice how few levels it takes to reach any value. Type a value into the search box to look for something specific, or leave it empty and let the Target menu pick one that is present or falls in a gap. Data switches between numbers and words, and New array deals a fresh sorted set.