Understanding SQL Indexes and Query Performance

How a B-Tree Index Is Organized

Most general-purpose indexes (the default in Postgres, MySQL's InnoDB, SQL Server, SQLite) are B-trees (or one of its variants, B+trees) — a balanced tree structure where every leaf is the same distance from the root, keeping lookups predictable regardless of which value you're searching for.

• Internal nodes hold routing keys that guide a search toward the correct branch, the way a dictionary's guide words at the top of a page tell you whether to keep flipping forward or back.
• Leaf nodes hold the actual indexed values, in sorted order, each with a pointer back to the full row (or, for a clustered index, are the full row — see the next chapter).
• Because leaves are linked and sorted, a B-tree efficiently answers not just exact-match lookups (= 'Sales') but also range queries (salary BETWEEN 50000 AND 70000, ORDER BY salary) by walking the sorted leaves — this is a genuinely important property that distinguishes a B-tree from a hash index, which only supports exact-match lookups efficiently.
• The tree stays balanced automatically as rows are inserted, updated, and deleted — the database splits and merges nodes internally, which is precisely the maintenance work that makes writes to an indexed column more expensive than writes to an unindexed one.

A hash index (available in some engines as an alternative index type) trades away range-query support for theoretically faster exact-match lookups — it's rarely the default and rarely worth reaching for unless a specific workload is proven to be exact-match-only and lookup-latency-critical.