LLM Best Practices

B-tree Index

2 min read

View markdown source

Definition

A B-tree (Balanced tree) index stores keys in sorted order across a balanced tree of fixed-size pages, with leaf pages holding key values and heap tuple identifiers (TIDs). Internal pages hold routing keys that guide searches to the correct leaf. The tree self-balances on insert and delete, keeping all leaf pages at equal depth.

B-tree indexes are useful for:

  • Equality: WHERE col = $1
  • Range: WHERE col BETWEEN $1 AND $2
  • Prefix match on strings: WHERE col LIKE 'prefix%'
  • Ordering: ORDER BY col (index-only or index scan avoids a sort node)
  • IS NULL: WHERE col IS NULL (Postgres B-trees store NULL keys)

B-tree indexes are not useful for full-text search, JSONB containment, array overlap, or nearest-neighbor vector search. Use GIN for those.

Index size grows linearly with cardinality. A partial index (WHERE active = true) covers a subset and stays smaller. A covering index (INCLUDE (col1, col2)) enables Index Only Scans for queries that read only the included columns.

When it applies

Create a B-tree index on any column used in WHERE, JOIN ON, or ORDER BY that results in a sequential scan on a table with more than a few thousand rows. Create composite indexes with the equality column(s) first and the range or sort column last: (user_id, created_at DESC). Monitor index bloat with pg_stat_user_indexes; rebuild with REINDEX CONCURRENTLY if idx_tup_read / idx_tup_fetch diverges widely.

Example

CREATE INDEX idx_orders_user ON orders (user_id);
CREATE INDEX idx_orders_user_date ON orders (user_id, created_at DESC);
CREATE INDEX idx_orders_pending ON orders (created_at) WHERE status = 'pending';
CREATE INDEX idx_orders_covering ON orders (user_id) INCLUDE (status, total_cents);
  • query-plan - the query planner decides whether to use the B-tree or a sequential scan.
  • gin-index - GIN is the alternative for full-text, JSONB, and array operators.
  • sequential-scan - what the planner falls back to when B-tree is not cost-effective.
  • postgres - the Postgres deep-dive.
  • postgres-explain - reading EXPLAIN output to confirm index usage.

Citing this term

See B-tree Index (llmbestpractices.com/glossary/btree-index).

Graph View

Backlinks