B-tree Index

A B-tree index keeps keys in sorted order in a balanced tree. Internal pages direct a search toward a key range; leaf entries identify matching keys and rows. Instead of checking every order, an index on customer_id can navigate to one customer’s entries and walk through that range.

Finding the first key is only part of the work. Returning many matches can require many index entries and table visits, so an indexed query is not automatically cheap. If most rows match, a sequential scan may cost less. Cached pages also mean a page visit is not necessarily a physical storage read.

An index adds storage and maintenance work. Inserts, deletes, and some updates change index structures as well as table data. Measure the relevant read and write workload, and check whether the index enforces a constraint before removing it. A B-tree orders its own keys; it does not promise that a SQL result is sorted without ORDER BY.

Further reading

• PostgreSQL Documentation, Index Types

See the worked examples in Relational Database Internals.