Ch.9: Algorithms: Why Databases Use B-Trees

0:00 Let's say a checkout index is getting new orders every second. A sorted sequence can search beautifully, but one middle insert asks the structure to scoot the furniture around. And the dashboard still wants ranges in order. So why do databases use B-trees instead of just sorted arrays or hash tables? Right, and the honest answer is annoyingly, it depends what search means here. The shape it keeps landing on is a tree, but a fat one, sized to a storage page. B-trees make ordered data searchable while the set changes, and they do it in chunks that make point lookups and range scans cheap.

0:37 Yeah. So finding the key is the easy half. The hard half is keeping the whole index from rearranging the living room every time a row arrives. That leaves one practical target: keep writes local while reads stay ordered. Start with the simple version. If keys sit in a sorted list, a point lookup can use binary search in O of log n. That is excellent. But inserting one new key can mean sliding half the array over by one slot. Yeah. And that's the catch. The search path is tiny, but the update path, I mean, it can be huge.

1:12 For example, an orders service adds one order in the middle of a sorted customer history, and the index has to slide thousands of later keys before the checkout dashboard can show the new row. That image hurts because we have all built that spreadsheet. The structure is fast at the question we asked yesterday and awkward at the write pattern we got today. The result is a simple design target: keep the write local. From that array-update problem, the first escape is links instead of shifts. Oh, so we stop sliding the whole row and change pointers.

1:47 A search tree keeps sorted order by links. Smaller keys go left. Larger keys go right. So search is still a comparison path. At each node, compare once, then choose one side. If the tree stays shallow, search, insert, and delete are all proportional to the tree height. And that's the whole idea: keep the tree shallow. Yeah. And the source links are in the description because this is where textbook diagrams and real engines start diverging. The idea is simple. The implementation choices are not, and that difference is what turns a classroom tree into an index design question.

2:22 It sets up the real constraint: the tree has to stay shallow under pressure. But links alone are not enough, right? No. The catch is shape. That structure is only fast if the shape is good. Hold on, if I insert already-sorted keys, does the tree just lean over? Yeah. Insert one, then two, then three, then four. Every new key goes to the right. You did not build a tree. You built a linked list wearing a tree costume. Sure. So the word tree is not the guarantee. Height is the guarantee. That is the point. A balanced tree with a million keys has a small height.

2:59 The same million keys in a collapsed shape can have a million-step worst path. Same values, same rule, totally different performance. Once height is the contract, balance becomes the maintenance work. After inserts and deletes, the structure does, A little repair work so the height stays near log n. That repair is the rotations people remember from data-structures class? Yeah, but I think we can skip the case table entirely. What a rotation actually does is change local shape without breaking sorted order.

3:31 It kind of moves a few links around so the tree is less tall, while the left-smaller, right-larger rule remains true. So rotations are not clever decoration. They are the rent you pay to keep future operations cheap. I love that. Tiny rent now, fewer bad paths later. Skip the rent and every future lookup gets the invoice. Now the choice becomes how strict that balance should be. So why do we have multiple balanced trees? Because balance is a tradeoff, not a single answer. A V L trees keep stricter balance, so lookups can be very tight. Red-black trees allow a little more slack, which usually makes updates cheaper and simpler.

4:15 And the official Java docs say TreeMap is backed by a red-black ordered map. That is not trivia. It tells you the library is buying sorted-key operations with a maintained tree, not hashing. Oh, that's the giveaway. The API is exposing the workload itself, not merely an implementation detail. HashMap asks "do I have this key?" TreeMap can ask "the next key after this," "the starting key in this range," and "walk keys in order." Different workload, different data structure. So the type you pick is basically a bet on the queries you will get.

4:48 Where does this bet actually show up in production? You see balanced trees wherever the next key matters. Ordered maps, schedulers, timers, and in-memory indexes all depend on predictable adjacency and steady sorted traversal. I used to think of that as a niche feature until I needed the nearest key, not the exact key. The hash map gave me the exact lookup and then just stared at me. We have all done the "use a map" reflex. Most of us do not reach for predecessor, successor, range, or sorted iteration, and hashing stops being the whole story.

5:22 And that is the bridge to databases. A database index rarely needs only one exact key forever. It often needs a starting point, then ordered movement from there. That gives the database a trail from one key to the next instead of a single mailbox. From in-memory ordered maps, here's where it gets interesting for databases. If ordinary balanced trees are so useful, why does a database not just use a memory-shaped tree for an index? Storage pages. A binary tree is skinny. Every node has at most two children, so a big lookup can require many node reads.

5:58 In memory, that might be okay. On disk, or across storage pages, every level is expensive. Oh, right. So the problem is not comparison count anymore. It is how many pages I make storage touch? Usually, yes. If one page read can bring in thousands of bytes, the page should hold many separator keys, not one key and two pointers. A skinny tree wastes the page. Yeah, that's the physical detail we were missing. The tree is not floating in math space. It is sitting on pages, and pages make branching factor a systems problem.

6:33 Imagine a dashboard query that needs one row from each of 10 million records. If storage has to bring in a whole page anyway, what do you want on that page? Useful routing keys, not one tiny clue. Otherwise you get the storage-page nightmare: lots of reads, almost no useful work. So the fix writes itself: make each node fatter. Once page reads are the bottleneck, the database tree widens the node. One node can hold many keys and many child pointers. Instead of "less than this key goes left and greater goes right," each node has several separators, and each separator chooses a range. So a single page load lets you compare against many keys before choosing the next child.

7:16 Yes. That is why the fanout matters. If a node has, you know, hundreds of children, a very large table can have a very short tree. The lookup path might be root page, one internal page, one leaf page. Not always, but that is the shape. Right, so the page is doing the routing, not the node. Wait, so a giant table is what, three page reads deep? Pretty much. One page narrows the search across many ordered ranges instead of making the lookup crawl one binary branch at a time. And the engine docs line up with that B-tree intuition, with implementation details varying.

7:53 The specific docs are linked below. Okay, so this is where the slogan needs a footnote. Yeah. Postgres describes its btree index as a multi-way balanced tree. MySQL says InnoDB indexes are B-tree structures except for spatial indexes. SQLite's planner talks about binary searches against indexes. That is a useful correction. "Database uses a B-tree" is true enough for the intuition, but the real claim is narrower: the B-tree family matches page-based ordered lookup. Right, and that narrower claim tells you what to reach for when the workload is not pure equality. It leaves room for engine-specific details instead of pretending every storage engine is the same.

8:33 So where does the plus in B plus tree fit? The plus matters at the leaves. In the common teaching version, internal nodes route the search, and the actual records or row pointers live down in the leaves. The leaves are linked in key order. Ah, so once you land in the right neighborhood, you just walk sideways. Yes. Find the first key once. The vertical work is done. Then walk leaf to leaf in order. You are not restarting a search for every row in the range. You are using the ordered leaf chain. Right. So scanning a range is not one fresh lookup per row.

9:08 Yeah. Take a concrete case: a payments analyst asks for every charge between Monday morning and Tuesday morning. The index finds the first timestamp, then walks the leaf pages until the time window ends. The consequence is a bounded ordered walk instead of a full table scan. Yeah, that makes database indexes feel much less magical. Point lookup is the root-to-leaf path. Range scan is root-to-first-leaf, then a sideways walk. Let's hear it. The backend reviewer will still say, "this endpoint is a customer-I D lookup.

9:41 If I only need equality, why are we paying for an ordered tree?" Fair question. A hash index is built for "exactly this key." That can be great when the workload is pure equality and the engine supports the right shape. But the moment the query says between two dates, latest first, greater than this price, next event after this timestamp... ...the hash has no order to walk. It can tell you where one key should land. It cannot give you neighboring keys in sequence. A storage-shaped ordered tree wins when preserving order is part of the work, not just finding one key.

10:15 Now, "there is an index" still does not mean "the planner should use it." Sure. A tiny table might be faster to scan. A query that returns half the table might not save enough work. An index that matches the wrong leading column can miss the query shape. Yeah. We have all seen that postmortem sentence, too. A reviewer says, "add an index," as if the index is a sticker you slap on a slow query. Classic. The database is not being stubborn; it is doing math. So what you actually ask is: what work does the index avoid?

10:49 Does it jump to a selective key? Does it preserve the order the query needs? Does it turn a huge scan into a short tree walk plus a small leaf walk? For example, a reporting API filters by customer ID but orders by created time. If the index only helps the first part and then the database sorts millions of rows anyway, the page still loads late and the incident review still says "index added." The index has to change the cost shape, not just exist. After the planner view, here's the mistake people make: treating all lookup structures as interchangeable.

11:24 Hash table, sorted array, linked search tree, B-tree. Same general vibe: find stuff fast. Right, and that's the trap. Their promises are completely different. Hash tables give equality lookup without order. Sorted arrays give amazing reads and painful middle inserts. Memory-resident balanced trees give ordered updates. B-trees give page-aware ordered access for storage engines. So the question is not "which structure is fastest." It is "fast for which promise?" Yes. Ask what the workload needs: exact match, nearest key, range scan, or page-efficient reads. Imagine a support queue.

11:57 The useful query asks for the next ticket due. A single exact ticket ID does not help much. The data structure answer follows from that. That gives the checklist some teeth: name the access pattern first, then pick the structure. So the tree lesson is not "memorize rotations." It is that sorted data needs a maintenance strategy. Arrays keep order by shifting. Balanced trees reshape to keep it. B-tree nodes preserve order in page-sized chunks. Honestly, that's the part I like: order is never free. Every structure pays for it somewhere.

12:34 That is why an index is not just a faster lookup. It is a maintained ordered structure with real costs and real query shapes. Man, that is the design bargain. The index is doing maintenance work so your query gets to feel simple. Next time, we leave trees as a special case and look at the bigger shape: graphs, dependencies, D A Gs, and the systems that are secretly made of nodes and edges. Thanks for listening to Learning Podcasts.