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, and you're covering over a billion records with just 4 disk reads.

Compare that to linear search through a billion records. The B-tree is about 250 million times faster.

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 faster when the data is sorted by the grouping column. All records for the same donor are adjacent, so the database can process them in a single pass — O(n) instead of needing to build hash tables or make multiple passes.

Real-World Example: Amazon's DynamoDB

Amazon's DynamoDB handles tens of millions of requests per second across Amazon's retail platform, Amazon Web Services, and services like Twitch and Alexa. Every product listing, every shopping cart, every order — all stored and retrieved through DynamoDB.

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 we discussed in section 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:

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. A system that takes 1 microsecond per query at O(log n) would take days at O(n) with the same data.

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.)