Case Study 1: How Databases Use Indexing and Sorting to Handle Billions of Records

The Problem of Scale

Imagine a hospital's patient records database. It contains 50 million records — one for every patient who has ever visited. A doctor needs to pull up a specific patient's history by their patient ID. The query needs to return in under 100 milliseconds; anything slower disrupts the clinical workflow and, in emergency situations, could delay critical care.

If the database used linear search — scanning through all 50 million records one by one — even at a million comparisons per second, that's 50 seconds per lookup. Completely unacceptable. A nurse searching for patient records hundreds of times per shift would spend more time waiting than working.

This is the problem that database indexing solves. And at its core, database indexing is just a sophisticated application of the same binary search principle you learned in section 19.3.

What Is a Database Index?

A database index is a separate data structure that maintains a sorted mapping from key values (like patient IDs, names, or dates) to the location of the full record on disk. When you create an index on a column, the database builds something similar to a sorted list with pointers to the original data.

Think of it like a book's index. Instead of reading every page to find where "binary search" is mentioned, you flip to the index at the back, find "binary search" in alphabetical order (quickly, because it's sorted), and it tells you exactly which pages to turn to. The index is small and sorted; the book is large and unsorted.

The B-Tree: Binary Search on Steroids

Most database indexes use a data structure called a B-tree (or a variant called a B+ tree). A B-tree is a generalization of the binary search principle:

• In binary search, you divide data into 2 groups at each step.
• In a B-tree, you divide data into hundreds of groups at each step.

A typical B-tree node might have 100–500 entries. This means that a B-tree with just 3 levels of nodes can index over 100 million records. A lookup requires reading only 3 nodes from disk — that's 3 disk reads to find any record among 100 million.

Here's the math: - Level 1 (root): 1 node with ~200 entries → 200 branches - Level 2: 200 nodes with ~200 entries each → 40,000 branches - Level 3 (leaf): 40,000 nodes with ~200 entries each → 8,000,000 record pointers

With just three disk reads, the database can locate any one of 8 million records. Add a fourth level (200⁴ = 1.6 billion), and you're covering over a billion records with just 4 disk reads.

Compare that to linear search through a billion records: a billion record checks versus 4 node reads. Even allowing for the work of searching inside each node (which is itself a quick binary search over ~200 sorted entries), the B-tree wins by a factor in the millions.

How Sorting Powers Query Performance

Indexes aren't the only place sorting matters in databases. Sorting is fundamental to several critical operations:

ORDER BY Clauses

When you write a SQL query like SELECT * FROM patients ORDER BY last_name, the database needs to sort the results. If there's an index on last_name, the data is already sorted — the database just reads the index in order. If there's no index, the database must sort the entire result set, which can be extremely expensive for large tables.

JOIN Operations

When a database joins two tables (combining related data from different tables), one of the most efficient strategies is the sort-merge join:

1. Sort both tables by the join column
2. Merge the two sorted tables (exactly like the merge() function from merge sort)
3. Matching rows are combined into the result

If you've implemented merge sort's merge() function, you already understand the core of how major databases join millions of rows.

GROUP BY and Aggregation

Grouping data (e.g., "total donations per donor") is much easier when the data is sorted by the grouping column. All records for the same donor are adjacent, so the database can total them in a single O(n) pass, keeping only one running total in memory at a time. If the data isn't already sorted, the database must choose: sort it first (O(n log n)), or build a hash table of running totals (the dictionary idea from Chapter 9), which is fast but needs memory for every group.

Real-World Example: Amazon's DynamoDB

Amazon's DynamoDB is a database service that powers high-traffic Amazon systems, including Alexa, the Amazon.com sites, and Amazon's fulfillment centers. During Prime Day 2024, it peaked at 146 million requests per second.

DynamoDB uses a concept called a sort key alongside a partition key:

• The partition key determines which physical server stores the data (distributing load across thousands of machines).
• The sort key determines the order of records within each partition.

Because records within a partition are stored in sorted order by the sort key, DynamoDB can efficiently: - Retrieve all orders for a customer, sorted by date - Find all products in a category with prices between $10 and $50 - Get the most recent 20 log entries for a system

These are all range queries — and they're only efficient because the data is sorted. Without sorted storage, each of these queries would require scanning every record in the partition.

The Cost of Indexing

Database indexing isn't free. Every index has costs:

1. Storage space. Each index takes up disk space. A table with many indexes can use more space for indexes than for the actual data.

2. Write performance. Every time a record is inserted, updated, or deleted, every index on that table must also be updated. This is exactly the trade-off from sections 19.2 and 19.3: binary search requires sorted data, and maintaining sorted data during updates is expensive.

3. Decision complexity. Database administrators must decide which columns to index. Index everything, and writes slow to a crawl. Index nothing, and reads become unbearable. Finding the right balance requires understanding query patterns — which queries run frequently, which are performance-critical, and which columns appear in WHERE, ORDER BY, and JOIN clauses.

This is the same trade-off you evaluated in the chapter: is it worth sorting data once to enable fast binary searches later? The answer depends on how many times you'll search versus how often the data changes.

The Scale Problem Is Only Getting Bigger

Modern databases deal with scales that would have been unimaginable a few decades ago:

(Figures as reported by each company: Google's "How Search Works" and its 2025 search-volume announcement, AWS's Prime Day 2024 recap, a Netflix engineering talk at Trino Summit 2024, and Visa's fiscal 2024 annual report and fact sheet.)

At these scales, the difference between O(n) and O(log n) isn't academic — it's the difference between a system that works and one that collapses. Suppose a lookup in a billion-record index takes 30 steps (log₂ of a billion) and finishes in 1 microsecond. A linear scan of the same data needs a billion steps — over 30 million times as many — so each query would take about half a minute. Multiply that by thousands of queries per second and the system is hopeless.

Every time you search for a product on Amazon, every time Netflix recommends a show, every time your credit card is authorized — sorting and searching algorithms, implemented through database indexes, are doing the work behind the scenes.

Connection to What You Learned

The algorithms in this chapter aren't just classroom exercises. They're the conceptual foundation of systems that handle billions of records and millions of queries per second:

• Linear search → Full table scans (what databases do when there's no index)
• Binary search → The principle behind B-tree index lookups
• Merge sort → The merge step in sort-merge joins
• Key functions → Sort keys in databases like DynamoDB
• The sorting/searching trade-off → The index maintenance cost analysis that database administrators perform daily

You now understand the ideas that power the infrastructure of the internet.

Discussion Questions

1. A database table has 10 million records. A specific query runs 10,000 times per day. A developer is deciding whether to add an index on the queried column. The index would speed up each query from 5 seconds to 0.001 seconds, but would slow down each insert operation from 0.001 seconds to 0.003 seconds. The table receives 50,000 inserts per day. Should the index be created? Show your math.

2. Why do you think B-trees use hundreds of entries per node instead of just 2 (like binary search)? Hint: think about how data is stored on physical disks and the cost of reading from disk.

3. A social media platform stores posts in chronological order. A user asks to see posts sorted by "most liked." If the platform has 500 million posts, should it re-sort all posts every time someone makes this request? What alternative strategies could it use?

4. The sorting/searching trade-off in databases mirrors the trade-off in this chapter: sorting data is expensive, but enables fast searching. Can you think of non-computing examples of this same trade-off? (Think about organizing physical spaces, filing systems, or libraries.)