Databases and indexes

A database stores data durably, finds it quickly, and keeps it correct when many things happen at once. There are two broad families, and the choice shapes the rest of your design: relational (SQL) databases and non-relational (NoSQL) databases. Neither is better. They are good at different jobs.

A relational database stores data in tables of rows and columns, with a fixed schema that every row must follow. Tables are connected by keys, and you combine them with a join. Examples are PostgreSQL and MySQL.

Their great strength is transactions with ACID guarantees:

• Atomicity: a group of changes happens entirely or not at all.
• Consistency: data always obeys the rules you set.
• Isolation: concurrent transactions do not see each other's half-finished work.
• Durability: once committed, data survives a crash.

This is exactly what you want for money, orders and accounts. The weakness is scale: spreading one relational database across many machines while keeping joins and transactions is hard, so they usually grow upward first.

NoSQL covers several designs, each tuned for a shape of data.

• Key value stores map a key to a value. They are extremely fast and easy to spread across machines.
• Document stores keep flexible, self-contained records such as JSON.
• Wide column stores hold huge tables with many columns per row, spread across a cluster. They suit very large writes and reads by key.
• Graph stores model connections, such as friends of friends.

They usually give up some of the relational promises, such as joins or strict cross-record transactions, and often offer eventual consistency: copies agree after a short delay. In return they scale out easily and the schema can change freely.

Ask four questions in order.

• What does the data look like, and how are the pieces related?
• How will it be queried: by key, by range, by complex conditions?
• How strict must correctness be? Is a brief disagreement between copies acceptable?
• How big will it get, and how fast will it grow?

For our link shortener, the main table has billions of small rows, no joins, and every read is a lookup by key. That fits a key value or wide column store. User accounts are small and need strong rules, so a relational table is fine. Using both is normal and sensible.

Without help, finding a row means reading every row until you hit it, a full scan. With 30 billion links that is hopeless. An index is a separate sorted structure that points to rows, like the index at the back of a book.

Most databases use a B-tree. It keeps keys in sorted order across wide nodes, so each step narrows the search enormously. If each node holds about 500 keys, then four levels address 500 x 500 x 500 x 500, about 62 billion rows. A lookup in 30 billion rows takes about four reads, not 30 billion.

Indexes are not free. Every index must be updated whenever a row is inserted, changed or deleted, so each extra index slows writes. Each also uses memory and disk. A table with many indexes can write several times slower than one with none.

A few practical rules follow.

• Index the columns you filter or sort by often, and no more.
• For a combined filter, a composite index helps, but column order matters: it serves queries that start with its first column.
• Read heavy tables tolerate more indexes than write heavy ones.

Our key lookup uses the primary key, which is indexed by default, so redirects stay fast without any extra index. If you also want "all links owned by this user", add an index on the owner, and accept the small write cost.