Why Databases Are Faster Than They Have Any Right to Be

The Brute Force Answer, and Why It Breaks

Before getting into how databases are fast, it helps to understand the naive alternative.

Imagine your data is stored in a plain flat file, row after row, no structure beyond that. You want to find every customer whose last name is "Nguyen." The computer has one option available to it. Start at the top. Read every single row. Check if the name matches. Keep going until the file runs out. In computer science, this is called a full table scan, and it is exactly as slow as it sounds. On a table with a hundred million rows, that is a hundred million comparisons, every single time, for every single query.

Sorting the data helps some. If the rows are sorted alphabetically by last name, you can use binary search. Split the dataset in half, check the middle, decide which half the answer lives in, and repeat. That turns a hundred million comparisons into roughly twenty seven. The math is genuinely beautiful. But sorting only helps when you are searching on the column you sorted by. Sort by last name and your queries on email address are back to scanning every row. Sort by email address and last name is slow again. You can only sort one way at a time, and real applications search on dozens of different columns.

Something else was needed. Something that could answer arbitrary queries on arbitrary columns, at arbitrary scale, without scanning the whole table every time. The answer that emerged, and that still underlies almost every database you have ever used, is a tree.

Binary Search Trees, and Where They Fall Apart

A binary search tree is a structure most programmers encounter early. Every node holds a value, a left child, and a right child. Values smaller than the node go left, values larger go right, and the whole thing stays ordered so that searching becomes a series of left or right decisions rather than a full scan. Find the root, compare, go left or right, compare again, repeat until you arrive at the answer. Fast, elegant, and completely impractical for databases.

Why you may ask? Well, the problem here is not the logic. The logic itself is already sound and clear. The actual problem here lies in the hardware.

A binary search tree in memory works beautifully because reading any node is nearly instant. But databases do not live in memory. They live on disk, spinning hard drives or SSDs, and reading from disk is orders of magnitude slower than reading from RAM. Every time a tree node sits on a different part of the disk, reading it costs a full disk seek. A binary search tree with a million nodes can be thirty levels deep, meaning a single search might require thirty separate disk reads. Thirty disk seeks. On hardware where each seek takes milliseconds, that adds up to something embarrassingly slow.

The database world needed a tree that could answer searches in far fewer disk reads. The answer was to make each node much, much fatter.

B-Trees, the Structure That Changed Everything

A B-tree solves the disk problem by changing the shape of the tree entirely. Where a binary search tree keeps exactly two children per node, a B-tree node can hold hundreds or even thousands of keys, with a corresponding number of child pointers. The tree grows wide instead of tall. A B-tree with millions of entries might only be three or four levels deep, meaning finding any record requires at most three or four disk reads instead of thirty.

The mechanics work like this. Each node in a B-tree holds multiple keys in sorted order, with child pointers sitting between them. If a node holds the keys 10, 20, and 30, then the first child pointer leads to values less than 10, the second to values between 10 and 20, the third to values between 20 and 30, and the fourth to values greater than 30. Searching means loading one node, scanning its keys, following the right pointer, loading the next node, and so on down the tree. Because each node is sized to match a disk page, typically 4 or 16 kilobytes, each step costs exactly one disk read, and the tree is shallow enough that the whole search finishes in a handful of reads.

Insertions and deletions keep the tree balanced automatically. When a node fills up, it splits in two and pushes a key up to the parent. When nodes get too sparse, they merge. The tree never degenerates into a lopsided mess the way an unbalanced binary tree can. That self-balancing behavior is part of why B-trees became the default choice. They perform predictably under all kinds of workloads, which is exactly what a database engine needs.

B+ Trees, and the Refinement That Stuck

B-trees were a major leap forward, but the database world landed on a variation called the B+ tree, and understanding the difference explains a lot about how modern databases behave.

In a standard B-tree, actual data records can live anywhere in the tree, including the internal nodes. In a B+ tree, internal nodes hold only keys and pointers. All the actual data lives exclusively in the leaf nodes, and the leaf nodes are linked together in a chain. That single structural change has consequences that ripple through everything.

Range queries become dramatically faster. If you want every order placed between January and March, a B+ tree can find the January starting point, then follow the leaf chain forward through February and March, reading records sequentially. A standard B-tree would require backtracking up and down the tree for every record in the range. Sequential reads from linked leaf nodes are far more cache-friendly, far more predictable, and far faster on real hardware.

Internal nodes also get denser. Without any data records taking up space, internal nodes can hold more keys, which makes the tree even wider and shallower, reducing the number of disk reads required per search. PostgreSQL, MySQL, SQLite, Oracle, SQL Server. All of them build their indexes on B+ trees. The structure is so well suited to relational database workloads that it has remained essentially standard for decades.

Indexes, the Layer Most People Actually Touch

B+ trees are what live underneath indexes, and indexes are the thing most application developers interact with directly, even if the tree underneath is invisible.

When you create an index on a column, the database builds a B+ tree over the values in that column, with each leaf node storing the column value alongside a pointer to the full row. A query filtering on that column can walk the tree to the matching leaf in a few disk reads, grab the row pointer, and fetch the full record. No full table scan needed.

Primary indexes store the actual row data in the leaf nodes directly. Secondary indexes store just the pointer. Composite indexes build the tree over multiple columns together, which is why the order of columns in a composite index matters so much. An index on (last name, first name) will efficiently answer queries filtering on last name, or on last name and first name together, but it does almost nothing for queries filtering only on first name. The tree is sorted by last name first, so the first name values are scattered all over it.

Understanding this is the difference between a developer who can debug a slow query and one who cannot. The query planner in any relational database is essentially asking the same question every time. Is there a B+ tree I can walk to answer this, or do I have to scan the whole table? If you have built your indexes thoughtfully, the planner finds the tree. If you have not, it scans.

The Relational World, Up Close

Armed with B+ trees and indexes, relational databases became the default answer to data storage for most of the last fifty years. A few of them are worth knowing in some detail.

PostgreSQL is the one that serious engineers tend to reach for when correctness matters more than anything else. It was born out of academic research at UC Berkeley in the 1980s, grew slowly and carefully, and arrived in the modern era as one of the most capable open source databases ever built. Full ACID compliance, rich data types, an extraordinarily capable query planner, support for JSON alongside relational data, geospatial queries through PostGIS, and a community that has been steadily improving it for forty years. It is not the flashiest choice and it has never tried to be. It just handles an extraordinary range of workloads without breaking a sweat.

MySQL took a different path. Where PostgreSQL prioritized correctness and features, MySQL prioritized simplicity and speed, and it became the database that powered the early web. WordPress runs on it. Facebook started on it. Most of the LAMP stack era ran MySQL underneath everything. It has had a complicated history, acquired by Sun Microsystems, then Oracle, then forked by its original creators into MariaDB, but it remains one of the most widely deployed databases in the world, still humming away under an enormous portion of the internet's infrastructure.

SQLite also deserves a mention here not because it is competing with the others but because it is everywhere and almost nobody thinks about it. No server, no network, no configuration. Just a file. SQLite is the database embedded in your Android phone, your iPhone, your browser, your desktop applications. It handles a staggering amount of real-world data and without ceremony. For smaller applications and embedded use cases, it is often the right answer, and the right answer arrived before anyone thought to go looking.

When the Relational Model Stops Fitting

Relational databases are genuinely excellent at what they do. But they were designed around assumptions that do not hold for every kind of data or every kind of workload, and as the internet scaled into something nobody had planned for, those edges started to show.

A social graph does not fit naturally into tables. A document with nested, variable structure is awkward to squeeze into rows and columns. Write traffic spread across dozens of geographic regions creates consistency challenges that relational databases were never designed to handle elegantly. And at some point, the volume of data grew large enough that no single server, no matter how powerful, could hold it all. The database world responded by building things with fundamentally different shapes underneath.

Cassandra came out of Facebook in 2008, designed from the ground up around one specific reality. At Facebook's scale, write traffic never stopped, it came from everywhere simultaneously, and any database that required a single authoritative source of truth would eventually crack under the pressure. Cassandra abandoned that model entirely. It distributes data across many nodes with no single master, and it accepts that copies of the same data on different nodes might briefly disagree with each other. The tradeoff is deliberate. Availability and write performance take priority over strict consistency, and for the problems Cassandra was built to solve, that tradeoff is exactly right. Netflix uses it. Apple uses it. Any time you need writes to keep flowing regardless of what is happening in the cluster, Cassandra is worth a serious look.

Nevertheless, Cassandra has a ceiling, and Discord found it.

Discord was one of Cassandra's most high-profile users, storing hundreds of billions of messages across billions of rows at peak usage. For years it held up. Then, as the platform grew into something nobody had originally planned for, the cracks became impossible to ignore. Latency spikes started appearing during garbage collection pauses inside the JVM, the runtime Cassandra runs on. At Discord's scale, even occasional pauses of a few hundred milliseconds were enough to degrade the experience for millions of users simultaneously. Cassandra's data model or its distributed architecture was not causing issues here, it was the runtime Cassandra was built on.

ScyllaDB is Cassandra's answer to itself. It keeps the same data model, the same query language, the same distributed architecture, but throws out the JVM entirely and rewrites everything in C++, handling memory management directly rather than relying on a garbage collector. The result is a database that behaves like Cassandra under normal conditions and keeps behaving like Cassandra when the load gets ugly, because there is no garbage collector to pause and no JVM overhead eating into the headroom. Discord migrated its message storage to ScyllaDB and came out the other side with dramatically lower tail latency and far better hardware efficiency. The story is a useful reminder that even a sound architectural idea has a ceiling, and sometimes the right move is to rebuild the same idea on a sturdier foundation.

Redis takes a completely different approach to the speed problem. Where most databases assume data lives on disk and gets pulled into memory when needed, Redis keeps everything in memory all the time and treats disk as a backup. The result is a database that responds in microseconds rather than milliseconds, fast enough to use as a cache, a session store, a real-time leaderboard, a message broker, or a rate limiter. Its data structures go well beyond simple key-value pairs, covering sorted sets, streams, bitmaps, and more. Redis became the first answer to "we need this to be faster" for an enormous range of applications, and it earned that position honestly.

The question a reader might be asking at this point is why everyone does not just store everything in Redis and be done with it. The answer comes down to two things: cost and risk. RAM is expensive, far more so than disk per gigabyte, and a database that keeps everything in memory is a database where your storage bill scales in a very uncomfortable direction as your data grows. A few gigabytes is fine. A few terabytes is a different conversation entirely. Beyond cost, there is the question of durability. If the server crashes before Redis has had a chance to flush to disk, recent writes can disappear. Redis has persistence options that reduce that risk, but they come with a performance cost, and once you start making those tradeoffs you are closing the gap between Redis and a database that was designed for durability from the start. For caching, ephemeral state, and data that can reasonably be rebuilt or lost, Redis is an excellent fit. For anything that genuinely cannot vanish, it asks you to think carefully before committing.

ClickHouse started inside Yandex as an internal tool for analyzing web analytics data and was open sourced in 2016. The problem it was built for sounds simple and is actually brutal. Scan billions of rows, aggregate them, return the result fast enough for a human to wait for it. Relational databases built around B+ trees and row-oriented storage are not well suited to this. ClickHouse stores data column by column rather than row by row, which means an analytical query that touches only three out of fifty columns reads only those three columns from disk, skipping the rest entirely. Combine that with aggressive compression and vectorized execution, and ClickHouse can chew through hundreds of billions of rows in seconds. It is genuinely astonishing to watch the first time.

SpacetimeDB is newer and stranger than the others, and interesting precisely because of the problem it has chosen to solve. Game servers and multiplayer applications have always had an awkward relationship with databases. The game state lives in the server's memory because reading from a database on every frame is far too slow, but that means the database and the application are constantly out of sync, requiring a layer of synchronization logic that is painful to write and easy to get wrong. SpacetimeDB bets that the database should simply be the server. Application logic runs inside the database as stored procedures, state lives in tables, and clients subscribe to query results that update in real time as the underlying data changes. Whether that bet pays off broadly is still an open question, but the thinking behind it is sharp, and it points toward a genuinely different way of building stateful applications.

The Structure Underneath Shapes Everything

Once you understand what a B+ tree is and why it exists, the differences between databases stop feeling arbitrary. PostgreSQL and MySQL reach for B+ trees because relational workloads are full of point lookups and range queries on indexed columns, and a B+ tree handles both beautifully. Cassandra uses a log-structured merge tree instead, an architecture that makes writes extremely fast by appending data sequentially and merging it in the background, accepting slightly slower reads as the cost. ScyllaDB keeps that same structure but removes the runtime overhead that eventually caught up with Discord. Redis sidesteps the disk problem entirely by refusing to use it as the primary store, accepting the cost and risk that come with that choice. ClickHouse rearranges the data itself, storing columns rather than rows so that analytical queries read only what they need.

Every one of these is a different answer to the same underlying question. Given the kinds of reads and writes this system will receive, what shape should the data take on disk so that the hardware can answer them as fast as possible?

That question does not have a single answer. It has many answers, each one right for a different set of circumstances. The engineers who built these systems understood the hardware deeply, worked backward from the workloads they needed to serve, and made deliberate structural choices that everything else followed from.

After reading this whole blog, I hope you have come to the conclusion that the speed was never magic. All of it was just a very careful thinking about where the data lives and how to get to it.