Indexing and B-Trees in Databases: Complete Beginner's Guide

An index is a lookup structure that finds rows without scanning the whole table — like the index at the back of a textbook. A B-tree (balanced tree) powers almost every database index: it keeps keys sorted across levels so any search, insert, or delete needs only a few disk reads, even for millions of rows.

It matters because disk access is slow. Scanning a million-row table reads a million rows; a B-tree index finds the same row in about three hops. That gap — seconds versus milliseconds — is why indexed queries feel instant and unindexed ones time out.

Key Concepts

• B-tree of order m: each node holds up to m − 1 keys and m children; every non-root node holds at least ⌈m/2⌉ − 1 keys. All leaves sit at the same depth, so the tree stays balanced.
• Node / page: one disk block (often 4–16 KB) of sorted keys plus child pointers.
• Clustered vs non-clustered: a clustered index sets the physical row order (one per table); non-clustered indexes are separate structures pointing at rows.
• Composite index: an index on (City, Age) speeds filters on City, or City and Age — but not Age alone.
• B+ tree: the variant real databases use — all data in the leaves, linked left to right for fast range scans.
• Selectivity: how choosy an index is. Gender (2 values) helps little; Email (unique) helps enormously.

Formulas

• Height: h ≈ log_m(N), where m is the branching factor and N the key count — measured in disk reads per lookup.
• Keys per node: minimum ⌈m/2⌉ − 1 (root may hold just 1), maximum m − 1.
• Lookup cost: O(log_m N) node visits, roughly h page reads.

Assumes fixed-size keys and the B-tree invariant (nodes at least half full). Heavy deletes shrink the effective fan-out but the height bound still holds.

Worked Example

Table of N = 1,000,000 student rows; B-tree index of order m = 101 (up to 100 keys, 101 children per node):

1. Root: 1 node → up to 101 children. Level 1: up to 101 nodes → up to 10,201 children.
2. Level 2: up to 101³ = 1,030,301 leaf slots ≥ 1,000,000 — three levels suffice.
3. Any lookup touches at most 3 nodes = 3 disk reads, versus a 1,000,000-row scan — about 333,000× fewer reads worst case.
4. Range query: IDs 5000–5100: find key 5000 in 3 reads, then walk linked leaves — ~100 extra reads instead of scanning everything.
5. Write cost: each insert costs ~3 reads plus occasional node splits — why many indexes slow down writes.

Common Misconceptions

• "Indexes make everything faster." They speed reads but slow writes — every INSERT/UPDATE/DELETE must update each index. Indexing every column is a classic mistake.
• "An index on (A, B) helps queries on B." No — it is ordered by A first, so it helps filters on A (or A and B) only.
• "The database always uses my index." The optimizer skips it when a full scan is cheaper — e.g. a filter matching 40% of the table.

Real-World Applications

• Primary keys: backed by B-tree indexes — why lookups by ID are instant.
• E-commerce filters: indexes on category, price, and brand filter millions of items in milliseconds.
• Joins: indexes on foreign-key columns make table joins fast.
• Log analysis: timestamp indexes pull "last hour's errors" from billions of rows.

A B-tree turns a million-row hunt into a three-hop walk: each level multiplies reach by the fan-out, so depth grows only logarithmically. Index the columns you filter and join on, respect the leftmost-column rule, and remember the deal — faster reads for slower writes.