That your database answers in milliseconds is not magic: it is a tree called B+, a data structure that rearranges your rows so that the disk is read the absolute minimum. It is arguably the piece of software that speeds up the most queries in the world, and almost no one ever sees it working.
Think of a table with ten million rows. Without any index, the engine would have to examine every single one to find a match: a sequential scan that turns a trivial query into an operation of seconds in the worst case. The B+ index exists precisely to avoid that scan. It is a secondary structure that keeps an ordered copy of a few columns and, in every leaf, the physical reference to the full row.
Why a tree and not a list
A B+ tree is a balanced search tree, a relative of the better-known binary trees but with one decisive difference: each node can have hundreds of children, not just two. That is exactly what makes it work well on disk, because the real cost of a read is not computing but moving data from the physical medium. With a high branching factor, the depth of the tree is tiny: in practice, an index over millions of rows fits in three or four levels. Finding a value costs, at most, three or four page reads of a few kilobytes each, even if the table weighs tens of gigabytes.
There is another key detail in the letter “B”: the structure stays balanced automatically. As you insert and delete rows, the tree splits and merges along its branches so that every path from root to leaves has the same length. That invariant is what guarantees that lookup time does not degrade with use.
Internal nodes and leaves: two different jobs
An indexed access never goes straight from the root to disk. Each piece of data ends up in a leaf, which stores the values of the indexed column in ascending order together with a pointer to the real row in the table. Internal nodes, by contrast, hold no data: they only act as a routing guide, with separator keys and pointers to the nodes one level below. The search algorithm walks those internal nodes, taking the correct branch for the value sought, until it reaches the leaf that holds the result.
That separation between internal nodes and leaves is not a whim. By chaining the leaves together with pointers, the B+ allows very efficient sequential scans: to return a range of values, the engine advances from leaf to leaf without climbing back up the tree. That is why most modern engines, from PostgreSQL to MySQL with InnoDB, adopt the B+ rather than the classic B tree.
Clustered vs. secondary index
It is worth distinguishing two types. A clustered index physically orders the table itself following the index: the full rows live inside the leaves. In InnoDB, for example, the primary key works this way, which is why it is wise to choose it carefully. A secondary index, in contrast, stores only copies of its columns and a pointer to the record in the clustered index. That pointer adds an extra level of indirection, which is worth it because a single secondary index cannot organize the whole table.
There is also a common trick: the covering index. If the query asks for exactly the columns already present in the index, the engine can answer without touching the table at all, reading only the leaves of the index. It is one of the most profitable optimizations that exist, because it cuts the work down to a handful of reads instead of tens of thousands.
The hidden cost: not everything is an advantage
An index is not free. Every insert, delete, or update of a row must also maintain the tree, adding writes and fragmentation. That is why it makes no sense to index every column: you pay on each write operation and in disk space. The pragmatic rule is to index what gets queried in WHERE filters, in JOINs, and in ORDER BY, and always to measure with the execution plan (your engine’s EXPLAIN) before deciding.
Seen up close, the B+ is an almost elegant engineering lesson: it does not optimize computation but the movement of data, which is the real bottleneck. When your application answers in milliseconds over millions of rows, you can be sure that, behind it, there is a quiet, balanced tree doing the work.
