Indexes & Query Performance

B-Tree Indexes

A B-tree keeps sorted separator keys in a shallow, balanced page hierarchy. Navigation finds a leaf boundary; linked or successive leaves support ranges and order, while splits, occupancy, concurrency, and row fetches shape real cost.

Fan-out keeps trees shallow.
Leaves hold the searchable order.
Balanced means bounded path length, not constant I/O.
Splits preserve order under growth.
B-trees can satisfy ordering.
Wide or random keys change economics.

Seek, range scan, and split

Seek to a boundary, then walk the range

CREATE INDEX orders_placed_idx ON orders (placed_at);

SELECT order_id, placed_at
FROM orders
WHERE placed_at >= TIMESTAMP '2026-05-01 00:00:00'
  AND placed_at <  TIMESTAMP '2026-06-01 00:00:00'
ORDER BY placed_at;

Physical stages
Stage	Mechanic	Cost drivers
Root/internal descent	Compare separator keys and choose child	Height, cache, key width
Leaf positioning	Binary/search-method lookup within page	Page format and compression
Range advance	Consume ordered leaf entries	Matching entries and leaf pages
Row retrieval	Follow locator unless covered	Clustering, visibility, random access
Insert/split	Place key; redistribute if full	Free space, key pattern, contention, logging