Balanced Trees and B-Trees

This unlocks the next topics in your library: Binary Tree Traversal, Heaps and Priority Queues, and eventually performance engineering. More practically, balanced trees and B-trees are the reason database indexes work — every time you search a record in a database like PostgreSQL or MySQL, a B-tree is doing the lookup. Understanding this gives you the mental model for why indexes make queries fast and why inserting rows can sometimes slow down. It also connects to hash functions and bloom filters (which you have notes on) — they are all ways to find data quickly, but each trades off something different.

Imagine you have a list of names, say 1,000 of them, written on a single long sheet of paper. To find a particular name, you might have to read all 1,000 — that's slow. Now imagine you split the list into 10 pages of 100 names each, and on the front of each page you write the first and last name on that page. To find a name, you first look at the 10 page labels (10 checks), then within that page you look through 100 names (100 checks). Total worst case: 110 checks, better than 1,000. Now split each page into 10 sub-pages, with labels on each — the search becomes: check 10 big labels, then 10 sub-labels, then 10 names — 30 checks. This is the idea of a tree: each level reduces the remaining search space by a factor. A balanced tree keeps this structure even as you add and remove items. Without balancing, if you add names in sorted order, the tree might degenerate into a single long chain — like the original 1,000-name sheet — and you're back to 1,000 checks. A B-tree extends this by making each node (page) wider — capable of holding many keys and many child pointers — so that the tree is short and wide, which is perfect for disk storage where reading a block of data is the costly operation. In short: balanced trees keep searches fast regardless of insertion order, and B-trees are a specific kind of balanced tree designed for storage systems.

Think of a library's catalog system. A small library might have a single card catalog drawer with one card per book. To find a book, you flip through all cards — O(n). A bigger library organizes cards into drawers, each drawer labeled with a range (e.g., 'A–C'). To find 'Bharat', you first pick the 'A–C' drawer (one step), then flip through cards inside (maybe 100). That's a two-level tree. Now imagine each drawer has sub-drawers: 'A–B', 'C' — you go from main label to sub-label to card. This is a balanced tree: every path from top to bottom has the same length (or nearly). The invariant is that no drawer is empty and no drawer is too deep, so the number of steps stays logarithmic. The analogy breaks when you add B-trees: in a real library, a drawer can hold many cards, but in a B-tree, a node can hold many keys AND many child pointers — it's like a drawer that contains not just cards but also sub-drawers, and each sub-drawer is itself a drawer. This makes nodes large, which is perfect for disk because reading a node means reading a whole block (e.g., 4 KB). If you had to read one small piece at a time, you'd make many disk seeks (slow); with B-trees, you read a whole block and get many keys at once, reducing seeks. The library analogy works until you consider that a B-tree node can have hundreds of keys, not just 26 — the 'drawer' is huge because disk blocks are huge, and searching within a node is done in memory (fast) rather than on disk.

A balanced tree is a search tree that maintains a height invariant — the length of the longest path from root to leaf stays within a constant factor of the shortest — so that search, insert, and delete remain O(log n); a B-tree is a balanced tree where each node can hold many keys and many children, specifically designed to minimize disk seeks by aligning node size with block size.

You have notes on Hash Functions and Bloom Filters — those are also about fast lookup but with different trade-offs. A hash table gives you O(1) average lookup but no ordering and no worst-case guarantee. A balanced tree gives you O(log n) and maintains sorted order, which lets you answer range queries (e.g., 'all names between A and C') efficiently. Heaps (you have notes) are a partially ordered tree — they only guarantee access to the min or max, not full ordering. Balanced trees give full ordering. B-trees connect to performance engineering and systems programming — they are the standard index structure in databases. Your library mentions 'Balanced trees keep operations logarithmic by maintaining a height invariant' — that's the core of this topic. The neighbouring topics of Binary Tree Traversal apply here: in-order traversal of a balanced search tree yields sorted output.