Data Storage Fundamentals

A relational database keeps data in tables, like class lists on a clipboard. Each row is one thing, such as one kid. Each column is one fact about it, such as a name or a class. Every row has its own ID number, called the primary key, so nobody gets mixed up even when two kids share a name.

Tables link to each other by storing those ID numbers. The lunch table does not copy a kid's name. It just says kid 1 ordered soup. When you need both, the database matches the rows up for you. This is called a join, and you ask your questions in a language called SQL.

The shape is strict. You decide the columns up front (the schema), and the database refuses data that does not fit, like a lunch order for a kid who does not exist. Changes happen in transactions that are all or nothing: if you move a book from one shelf to another, it is never lost halfway. These promises are called ACID: all or nothing, the rules always hold, people working at the same time do not trip over each other, and saved means saved, even after a crash.

Relational databases like PostgreSQL and MySQL are a great fit when data is connected and correctness matters, like money, orders and grades. The trade-off is that one main machine usually takes all the writes. You can add copies that help with reading, but splitting the data across many machines is hard work.

Non-relational databases, often called NoSQL (short for not only SQL), give up some of the strict table rules in exchange for other strengths. Many of them were built to spread across lots of machines from day one, by splitting the data up by its key. Their flexible shape also means you can add a new field without changing every old record.

The trade-offs: there are usually few or no joins, so you store data in the shape you will read it. Some give weaker promises by default. For example, a copy on another machine may be a moment behind, which is called eventual consistency. And flexible shapes mean the app itself must cope with records that look different from each other.

Neither kind is better. Pick relational when data is linked and must be exactly right. Pick a NoSQL family for huge scale, very simple lookups, shapes that keep changing, or questions about connections. Many apps use both.

There are four main NoSQL families, and each one is shaped like a different kind of shelf:

• Key-value store: numbered lockers. Give a key, like locker 7, and get back whatever is inside. Very fast, but you can only look things up by the key. Examples: Redis, DynamoDB.
• Document store: folders with papers inside. Each folder (document) holds everything about one thing, and two folders do not need the same fields. Example: MongoDB.
• Wide-column store: a giant sticker book. Each page has a key and can hold its own set of stickers (columns), kept in sorted order. Built to swallow huge numbers of writes across many machines. Examples: Cassandra, HBase.
• Graph database: kids joined by friendship strings. Great for questions like who are my friends' friends. Example: Neo4j.

Imagine finding every page about dinosaurs in a 500 page book by reading every page. That is what a database does with no index: it checks every single row, which is called a full scan. An index is like the list at the back of the book: dinosaurs, pages 12, 40 and 210. You jump straight there.

An index is a separate, sorted list of one column's values, and each value points to where the full row lives. A table can have several indexes, one for each common question.

Indexes are not free. Each one takes extra space. And every time you add, change or delete a row, every index on that table must be updated too, so writes get slower. That is why you index the questions you ask often, not every column.

Different jobs need different kinds of index. The next three parts look at the big ones: B-trees for sorted lookups, inverted indexes for searching words, and LSM trees, a way of organizing data for very heavy writing.

Picture a huge library with signposts. The first sign says: A to L go left, M to Z go right. The next sign splits again, and again, until you are standing at the right shelf. A B-tree works the same way. It is a tree of sorted signposts, and it stays balanced, which means every shelf is the same number of steps from the front door.

Real B-tree signposts are big. Each one is a page on disk holding hundreds of keys, so the tree stays very short. Even with millions of rows, a lookup usually takes only 3 or 4 hops. Because everything is kept in order, B-trees are great for exact questions (find Pia) and range questions (everyone from F to N, or all orders from last week). Most databases also link the bottom shelves together in order, so a range search can simply walk sideways.

B-trees are the default index in most relational databases. When data changes, the B-tree updates the right page in place, and when a page gets too full, it splits in two. The trade-off is that writes jump around to many different pages on disk, which is slower than just adding to the end of a file.

A normal list goes from a document to the words inside it. An inverted index flips that around: it goes from each word to the list of documents that contain it. It is just like the index at the back of a book, and it is the heart of every search engine.

To build it, each document is split into words, the words are tidied up (for example made lowercase), and the document's ID is added to the list for every word it has. Each list is kept sorted, which makes lists easy to combine.

To search for cat AND dog, look up the cat list and the dog list, and keep only the documents found in both. To search for cat OR dog, merge the two lists. Search engines also keep extra notes, like how often and where a word shows up, so they can put the best matches first.

The trade-off: the index can be large, and adding one document touches many word lists. So search tools like Elasticsearch add new documents in small batches and merge them in the background, which means a brand new document may take a moment to show up in search.

Some apps write all the time, like a game saving every move or a sensor sending a reading every second. Fixing signposts in place for every write would be slow. An LSM tree (log-structured merge tree) takes a different path: it never edits old files. It only writes new ones.

Each new write does two quick things. First it is added to the end of a write-ahead log on disk, a plain diary so nothing is lost if the power goes out. Then it goes into a small sorted table in memory, called the memtable. When the memtable fills up, it is written to disk in one go as a sorted file that never changes, called an SSTable (sorted string table). Writing big sorted batches is much faster than poking at many places on disk.

Over time the files pile up, so a background job called compaction merges them into bigger sorted files, keeps only the newest version of each key, and throws away old and deleted ones. A delete is written as a small marker called a tombstone, which hides the old value until compaction removes both.

Reading is the harder part. To find a key, look in the memtable first, then in the files from newest to oldest. To avoid opening every file, each file has a bloom filter, a tiny summary that answers either definitely not here or maybe here. It never says not here when the key really is there. LSM trees power write-heavy databases like Cassandra and RocksDB. The costs are slower reads when many files must be checked (read amplification) and extra disk work as compaction rewrites data again and again (write amplification).

A schema is the plan for how data is shaped: which tables or documents, which fields, and how they link. A good schema starts from the questions the app asks most, called access patterns. If the home screen shows each kid with their class and teacher a million times a day, the data should make that exact question easy.

Normalizing means storing each fact in exactly one place. The teacher's name lives only in the classes table, and each kid just points to a class. If the teacher's name changes, you fix it once, and no copy can disagree. The cost is that reads need joins to put the pieces back together.

Denormalizing means copying some facts on purpose, so a read gets everything in one look, with no join. It is worth it when reads vastly outnumber writes. The cost is that every copy must be updated when the fact changes, and one missed copy means two places tell different stories.

• Design around your most common questions, not around how the data looks on paper.
• Normalize by default. Denormalize on purpose, for a measured reason, and have a plan to keep copies in sync.
• Use the right types and sizes: a date as a date, and money as whole cents or an exact decimal, never a number type that can round in odd ways.
• Index the questions you ask often, and drop indexes nobody uses, because each one slows down writes.
• Avoid one giant table that does everything. Keep big, rarely needed things, like profile pictures, apart from the small facts you read all the time.