Indexing

B-Tree is the most common index type in relational databases.

B-Tree Structure

                    [50]
                   /    \
              [20,30]    [60,80]
             /  |  \\    /  |  \
           [10] [25] [40] [55] [70] [90]

- Balanced tree
- All leaves at same depth
- Sorted data
- O(log n) lookups

How B-Tree Index Works

Table: users (1 million rows)
Index: idx_users_email ON users(email)

Query: SELECT * FROM users WHERE email = 'alice@example.com'

Without Index:
- Full table scan: 1 million rows checked
- Time: 500ms

With B-Tree Index:
- Index lookup: log2(1M) ≈ 20 comparisons
- Time: 0.5ms

1000x improvement!

B-Tree Operations

Search: O(log n)
- Navigate tree from root to leaf
- Find matching entries

Insert: O(log n)
- Find correct leaf position
- Insert new entry
- Split leaf if full

Delete: O(log n)
- Find entry
- Remove from leaf
- Merge if needed

Creating B-Tree Index

-- Single column
CREATE INDEX idx_users_email ON users(email);

-- Multiple columns (composite)
CREATE INDEX idx_users_name_email ON users(name, email);

-- Partial index
CREATE INDEX idx_active_users ON users(email) WHERE active = true;

-- Unique index
CREATE UNIQUE INDEX idx_users_email_unique ON users(email);

B-Tree Best Practices

1. Index columns used in WHERE: Speed up filters
2. Index columns used in JOINs: Speed up joins
3. Index columns used in ORDER BY: Speed up sorting
4. Don't over-index: Each index slows writes
5. Monitor index usage: Remove unused indexes

Hash indexes use hash tables for exact-match lookups.

Hash Index Structure

Hash Function: hash(email) → bucket

Bucket 0: [alice@a.com → Row 1]
Bucket 1: [bob@b.com → Row 2]
Bucket 2: [charlie@c.com → Row 3]

O(1) lookup for exact match

Hash vs B-Tree

Aspect	Hash	B-Tree
Lookup	O(1) exact match	O(log n) range
Range queries	Not supported	Supported
Ordering	Not maintained	Sorted
Partial match	Not supported	Supported
Memory	Lower	Higher

When to Use Hash Index

Use Hash Index when:
- Only exact-match queries (=)
- No range queries needed
- No ordering required
- High read throughput needed

Examples:
- Session lookup by ID
- User lookup by email
- Cache key lookup

Don't use Hash Index when:
- Range queries (>, <, BETWEEN)
- ORDER BY needed
- Prefix matching (LIKE 'abc%')

Hash Index in Practice

-- PostgreSQL Hash Index
CREATE INDEX idx_users_email_hash ON users USING hash(email);

-- Query using hash index
SELECT * FROM users WHERE email = 'alice@example.com';  -- Uses hash index
SELECT * FROM users WHERE email > 'a';  -- Does NOT use hash index

Hash Index Limitations

1. No range queries
   WHERE id > 100  -- Can't use hash index

2. No ORDER BY
   ORDER BY email  -- Can't use hash index

3. No partial matching
   WHERE email LIKE '%@example.com'  -- Can't use hash index

4. Hash collisions
   Multiple keys → same bucket
   Resolution: chaining or open addressing

Composite indexes include multiple columns in a single index.

Composite Index Structure

Index on (name, email, age):

Sorted by:
1. name (primary)
2. email (secondary)
3. age (tertiary)

Alice, a@b.com, 25
Alice, c@d.com, 30
Bob,   b@c.com, 28
Charlie, e@f.com, 22

Leftmost Prefix Rule

Index: (name, email, age)

Can use index:
✓ WHERE name = 'Alice'
✓ WHERE name = 'Alice' AND email = 'a@b.com'
✓ WHERE name = 'Alice' AND email = 'a@b.com' AND age = 25

Cannot use index:
✗ WHERE email = 'a@b.com'  (skipped name)
✗ WHERE age = 25  (skipped name, email)

Composite Index Examples

-- Index for common query
CREATE INDEX idx_orders_user_date ON orders(user_id, created_at);

-- Query uses index
SELECT * FROM orders
WHERE user_id = 123
ORDER BY created_at DESC;

-- Index for search
CREATE INDEX idx_products_category_price ON products(category, price);

-- Query uses index
SELECT * FROM products
WHERE category = 'electronics'
ORDER BY price;

Composite Index Best Practices

1. Column Order Matters
   - Most selective column first
   - Most frequently queried column first

2. Covering Index
   - Include all columns needed by query
   - Avoids table lookup

Example:
CREATE INDEX idx_covering ON users(name, email, age);
SELECT name, email, age FROM users WHERE name = 'Alice';
-- Index covers query, no table access needed

3. Index Size
   - More columns = larger index
   - Balance between coverage and size

Selectivity measures how many distinct values an index has.

Selectivity Formula

Selectivity = Number of Distinct Values / Total Rows

Example:
- email: 1M distinct values / 1M rows = 1.0 (highly selective)
- gender: 2 distinct values / 1M rows = 0.000002 (low selectivity)
- age: 100 distinct values / 1M rows = 0.0001

Selectivity Impact

High Selectivity (email):
- Many distinct values
- Index very effective
- Each lookup returns few rows

Low Selectivity (gender):
- Few distinct values
- Index less effective
- Each lookup returns many rows
- Full scan might be faster

Selectivity and Index Choice

Selectivity	Index Type	Example
High (>0.1)	B-Tree	email, user_id
Medium (0.01-0.1)	B-Tree	age, status
Low (<0.01)	Consider skip	gender, boolean

Index Cardinality

Cardinality = Number of distinct values

High cardinality: email, UUID, timestamp
Medium cardinality: age, price
Low cardinality: boolean, status, gender

Index on low cardinality:
- May not be used by query planner
- Consider partial index instead

Partial Indexes

-- Index only active users
CREATE INDEX idx_active_email ON users(email) WHERE active = true;

-- Smaller, more selective index
-- Only indexes rows where active = true

-- Query must match WHERE clause
SELECT * FROM users WHERE active = true AND email = 'x';  -- Uses index
SELECT * FROM users WHERE active = false AND email = 'x';  -- Does NOT

Index Monitoring

-- PostgreSQL: Check index usage
SELECT schemaname, tablename, indexname, idx_scan, idx_tup_read
FROM pg_stat_user_indexes
ORDER BY idx_scan DESC;

-- Remove unused indexes
DROP INDEX idx_unused;

-- Check index size
SELECT indexname, pg_size_pretty(pg_relation_size(indexname::regclass))
FROM pg_indexes
WHERE tablename = 'users';

Index Best Practices

1. Index high-selectivity columns: Most effective
2. Monitor index usage: Remove unused indexes
3. Use composite indexes wisely: Follow leftmost prefix
4. Consider partial indexes: For filtered queries
5. Balance index count: Each index slows writes