Understanding B‑Tree Indexes Across Major Relational Databases

Why Indexes Matter

When a web or mobile application goes live, the most common performance bottleneck is slow query execution caused by full‑table scans. Properly designed indexes allow the database engine to locate rows by traversing a B‑Tree instead of scanning every row, often delivering orders‑of‑magnitude speedups. Adding more hardware can only mask the problem; the root cause is usually inefficient data access.

Core Concept of B‑Tree Indexes

A B‑Tree is a balanced tree structure where each non‑leaf node stores a range of key values and pointers to child pages. Leaf nodes contain the indexed key values together with a reference to the actual row – either a ROWID (physical address) or the primary‑key value of the clustered index. Because the tree is balanced, the number of page reads required to locate a key grows logarithmically with the size of the table.

Oracle B‑Tree Indexes

In Oracle:

Non‑leaf blocks store only the maximum key value for the block and a pointer (file‑number + block‑number) to the next level.

Leaf blocks store the indexed column(s) plus the ROWID of the row in the heap segment.

Oracle also supports Index‑Organized Tables (IOT), where the table data itself is stored in the index leaf pages, eliminating the need for a separate heap.

Because the leaf contains the ROWID, a single index lookup can retrieve the row without an additional table access.

MySQL (InnoDB) B‑Tree Indexes

InnoDB distinguishes two index types:

Clustered index (primary key) : The table’s data rows are stored in the leaf pages of the primary‑key B‑Tree. Each leaf page contains the primary‑key value and the full row data, so the table is physically ordered by the primary key.

Secondary (non‑clustered) index : Leaf pages store the indexed column(s) plus the primary‑key value of the row. To fetch the full row, InnoDB performs a two‑step lookup – first using the secondary index to obtain the primary key, then using the clustered index to retrieve the row.

If a table has no explicit primary key, InnoDB creates a hidden 6‑byte row identifier and uses it as the clustered key.

SQL Server B‑Tree Indexes

SQL Server also provides clustered and non‑clustered indexes:

If a clustered index exists, the leaf pages of a non‑clustered index store the clustered key values (the primary key). The engine then performs a “bookmark lookup” (also called a non‑clustered index lookup) to retrieve the full row.

If the table is a heap (no clustered index), the leaf pages of a non‑clustered index store a RID (record identifier) that points directly to the row’s physical location.

Creating a clustered index on a heap reorganizes the table so that the data rows become the leaf pages of the new clustered index.

PostgreSQL B‑Tree Indexes

PostgreSQL’s B‑Tree implementation is similar to Oracle’s in that leaf pages store only the indexed key values. PostgreSQL does not distinguish between clustered and secondary indexes; tables and indexes are stored as separate files, each consisting of 8 KB pages.

Because PostgreSQL uses Multi‑Version Concurrency Control (MVCC), an index lookup may still require a heap fetch to verify row visibility. Even a covering index (where all queried columns are indexed) can trigger a “heap fetch” if the row version needed for the transaction is not visible in the index alone.

Key Differences Across Engines

Storage of Row Reference : Oracle stores ROWID in leaf pages; InnoDB stores the primary‑key value; SQL Server stores either the clustered key or a RID; PostgreSQL stores only the key and relies on MVCC for visibility checks.

Clustered Index Requirement : InnoDB always has a clustered index (implicit if none defined). SQL Server clusters are optional. Oracle and PostgreSQL treat clustering as a separate table property (IOT in Oracle, CLUSTER in PostgreSQL).

Index‑Only Scans : Oracle and MySQL can perform true index‑only scans when all needed columns are in the index. PostgreSQL can do index‑only scans only when the visibility map indicates that the row version is visible, otherwise a heap fetch occurs.

Physical Organization : Oracle and SQL Server store data and indexes in the same tablespace (segments). PostgreSQL stores each table and each index in separate files, which influences backup and recovery strategies.

Practical Guidance for Developers

Always define a primary key; it becomes the clustered index in InnoDB and the default clustered index in SQL Server.

When a query filters on a column that is not the primary key, create a secondary index on that column. Remember that in InnoDB and SQL Server this will add an extra lookup step.

For read‑heavy workloads, consider covering indexes (include all SELECTed columns) to avoid bookmark lookups.

In PostgreSQL, monitor the visibility map (using VACUUM) to maximize the benefit of index‑only scans.

Beware of index bloat: frequent updates or deletes can leave empty space in leaf pages. Periodic REBUILD INDEX (Oracle), OPTIMIZE TABLE (MySQL), or ALTER INDEX REBUILD (SQL Server) can reclaim space.