Architecture: Relational Databases
Databases store the state of our applications, yet plenty of developers only have a fuzzy picture of how they work underneath. This post digs into two of the pieces that matter most when working with an RDBMS: indexes and transactions.
What is an index?
An index is a data structure that makes finding specific rows in a table faster, the same way the index at the back of a textbook saves you from reading every page to find one topic.
It works by keeping a separate, smaller structure that holds part of the table’s data, ordered so it can be searched faster than scanning the whole table. That speed isn’t free. An index needs extra storage and memory, and it slows writes down, since every insert or update has to keep the index current. The textbook comparison is a fine place to start, but real database indexes get more involved than that.
Why do we need indexes?
Indexes exist to get the data you want as quickly as possible.
The more data you have, the harder that gets. Think of the difference between keeping a class attendance list and keeping a birth registry for a whole city. A short list is easy to scan; at city scale, finding one record by reading everything stops being practical.
Databases have a few tricks for this, but past a certain size you need something more deliberate, and that’s where indexes come in.
How do indices actually work?
💡 Using an index makes it faster to find the data you are looking for, but it also makes it slower to add new data. This is because the index needs to be updated every time you add new information to the database.
A simple idea would be ordering data in the way we want to query it. Unfortunately, in relational databases, it usually happens that we want to query data in multiple ways. Therefore, we need a different place to keep our data ordered.
An index creates a separate data structure that stores a subset of the data as well as a pointer to the corresponding rows on disk, organized in a specific way to optimize search performance for specific queries. The most common type of index is the B-tree index, which organizes data in a hierarchical tree structure of index leaf nodes, allowing for efficient searching and sorting of data. Since this structure requires index leaf nodes to be sorted logically, we need to find a way to add data quickly without having to move data or edit other entries.
This is done via a doubly linked list. Every node has links to two neighboring entries, very much like a chain. New nodes are inserted between two existing nodes by updating their links to refer to the new node. The physical location of the new node doesn’t matter because the doubly linked list maintains the logical order. The data structure is called a doubly linked list because each node refers to the preceding and the following node. It enables the database to read the index forwards or backwards as needed. It is thus possible to insert new entries without moving large amounts of data - it just needs to change some pointers.
Indexes can be created on one or more columns in a table, and a single table can have multiple indexes.
That linked list is only the bottom layer. On its own it would still mean walking the chain from one end, which is no better than reading the table. What makes the lookup fast is everything above it: the leaf nodes are grouped into branch nodes, those branch nodes are grouped again, and so on until a single root node covers the lot. Each node holds the largest value of every child beneath it, so the database can look at one node and know which child to descend into.
Which keeps the tree remarkably flat. Each level multiplies the number of entries the one above can address, so depth grows with the logarithm of the row count rather than the row count. A B-tree over a million rows is typically three or four levels deep. Over a billion rows it’s maybe five. Finding one row in a billion costs you a handful of node reads instead of a billion row reads, and that gap is the whole reason indexes exist.
Which column comes first
The moment an index covers more than one column, the order of those columns decides which queries it can serve. This is where most disappointing indexes come from: the index exists, the query looks like it should use it, and the database ignores it anyway.
An index sorts by the first column, then breaks ties with the second, and so on, exactly the way a phone book sorts by surname and then by first name. A phone book is perfect for finding every Schmidt, and useless for finding every Anna. Same book, same data, and the difference is only which column got sorted first.
The database can jump straight to a contiguous block when your conditions match the index from the left. Miss the leading column and there is no block to jump to, because the rows you want are scattered through the whole index.
So: put the column you filter by exactly on the left, and the column you filter by in ranges after it. PostgreSQL states this precisely enough to be worth reading twice:
The exact rule is that equality constraints on leading columns, plus any inequality constraints on the first column that does not have an equality constraint, will always be used to limit the portion of the index that is scanned.
MySQL is stricter about this than PostgreSQL is. PostgreSQL 18 gained skip scans, which let it use an index even when a leading column isn’t constrained, provided that column has few enough distinct values. Don’t design around it. An index whose usefulness depends on the planner guessing well is one refactor away from being dead weight.
The docs are also blunt about not getting carried away: “Multicolumn indexes should be used sparingly. In most situations, an index on a single column is sufficient and saves space and time. Indexes with more than three columns are unlikely to be helpful unless the usage of the table is extremely stylized.”
An index has to actually narrow things down
An index earns its place by eliminating rows. If it can’t eliminate many, the database won’t use it, and it’s right not to.
This is selectivity, and it’s why an index on a boolean column is usually pointless. If half your rows have active = true, the index tells the database to visit half the table anyway, one row at a time, in whatever order the index happens to be in. Reading the table straight through in physical order is faster than that, so the planner reads the table straight through. You get the storage cost and the write cost of the index, and none of the benefit.
People tend to guess that threshold far too high. Somewhere in the low single-digit percentages of a table, a scattered index lookup stops paying, because every row it points at is potentially a separate random read.
So check what your database actually does rather than assuming. EXPLAIN ANALYZE tells you the plan it chose and what that plan cost, and it will happily show you an index you were sure was being used sitting there untouched.
Reading straight from the index
If the index already holds every column a query asks for, the database can answer from the index alone and never touch the table. PostgreSQL calls this an index-only scan, and it’s the difference between one structure read and two.
-- has to visit the table for city
CREATE INDEX people_name ON people (last_name, first_name);
SELECT city FROM people WHERE last_name = 'Schmidt';
-- answers from the index alone
CREATE INDEX people_name_city ON people (last_name, first_name) INCLUDE (city);INCLUDE stores the extra column as payload without making it part of the sort key, so it doesn’t affect how the index searches and doesn’t affect uniqueness if the index is unique. Trailing key columns would work too, but INCLUDE says what you mean.
There’s a catch in PostgreSQL that surprises people. Index entries don’t record whether a row is visible to your transaction, so an index-only scan consults the visibility map, and if the relevant page isn’t marked all-visible it has to check the table after all. On a table that’s written to constantly, the index-only scan you carefully built quietly stops being index-only.
What indexes cost
Every index is a second structure describing the same data, and it has to stay correct on every write. Insert a row into a table with four indexes and you’ve done five writes. Delete one, same. This is why a table that’s written to far more often than it’s read can be slower with indexes than without.
Updates get an escape hatch. PostgreSQL has an optimization called heap-only tuples, where an update that doesn’t touch any indexed column, and that fits on the same page, skips the index maintenance entirely. The docs put the condition as “the update does not modify any columns referenced by the table’s indexes”.
Which is an argument for thinking twice before you index a column you update constantly. A last_seen_at timestamp changes on every single request, and indexing it means each of those updates now rewrites an index entry as well, and gives up heap-only tuples for the whole row.
Indexes are a read optimization you pay for on write, and the payment is real. Add one because a query needs it, not in advance because a column looks important.
The other half: transactions
An index is about speed. A transaction is about not being wrong, which matters more.
A transaction is a group of statements the database treats as a single unit. It either all happens or none of it does, and until it commits, nobody else sees any of it.
BEGIN;
UPDATE accounts SET balance = balance - 100 WHERE id = 1;
UPDATE accounts SET balance = balance + 100 WHERE id = 2;
COMMIT;All of the value is in the gap between those two updates. Without a transaction, a crash in that gap deletes 100 units of money from the world, and no amount of careful application code closes the window, because the window sits between two round trips to a machine that can lose power. Inside a transaction the gap isn’t observable. Either both updates are there afterwards or neither is.
ROLLBACK is the other half, and it’s what makes error handling tractable. When something fails halfway through, you don’t have to work out which of the six statements you already ran and write compensating updates to undo them. You abandon the transaction and the database forgets the whole thing happened.
The alternative is code that tries to clean up after itself, and cleanup code is only correct if it anticipates every failure point. It never does.
What makes it survive a crash
A write-ahead log. Before the database modifies the actual data files, it writes down what it’s about to do in a sequential log and flushes that to disk. Only then does it report the commit as successful.
Everything depends on that ordering. If the machine dies afterwards, the log is enough to reconstruct the work on restart, and anything that never reached the log is something the database never claimed had committed. It also explains why commits cost what they do: a commit waits on a physical write completing, which is why ten thousand inserts in ten thousand transactions is dramatically slower than the same ten thousand in one.
Where people get this wrong
Not using one. A read-modify-write spread over several statements with no transaction around it is a race waiting to happen, and it will pass every test you write, because tests run one thing at a time.
Holding one open across a network call. A transaction keeps resources locked and pins a snapshot of the database for as long as it’s open. Put an HTTP request inside one and a foreign service’s slow day becomes your database’s slow day. Do the outside work first, then open the transaction.
Assuming a transaction protects you from other transactions. It does, but only up to a point, and the point is set by a configuration value you’ve probably never touched. That’s the isolation level, and it decides which concurrency bugs your application is allowed to have. It has a post of its own, including a simulator for watching two transactions trip over each other.
Where this goes next
Indexes and transactions between them buy you a lot of headroom on one machine. When you genuinely run out of it, the next question is whether to split the data across several, which is another post, and mostly an argument for not doing it.