How to find one thing among millions, fast

Holding information has a shape too, and we call that shape a container. Even the same data takes a different shape depending on whether you hold it as a line, a table, or a branch. You don't grab just any container; you pick the one that fits the job. To go through things in order, a line is good; to find something by name fast, a table is good. And no single container does everything equally well. Some actions are fast and some are slow. So picking the right container is the start of a fast program. In the next lessons we'll meet the main containers one by one.

An array is a locker where numbered slots sit packed side by side. Give a number and you jump straight to that slot, pulling it out very fast. A list is slots scattered around, each holding a note with the next slot's address. So to reach the fifth one you must follow the notes from the start, one slot at a time, which is slower. But to slip a new slot into the middle you only fix two notes, so it is easy. An array instead has to push every later slot over, which is a hassle. Need fast access, pick an array; insert in the middle often, pick a list. You trade one for the other.

A stack is stacking plates. You put one on top, and when you take one out, the top (the last one you put in) comes out. So what went in last comes out first. A queue is lining up. You stand at the back, and when you take one out, the front (the one that came first) comes out. So what went in first comes out first. Where do we use them? When you want to undo what you just did or step back, a stack fits perfectly, because the last action is cancelled first, in order. When you want to handle things fairly in arrival order, a queue fits, like a print queue or a numbered ticket. Stacking is last-first, lining up is first-first, that one line is all you need to remember.

A database is a giant warehouse that holds information in an orderly way. It usually tidies things into a table, where one line (a row) is one record and a vertical slot (a column) is a field like name or age. When new information arrives, it goes neatly into the right column of the right table. It differs from just writing into a file in two ways. One, it stores many pieces safely all at once. Two, it quickly finds the one you want even among hundreds of millions. So when you handle a lot of information, you use a database instead of a file.

The simplest way a database finds something is a full scan: read from the start, row by row, to the end. When the data is small it is fast enough. But once the count explodes into the hundreds of millions, there are that many more rows to scan, so it gets slow. That is why we build an index ahead of time. An index is like a sorted list of labels, so instead of scanning everything you jump straight to the spot in a click or two. For the same count, an index finds the answer in far fewer steps than a full scan. How indexes are actually built (index, hash, tree) continues in the next lessons.

Hashing decides a slot number from the value by calculation, then puts in and finds at that very slot. It reaches in one step instead of scanning slot by slot, so it is very fast. The same calculation is used both when putting in and when looking up, so the slot you stored at matches the slot you search. There is a catch too. Two different values can calculate to the same number and head for the same slot, a collision. Then we handle it on the side, by bundling them in one slot or pushing one to a neighbor slot. In short, hashing decides the slot by calculation to find it at once, and handles collisions separately.

Instead of laying data in one long line, put it in a tree shape: from one root it splits into branches and goes down. If your target is bigger than the current spot, go one branch; if smaller, go the other. Then each step down halves the candidates to check. So even thousands are found in a few steps. The number of steps, the depth of the tree, sets the speed. When data doubles, the depth grows by just one step, so even a huge amount deepens slowly. It is just like opening a dictionary at the middle and narrowing by half.

A tree is fast when it finds things by halving down its branches. But if you insert values only in order, the branches never split and grow long on one side, becoming nearly a single line and slowing down. A balanced tree prevents this. When one side gets heavy on insert or delete, it re-seats the nodes by itself, which we call a rotation. By keeping both sides about the same depth through rotations, the depth grows slowly (log) no matter how much data piles up. So it always guarantees a find within just a few steps. We only have to insert and remove, and the tree keeps its balance on its own.

When there is a lot of data, scanning from the start is slow. An index is like the back-of-book lookup, a map built in advance so the database can jump straight to the right spot. There are two kinds. A hash index pinpoints one exact value in a single step. A tree index keeps values sorted, so it is good for scanning a range. But it is not free. An index takes extra space, and when the data changes the index must be updated too. Even so, used well, it makes lookups far faster.

A graph holds things as dots and the relations between them as lines. Put people as dots and friendships as lines, and the connections show at a glance. From one dot, following a line gives a neighbor, and following the neighbor's line gives a friend of a friend. Spreading along lines like this, you can tour a whole connected group. For tasks where relations are the point, like recommending or finding connections, what a table would make you dig for again and again, a graph lets you reach by just following lines. In short, dots are things, lines are relations, and you follow neighbors. That is a graph.

SQL is the language you ask a database to get what you want. You only say two things. First you choose which columns to look at. A table has many columns, and you keep only the ones you want to see. This is called SELECT. Then you set a condition for which rows to keep. Not all rows, only the rows that match the condition. This is called WHERE. When the chosen columns meet the kept rows, a small result table comes out that fits the condition exactly. Taking one table and asking with choosing columns and filtering rows, and getting the answer back as a table, that is the basics of SQL.

Data is usually split across several tables. Orders sit in an orders table, person info in a customers table, apart. Looking at one table alone cannot answer questions that cross tables. So we find a common column both tables share, like the customer number. Matching rows whose value in that column is equal links the two tables into one line. Linked this way, they can be treated like one table, answering questions such as the name behind an order. In short, a join links scattered tables by matching rows on a common column.

Normalization is the tidying where you take information that repeats across one table, split it into a separate table, and re-link them by a shared column. Instead of writing the customer name on every order, write the customer once in a customer table and leave only a customer number on the order table. Then if the number changes you fix one row in the customer table and you are done, so no mismatch arises. There is also no missing a scattered row while fixing them one by one. But if you split too finely, every time you look at something you must join many tables back together, which can be slow. Then you may deliberately merge often-viewed information back into one table, which is called denormalization. In the end, normalization is the balance of splitting out repeats and linking by relation, yet merging back when split too fine.

A transaction treats several edits as one bundle so that all happen or none do. When a take and an add are a pair, like a transfer, only when both finish does it really apply. If the power dies or something goes wrong midway, it does not leave half done but rolls the whole thing back to the earlier state. This is called a rollback. And when several people try to change the same balance at once, it handles them one at a time so they do not overwrite each other. The tangle of all-at-once becomes an orderly line. In short: all or nothing, roll back on a slip, and no tangling even at once. These three are the transaction.

Caching keeps a copy of often-used data in a nearby place. A far store is slow because the trip there and back is long. But with a copy close by, from then on you pull it through a short path at once. If what you want is in the cache, we call it a hit and fetch it fast. If not, we call it a miss, go all the way to the far place, bring it back, and leave that copy in the cache. So next time it becomes a hit. There is a catch too. Even after the original changes, the old copy stays in the cache and may hand out an old value. We say the cache has gone stale. So now and then we refill the cache or drop it after some time, to keep old values out. In short, keep a copy close so a hit is fast, and refresh the cache when the original changes, that is caching.

Compression is the craft of holding the same information in less space. There are two skills. One is cutting repetition. When the same thing runs on like AAAA, writing A four times makes it shorter. The other is giving a short code to a piece that shows up often. Swapping a long piece for a short symbol shrinks the whole. And a compressed copy, once undone, is exactly the original; nothing was thrown away. This is called lossless. Compress harder and it gets smaller, but compressing and unpacking take more time. So you trade off how small against how fast. In short, cut repetition and give short codes to pack it small, while undoing it gives back the original; that is compression.

When data grows too big for one machine, you cut it into pieces and split it across several. This is called distribution, or sharding. Each machine holds only part of the whole, so together they can hold even very big data. And so nothing breaks when one machine dies, you copy the same data onto several machines. This is called replication. Distribution, which splits, and replication, which copies, are different ideas. Distribution chops the load and shares it out; replication keeps the same load in several places. For this huge and fast handling, a container that loosens the strict table form is called NoSQL. It is like a much bigger version of the hash container that puts in and finds a value straight by its key, so it becomes a bridge to the enormous data handled by the next area, artificial intelligence.