Database Indexing: B-Trees, Hash Indexes, and Making Queries Fast

The Story of a Slow Dashboard

A single database index can turn a 12-second page load into 15 milliseconds. A startup once shipped an admin dashboard that showed recent orders.On day one with 100 orders, it loads instantly. Six months later with 2 million orders, the page takes 12 seconds. The team assumes they need a bigger server. The actual fix? One line of SQL: CREATE INDEX. The page loads in 15ms. Understanding indexes is the difference between panic and a one-line fix.

What an Index Actually Is

Without an index, finding one row among millions requires scanning every single row (a 'full table scan' or 'Seq Scan' in PostgreSQL). An index is a separate sorted data structure that maps column values to row locations.

Without index - Full Table Scan:

  Query: WHERE email = 'alice@example.com'

  Table (10 million rows):
  +----+------------------+-------+
  | id | email            | name  |  <-- check row 1... no
  | id | email            | name  |  <-- check row 2... no
  | id | email            | name  |  <-- check row 3... no
  |    ... 9,999,997 more rows ...  |  <-- check EVERY row
  +----+------------------+-------+
  Time: ~3 seconds (reads every 8KB page from disk)


With B-Tree index on email:

  Index (sorted tree):         Table:
       [M...]
      /      \
   [A-L]    [N-Z]              Jump directly to
   /    \                      the matching row
  [A-F] [G-L]                  
   |                           
  alice@example.com --> Row #4,729,103

  Time: ~0.1ms (reads 3-4 tree nodes = 4 disk pages)

B-Tree Indexes: The Default Workhorse

B-Trees are the default index type in PostgreSQL, MySQL, SQLite, and virtually every relational database. They keep data sorted in a balanced tree structure where each internal node has ~100-500 children (not just 2 like a binary tree).

-- Create an index
CREATE INDEX idx_users_email ON users(email);

-- Now compare query plans:
EXPLAIN ANALYZE SELECT * FROM users WHERE email = 'alice@example.com';

-- WITHOUT index:
--   Seq Scan on users  (cost=0.00..185432.00 rows=1)
--     Filter: (email = 'alice@example.com')
--   Actual time: 3241.532ms   <-- 3.2 seconds!
--   Rows scanned: 10,000,000

-- WITH index:
--   Index Scan using idx_users_email on users  (cost=0.43..8.45 rows=1)
--     Index Condition: (email = 'alice@example.com')
--   Actual time: 0.052ms      <-- 0.05 milliseconds!
--   Rows scanned: 1

What B-Trees Handle

• Equality lookups: WHERE email = 'alice@example.com'

• Range queries: WHERE created_at > '2024-01-01' AND created_at < '2024-07-01'

• Sorting: ORDER BY price ASC (index is already sorted)

• Prefix searches: WHERE name LIKE 'Joh%' (but NOT '%ohn' - cannot use index for suffix)

• MIN/MAX: SELECT MAX(price) FROM products (just read the last leaf node)

Hash Indexes: O(1) Equality Only

A hash index uses a hash function to map keys directly to their location. Lookups are O(1) instead of O(log n), but they ONLY support equality. No ranges, no sorting, no prefix matching.

In practice, B-Trees are almost always preferred because they handle both equality AND ranges with only slightly more overhead. Redis uses hash tables internally because its access pattern is purely key-value lookups.

Composite Indexes: Column Order Matters

A composite index covers multiple columns. The column order determines which queries can use it:

CREATE INDEX idx_location ON addresses(country, city, zip_code);

-- This index works for:
-- WHERE country = 'US'                          (uses index)
-- WHERE country = 'US' AND city = 'Seattle'     (uses index)
-- WHERE country = 'US' AND city = 'Seattle'     (uses index)
--   AND zip_code = '98101'

-- This index does NOT work for:
-- WHERE city = 'Seattle'                (skips first column!)
-- WHERE zip_code = '98101'              (skips first two columns!)

-- Think of it like a phone book sorted by:
-- Last Name -> First Name -> Middle Name
-- You can look up by last name alone,
-- but you cannot look up by first name alone.

-- Rule: INDEX(a, b, c) supports queries on:
--   (a), (a,b), (a,b,c)  -- NOT (b), (c), or (b,c)

The Cost of Indexes

Indexes are not free. Every index you create has a price:

Cost of each index:

  Disk space:   An index on a 10GB table might be 2-4GB
  Write speed:  Each INSERT updates the table AND every index
                5 indexes = 6 writes per INSERT
  Memory:       Hot indexes are cached in RAM (shared_buffers)
                More indexes = more RAM pressure

Real example:
  Table:    users (10M rows, 5GB data)
  Index 1:  idx_email    (800MB)
  Index 2:  idx_created  (600MB)
  Index 3:  idx_status   (400MB)
  Index 4:  idx_name     (700MB)
  Total indexes: 2.5GB > half the table size!

  INSERT without indexes: ~0.1ms
  INSERT with 4 indexes:  ~0.5ms  (5x slower writes)

Specialized Index Types

Index Type       Database        Best For
--------------   -------------   ---------------------------------
B-Tree           All             General purpose (default)
Hash             PostgreSQL      Equality-only, slightly faster
GIN              PostgreSQL      Full-text search, JSONB, arrays
GIST             PostgreSQL      Geospatial, range types
BRIN             PostgreSQL      Very large tables with natural
                                 ordering (timestamps, IDs)
Full-text        MySQL           Text search (MATCH AGAINST)
Covering index   All             Include extra columns to avoid
                                 table lookup (INDEX...INCLUDE)

Practical Index Strategy

1. Start with no indexes except primary keys and foreign keys

2. Monitor slow queries (pg_stat_statements in PostgreSQL, slow query log in MySQL)

3. Run EXPLAIN ANALYZE on slow queries - look for Seq Scan on large tables

4. Add targeted indexes on columns in WHERE, JOIN, and ORDER BY clauses

5. Verify the index is used by running EXPLAIN ANALYZE again

6. Periodically review unused indexes (pg_stat_user_indexes) and drop them.

Quick Revision

Here is index catalog that gives a good understanding of all the topics and concepts that is important to know to have a good understanding on current blog.

Interview Tip

When discussing database performance in interviews, always mention EXPLAIN ANALYZE. Say: 'Before adding any index, I would run EXPLAIN ANALYZE to see the current query plan and confirm there is a Seq Scan on a large table. After adding the index, I would run it again to verify the planner switched to an Index Scan. I would also check pg_stat_user_indexes periodically to drop unused indexes that are slowing down writes for no benefit.'

Key Takeaway

Indexes trade write speed and storage for dramatically faster reads. B-Trees handle equality, ranges, and sorting - use them by default. Index the columns you query on, use composite indexes in the right column order, and always verify with EXPLAIN ANALYZE.