In Module 2 you added an index on orders (restaurant_id, status) and a query dropped from 2 seconds to 2 milliseconds. You treated the index as a black box: a sorted structure that makes lookups fast. This lesson opens the box. In Postgres, MySQL, SQLite, Oracle and SQL Server, that box is almost always a B-tree, or more precisely its variant, the B+ tree.
Each shard of Tiffin's orders table now holds about 200 million rows. An index on order_id finds any one of them in 3 or 4 page reads. Here's how.
Why not a binary search tree?
A balanced binary tree over 200 million keys is about 28 levels deep. In memory, 28 pointer hops is nothing. On disk, each hop could be a separate read, and the cost of a read isn't the few bytes you want. It's the whole page around it, typically 4 to 16 KB, plus the time to fetch it.
So the idea behind the B-tree (Bayer and McCreight, 1970) is: if you're going to read a whole page anyway, make each tree node fill a page. A node then holds hundreds of keys, not one. The tree gets very wide and very shallow.
A B-tree is a balanced tree where each node is one disk page holding many sorted keys. Searching reads one page per level, and with hundreds of keys per page, even billions of rows need only 3 or 4 levels.