You run SELECT * FROM pedidos WHERE cliente_id = 2421 and, depending on the table, the answer takes an instant or several seconds. The only meaningful difference between the two cases is usually a structure we almost never hear about: the index, and specifically its real shape, a B-tree. When it is well designed, that tree turns a read that would touch millions of rows into one that barely brushes a few pages on disk.
The problem it solves: reading the whole table
Without an index, the database has no way to know where customer 2421 lives. It can only sweep the whole table, row by row, comparing the value in each one against what you are looking for. That is what is called a sequential scan. With ten million rows, that means ten million comparisons, and if much of the data does not fit in memory, most of the time goes into reading data from disk. The result: hundreds of milliseconds or whole seconds.
An index reverses that situation. Instead of asking “where is the row”, you build a search structure in advance that tells you in a few steps exactly where each value lives. The question becomes “which page holds the key 2421?”, and the answer arrives after descending a few levels of a tree.
What a B-tree actually is
A B-tree is a balanced, multiway search tree: each node can have many children, not just two as in a binary tree. In a database, each tree node corresponds to a page, the smallest unit of disk read and write: 8 KB in PostgreSQL, 16 KB in InnoDB, the storage engine of MySQL/MariaDB.
Inside a node the keys are kept sorted. If a node has k keys, it has k+1 children, and each child covers an interval between two consecutive keys. To search, you start at the root, compare the sought value with the node’s keys and decide which child to descend to. Because the keys are sorted, you discard all other subtrees at every step.
Why not a binary tree
The choice of a B-tree has a deep reason: the real bottleneck is disk access, not the CPU. Reading a page from disk costs on the order of milliseconds; comparing keys in memory takes nanoseconds. That is six orders of magnitude of difference. So the goal is to minimize the number of pages read, that is, the number of tree levels you must traverse.
A binary tree stores one key per node, so with a million rows you need roughly 20 levels of depth: 20 disk accesses. A B-tree, with a typical fanout (branching factor) of between 200 and 300 keys per page, pushes the depth down to three or four levels. For millions of rows, the search is solved by reading the root, a couple of intermediate nodes and the final leaf: three or four disk reads that, on top of that, are usually in the cache after the first time.
How the work is split between nodes
The tree is divided into two kinds of nodes. Internal nodes only store keys and pointers to their children: they are the “navigation index” that tells you where to descend. Leaves are the last-level nodes and hold the data or references to it.
Here an important difference appears between engines. In InnoDB, data lives inside the leaves of the index, ordered by the primary key: it is a clustered index, which is why “the table” does not exist separately, only the index whose leaves are the table. In PostgreSQL, by contrast, the leaves store the TID (tuple id), an address pointing to a row inside a separate heap: it is a non-clustered index. Fetching a row back from the heap after an index returns it is called a table lookup, and if it touches too many rows it can end up slower than scanning the whole table.
Balanced without rotations, paying with space
That the tree stays balanced —all leaves at the same depth— is key to keeping the cost predictable. Unlike an AVL tree, which rebalances with rotations, a B-tree grows by splitting nodes: when one fills up, it splits in two and the middle key moves up to the parent. The splits propagate upward, and only when the root fills does the tree’s height grow, doubling at once.
That convenience has a price: wasted space. Nodes are rarely 100 % full. After millions of insertions, typical density hovers around 70-80 %, and on a heavily modified table you can see half-empty pages. Moreover, each insert or delete in the middle of the order may force pages to be rewritten and split: that is what storage people call write amplification, and it is why inserting into an index costs more than appending rows at the end of the table.
When an index is useless
The B-tree is not a universal answer. On a tiny table, reading the cache and scanning it is usually cheaper than maintaining an index, and the query planner sometimes ignores it on purpose. It also does not help with low-cardinality columns —like a sex field with two values— because each leaf would return a million rows and the planner would prefer the scan. And an index is designed to look up point values or bounded ranges; if in your query the column is wrapped in a function (WHERE DATE(fecha) = ...), the index cannot be used because the tree is ordered by the raw value, not by its result.
Maintaining an index is not free either: every write on the table must update the tree, and each extra index slows down inserts and takes disk space. It is a trade-off. The practical rule planners apply is to quantify the estimated cost in pages read and pick the cheapest path, whether an index or a plain scan.
The reads you do without noticing
When you fetch your cart, the database does not use “one” index: it uses several at once, crosses results and combines trees. Behind every WHERE x = ..., every ORDER BY or every foreign key there is, almost always, a B-tree doing exactly what you just saw: comparing keys, descending levels, and touching the disk as little as possible. That a query takes milliseconds and not seconds is not magic: it is a tree of hundreds of megabytes that learned not to read what it does not need.
