A B-tree index stores indexed values in sorted order, letting PostgreSQL search a balanced tree instead of scanning every table row. PostgreSQL uses B-tree as its default general-purpose index type. section 4.1 section 4.2
A B-tree supports efficient ordered access through several structural features:
- Root and branch nodes direct searches toward leaf nodes containing references to table records. section 4.1
- Linked leaf nodes preserve index order, allowing range queries and ordered retrieval without repeatedly navigating upward. section 4.1
- Searches require O(logᵦN) index lookups, so lookup growth remains comparatively small as indexed data grows. section 4.1 section 4.5.1
- Equality, comparison, and BETWEEN predicates can use B-tree indexes across supported data types. section 4.5.1
Speeding up a score range query
A game initially counts players with scores between 5,000 and 6,000 using a sequential scan. Create a descending B-tree index, then inspect the new plan: CREATE INDEX idx_score ON game.player_stats(score DESC); EXPLAIN (analyze, costs off) SELECT count(*) FROM game.player_stats WHERE score BETWEEN 5000 AND 6000; The plan changes from Seq Scan to Index Only Scan using idx_score, returning 970 rows with zero heap fetches. The same index also supports a leaderboard ordered by score: SELECT username, score, level FROM game.player_stats ORDER BY score DESC LIMIT 5; section 4.5.1
B-trees also back composite indexes, expression indexes, and indexes on date/time columns. For JSON, index the queried expression such as (pizza ->> 'type') rather than the entire JSON value; otherwise JSON-specific operators do not benefit from the B-tree. Specialized BRIN indexes can be smaller for large, append-oriented time-series tables when values correlate with physical row location. section 5.6.1 section 9.7.1 section 9.7.2
Figure 4.1 A sample B-tree index showing the search path to the index entry with ID = 5
Trace the search for ID = 5 from the root through branch nodes to the matching leaf entry. section 4.1
