Index Types: B-tree, Hash, GIN, GiST

B-tree isn't your only option. Different query patterns call for different index types. Choose the wrong one and your index might not be used at all.

Index Type Overview

B-tree: The Default Workhorse

B-tree is the default in PostgreSQL and MySQL. It handles most use cases well.

-- B-tree is the default
CREATE INDEX idx_users_email ON users(email);

-- Explicitly specifying (same result)
CREATE INDEX idx_users_email ON users USING btree(email);

When B-tree Shines

B-tree Limitations

-- B-tree CANNOT help with these patterns:

-- Suffix or infix search
WHERE email LIKE '%@gmail.com'  -- Scans all rows

-- Case-insensitive without proper setup
WHERE LOWER(email) = 'john@test.com'  -- Scans all rows (need functional index)

-- NOT conditions often skip index
WHERE status != 'deleted'  -- Usually scans all rows

Hash Indexes

Hash indexes use a hash table for O(1) lookups. Only for equality checks.

-- Create a hash index
CREATE INDEX idx_users_uuid ON users USING hash(uuid);

Hash vs B-tree Performance

GIN: Inverted Indexes

GIN (Generalized Inverted Index) is perfect for composite values - arrays, JSONB, and full-text search.

How GIN Works

GIN creates an entry for each element pointing to all rows containing it:

Traditional index (B-tree):
Row 1 → [tag1, tag2, tag3]
Row 2 → [tag1, tag4]
Row 3 → [tag2, tag3]

GIN (inverted):
tag1 → [Row 1, Row 2]
tag2 → [Row 1, Row 3]
tag3 → [Row 1, Row 3]
tag4 → [Row 2]

GIN for Arrays

-- Table with array column
CREATE TABLE articles (
  id SERIAL PRIMARY KEY,
  title TEXT,
  tags TEXT[]
);

-- GIN index on array
CREATE INDEX idx_articles_tags ON articles USING gin(tags);

-- Query: Find articles with 'sql' tag
SELECT * FROM articles WHERE tags @> ARRAY['sql'];

-- Query: Find articles with ANY of these tags
SELECT * FROM articles WHERE tags && ARRAY['sql', 'postgres'];

GIN for Full-Text Search

-- Full-text search with GIN
CREATE INDEX idx_articles_fts ON articles
  USING gin(to_tsvector('english', title || ' ' || body));

-- Query
SELECT * FROM articles
WHERE to_tsvector('english', title || ' ' || body) @@ to_tsquery('database & indexing');

GIN for JSONB

-- Index JSONB column
CREATE INDEX idx_products_data ON products USING gin(metadata);

-- Query: Find products with specific attribute
SELECT * FROM products WHERE metadata @> '{"color": "red"}';

-- Query: Check if key exists
SELECT * FROM products WHERE metadata ? 'color';

GiST: Geometric and Range Data

GiST (Generalized Search Tree) handles data that doesn't fit neatly into a linear order.

Geometric Queries with PostGIS

-- Enable PostGIS extension
CREATE EXTENSION postgis;

-- Table with geographic point
CREATE TABLE stores (
  id SERIAL PRIMARY KEY,
  name TEXT,
  location GEOGRAPHY(POINT)
);

-- GiST index for spatial queries
CREATE INDEX idx_stores_location ON stores USING gist(location);

-- Find stores within 5km of a point
SELECT name, ST_Distance(location, ST_MakePoint(-122.4194, 37.7749)::geography) as distance
FROM stores
WHERE ST_DWithin(location, ST_MakePoint(-122.4194, 37.7749)::geography, 5000)
ORDER BY distance;

Range Types

-- Table with date range
CREATE TABLE reservations (
  id SERIAL PRIMARY KEY,
  room_id INT,
  during DATERANGE
);

-- GiST index for range queries
CREATE INDEX idx_reservations_during ON reservations USING gist(during);

-- Find overlapping reservations
SELECT * FROM reservations
WHERE during && daterange('2024-03-15', '2024-03-20');

-- Check for conflicts
SELECT * FROM reservations
WHERE room_id = 101
  AND during && daterange('2024-03-15', '2024-03-20');

Choosing the Right Index

Key Takeaways

Next up: Composite Indexes - How multi-column indexes work and why column order matters.