Why Does PostgreSQL’s B‑Tree Index Behave Like a B+ Tree?

Hello, I’m Jun. We know MySQL uses B+ trees for indexes, while PostgreSQL uses B‑trees. Why doesn’t PostgreSQL adopt B+ trees? Let’s explore.

B+ Tree and B- Tree

B+ Tree

B+ tree primary index leaf nodes store data, while internal nodes store keys and pointers. This allows binary search in internal nodes with O(log_m N) complexity, where N is total nodes and m is fanout. After locating the data page, retrieving the row is straightforward.

B+ tree also links leaf nodes with a doubly linked list, giving excellent range query performance with O(log_m N + K) complexity.

B- Tree

Unlike B+ tree, B‑tree stores data in all nodes, including root, internal, and leaf nodes.

Random query: Because B‑tree can store data in non‑leaf nodes, the search may terminate earlier, shortening the path.

Range query: B‑tree needs inorder traversal across multiple levels, which is less efficient than B+ tree.

PostgreSQL Index

Index Overview

PostgreSQL modifies the B‑tree structure. The top page is a metadata page storing root information. Internal pages contain keys and pointers to child pages. Leaf pages store pointers (TIDs) to actual table rows.

TID (Tuple Identifier) is a physical address composed of page number and row offset, used because PostgreSQL stores table data in a heap separate from indexes.

Since leaf nodes store only TIDs, more leaf entries fit per page, making the tree shallower compared to B+ tree for the same data volume.

Both internal and leaf pages store data in ascending order, and leaf pages are linked by a doubly linked list, allowing ordered traversal without inorder scans for range queries.

Index page format (from official docs):

Explanation of each attribute:

PageHeaderData: 24‑byte header with general page info, including free space pointers.

ItemIdData: Array of item identifiers (offset, length) pointing to actual items, 4 bytes each.

Free space: Unallocated area; new identifiers allocated from the start, new items from the end.

Items: The actual items.

Special space: Index‑method‑specific data; empty for ordinary tables.

Although PostgreSQL calls its index a B‑Tree, it implements B+‑tree functionality.

Three Optimizations

Deduplication: When many identical key values exist (e.g., a frequently updated status flag), PostgreSQL merges them, storing a single key with a list of TIDs, saving space and improving cache efficiency.

Index‑Only Scan: Leaf nodes can also store additional non‑indexed column values, acting like a covering index, allowing queries that need only indexed columns to be satisfied without visiting the heap.

Reverse‑Key Index: PostgreSQL can create indexes with reversed sort order to mitigate insert hotspots for monotonically increasing keys. Example:

CREATE INDEX idx_emp_id ON tb_emploee(emp_id REVERSE);

Conclusion

PostgreSQL’s index structure is named B‑Tree but effectively provides B+‑tree capabilities, and includes optimizations such as deduplication, index‑only scans, and reverse‑key indexes to enhance performance.