Database Indexing in System Design: How Indexes Speed Up Queries

A database index is an extra data structure that helps the database find rows quickly without reading the entire table. A good index can turn a query that takes seconds into one that takes a millisecond. A missing index is one of the most common reasons applications slow down as their data grows.

This tutorial explains what an index is, how a B-tree index finds data, the main types of indexes, clustered versus non-clustered indexes, composite indexes and the leftmost prefix rule, how to read an execution plan, what indexes cost, and how to define them in Spring Boot with JPA. It finishes with common mistakes and best practices.

1. What Is a Database Index?

Think of a thick cookbook. To find the recipe for "paneer tikka", you could flip through every page from the start. Or you could open the alphabetical index at the back, find "Paneer tikka … page 214", and jump straight there. The index takes a few extra pages, but it saves enormous time.

A database index works the same way. It stores the values of one or more columns in a sorted, searchable structure, and each entry points to the location of the full row in the table. When you search on an indexed column, the database looks up the value in the index and goes directly to the matching rows.

• Index key: the column or columns the index is built on, such as email.
• Pointer: how the index finds the row, such as a physical row address or the row's primary key.
• Maintenance: the database updates the index automatically on every insert, update and delete. You never edit it by hand.

2. What Happens Without an Index

Suppose a customers table has ten million rows and you run:

SELECT * FROM customers WHERE email = 'neha@mail.com';

Without an index on email, the database has no idea where Neha's row is. It must perform a full table scan: read every row, compare the email, and keep the matches. The work grows in direct proportion to the table size, which computer scientists write as O(n). With an index, the lookup takes roughly O(log n) steps, which for ten million rows is only a couple of dozen comparisons.

On a tiny table the difference is invisible. On a table with millions of rows, or a query that runs thousands of times per second, it decides whether your system is fast or falls over.

3. How an Index Works: The B-Tree

Most relational databases use a B-tree (more precisely a B+ tree) as their default index structure. It is a balanced tree designed for disks and memory pages:

• Root and internal nodes hold keys that act as signposts, such as "values below 30 go left".
• Leaf nodes hold every indexed value in sorted order, each with a pointer to its row.
• Leaves are linked to their neighbours, so range scans like BETWEEN 30 AND 60 can walk sideways without going back to the root.
• The tree stays balanced: every leaf is at the same depth, so every lookup costs about the same.

Real B-tree nodes hold hundreds of keys each, so the tree is very wide and shallow. A table with hundreds of millions of rows usually needs a tree only three or four levels deep, which means a lookup touches just three or four pages. Those upper levels are almost always cached in memory, making lookups extremely fast.

B-trees support equality (=), ranges (<, >, BETWEEN), sorting (ORDER BY) and prefix searches (LIKE 'abc%'). They cannot help with a search like LIKE '%abc', because the start of the value is unknown.

4. Types of Indexes

5. Clustered vs Non-Clustered Indexes

This distinction describes where the actual row data lives.

• A clustered index stores the table rows themselves in the order of the index key. The leaf level of the index is the table. Because rows can only be physically ordered one way, a table has at most one clustered index. In MySQL InnoDB and SQL Server, the primary key is the clustered index by default.
• A non-clustered (secondary) index is a separate structure. Its leaves hold the indexed value plus a pointer to the row. In InnoDB, that pointer is the primary key value, so a secondary lookup is followed by a second lookup in the clustered index.

PostgreSQL works a little differently: it stores rows in an unordered heap, and every index, including the primary key, is a secondary index that points to a row's physical location.

A practical consequence for InnoDB: keep primary keys short (such as a BIGINT), because every secondary index stores a copy of the primary key in each entry.

6. Composite Indexes and the Leftmost Prefix Rule

A composite index covers several columns in a specific order. Think of a phone book sorted by last name, then first name. It is great for finding "Sharma, Priya" or every "Sharma", but useless for finding everyone named "Priya", because Priyas are scattered across all last names.

Databases follow the same leftmost prefix rule. Given this index:

CREATE INDEX idx_orders_customer_created ON orders (customer_id, created_at);

A good rule of thumb for column order: put columns compared with equality first, and the column used for a range or sort last. Some databases can occasionally use a composite index without its first column (a "skip scan"), but you should not design around it.

7. Creating and Managing Indexes in SQL

The syntax below is PostgreSQL, but MySQL and other databases are very similar:

-- Simple index on one column
CREATE INDEX idx_customers_email ON customers (email);

-- Unique index: also enforces "no two customers share an email"
CREATE UNIQUE INDEX uq_customers_email ON customers (email);

-- Expression index for case-insensitive lookups
CREATE INDEX idx_customers_email_lower ON customers (LOWER(email));

-- Partial index: only the rows most queries care about
CREATE INDEX idx_orders_pending ON orders (created_at) WHERE status = 'PENDING';

-- Covering index (PostgreSQL 11+): extra columns stored in the leaf
CREATE INDEX idx_orders_customer_cover ON orders (customer_id) INCLUDE (total_amount, status);

-- Build on a busy production table without blocking writes (PostgreSQL)
CREATE INDEX CONCURRENTLY idx_orders_created ON orders (created_at);

-- Remove an index that is no longer useful
DROP INDEX idx_customers_email_lower;

8. Reading an Execution Plan with EXPLAIN

Never guess whether a query uses an index. Ask the database with EXPLAIN, or EXPLAIN ANALYZE to actually run the query and measure it. Here is what PostgreSQL might show before and after adding an index on email (your exact numbers will differ):

EXPLAIN ANALYZE SELECT * FROM customers WHERE email = 'neha@mail.com';

Seq Scan on customers  (cost=0.00..208334.00 rows=1 width=96) (actual time=412.118..823.406 rows=1 loops=1)
  Filter: ((email)::text = 'neha@mail.com'::text)
  Rows Removed by Filter: 9999999
Execution Time: 823.441 ms

Index Scan using idx_customers_email on customers  (cost=0.43..8.45 rows=1 width=96) (actual time=0.031..0.032 rows=1 loops=1)
  Index Cond: ((email)::text = 'neha@mail.com'::text)
Execution Time: 0.054 ms

Key things to look for:

• Seq Scan (PostgreSQL) or type: ALL (MySQL) means a full table scan.
• Index Scan or Index Only Scan means an index is used; "Index Only" means the table itself was not even touched.
• Rows Removed by Filter shows wasted work: rows read and then thrown away.
• Estimated vs actual rows: big differences mean the planner's statistics are outdated. Running ANALYZE refreshes them.

Also remember that the planner may deliberately ignore an index. If a query matches a large share of the table, reading the table sequentially is cheaper than jumping between index and table thousands of times.

9. The Cost of Indexes

Indexes are not free. Each one is a trade-off:

• Slower writes: every INSERT, DELETE and every UPDATE of an indexed column must also update each affected index. A table with ten indexes does roughly ten extra pieces of work per insert.
• More storage: indexes take disk space and, more importantly, memory in the buffer cache. Large unused indexes push useful data out of memory.
• Maintenance: indexes can become bloated or fragmented over time and occasionally need rebuilding.
• Planner complexity: too many similar indexes make it harder for the optimiser to choose well.

For read-heavy tables, such as a product catalogue, more indexes are usually worth it. For write-heavy tables, such as event logs or metrics, keep indexes to the minimum your queries truly need.

10. When to Add an Index (and When Not To)

Selectivity is the key idea: an index helps most when a condition narrows millions of rows down to a few. An index on gender rarely helps alone, but it can still be useful as part of a composite or partial index.

11. Defining Indexes in Spring Boot with JPA

With JPA, you can declare indexes on the entity so they are created when Hibernate generates the schema:

package com.javabytechie.indexing;

import java.time.Instant;

import jakarta.persistence.Column;
import jakarta.persistence.Entity;
import jakarta.persistence.GeneratedValue;
import jakarta.persistence.GenerationType;
import jakarta.persistence.Id;
import jakarta.persistence.Index;
import jakarta.persistence.Table;

@Entity
@Table(name = "customers", indexes = {
        @Index(name = "uq_customers_email", columnList = "email", unique = true),
        @Index(name = "idx_customers_city_created", columnList = "city, created_at")
})
public class Customer {

    @Id
    @GeneratedValue(strategy = GenerationType.IDENTITY)
    private Long id;

    @Column(nullable = false, length = 120)
    private String email;

    @Column(length = 60)
    private String city;

    @Column(name = "created_at", nullable = false)
    private Instant createdAt;

    protected Customer() { }

    public Customer(String email, String city, Instant createdAt) {
        this.email = email;
        this.city = city;
        this.createdAt = createdAt;
    }

    // getters omitted for brevity
}

package com.javabytechie.indexing;

import java.time.Instant;
import java.util.List;
import java.util.Optional;

import org.springframework.data.jpa.repository.JpaRepository;

public interface CustomerRepository extends JpaRepository<Customer, Long> {

    // Served by uq_customers_email
    Optional<Customer> findByEmail(String email);

    // Served by idx_customers_city_created: equality on city, range and sort on created_at
    List<Customer> findByCityAndCreatedAtAfterOrderByCreatedAtDesc(String city, Instant after);
}

The @Index annotation only matters when Hibernate creates the schema, which is common in development but not recommended in production. In production, manage indexes with versioned migrations using Flyway or Liquibase, so every environment gets exactly the same, reviewed changes:

CREATE UNIQUE INDEX uq_customers_email ON customers (email);
CREATE INDEX idx_customers_city_created ON customers (city, created_at);

To check what SQL your repository methods generate, temporarily set spring.jpa.show-sql=true, copy the query, and run it with EXPLAIN in your database.

12. Seeing the Difference in Java

This small program imitates what a database does. It searches one million records first by scanning every one, then through a sorted tree structure (TreeMap, a balanced red-black tree, playing the role of the index):

package com.javabytechie.indexing;

import java.util.ArrayList;
import java.util.Collections;
import java.util.List;
import java.util.Random;
import java.util.TreeMap;

public class IndexDemo {

    record Customer(int id, String email) { }

    public static void main(String[] args) {
        int rows = 1_000_000;
        List<Customer> table = new ArrayList<>(rows);
        for (int i = 1; i <= rows; i++) {
            table.add(new Customer(i, "user" + i + "@mail.com"));
        }
        Collections.shuffle(table, new Random(7));          // like a heap table: no useful order

        String target = "user765432@mail.com";

        // 1. Full table scan: compare every row
        long start = System.nanoTime();
        int checked = 0;
        Customer found = null;
        for (Customer c : table) {
            checked++;
            if (c.email().equals(target)) {
                found = c;
            }
        }
        long scanMicros = (System.nanoTime() - start) / 1_000;
        System.out.printf("Full scan : checked %,d rows, found id %d in %,d µs%n", checked, found.id(), scanMicros);

        // 2. Build an "index": email -> row, kept sorted in a balanced tree
        TreeMap<String, Customer> emailIndex = new TreeMap<>();
        for (Customer c : table) {
            emailIndex.put(c.email(), c);
        }

        start = System.nanoTime();
        Customer viaIndex = emailIndex.get(target);
        long indexMicros = (System.nanoTime() - start) / 1_000;
        int steps = (int) Math.ceil(Math.log(rows) / Math.log(2));
        System.out.printf("Index     : about %d comparisons, found id %d in %,d µs%n", steps, viaIndex.id(), indexMicros);
    }
}

Full scan : checked 1,000,000 rows, found id 765432 in 20,007 µs
Index     : about 20 comparisons, found id 765432 in 24 µs

The scan compares one million emails; the tree needs about twenty comparisons, because each step halves the remaining search space. Building the index took extra time and memory, which mirrors the write and storage cost of real indexes.

13. Indexes in NoSQL and Distributed Databases

• MongoDB: uses B-tree indexes much like relational databases, created with db.customers.createIndex({ email: 1 }, { unique: true }), including compound, text, geospatial and TTL indexes.
• Cassandra: data is organised by partition key, and queries are expected to include it. Secondary indexes exist but can be expensive across a large cluster, so teams often create extra tables designed for each query instead.
• DynamoDB: offers Global Secondary Indexes (a different partition key, updated asynchronously) and Local Secondary Indexes (same partition key, different sort key).
• Elasticsearch and OpenSearch: built on inverted indexes, which map each word to the documents containing it, ideal for full-text search.
• LSM-tree storage engines (used by Cassandra, RocksDB and others) are optimised for very fast writes. They buffer writes in memory and merge sorted files on disk in the background, trading some read cost for write speed.

In a sharded system, a local index covers only the data on one shard, so a query on that index may need to ask every shard. A global index is partitioned by the indexed value itself, so lookups are fast, but writes must update an index entry that may live on a different shard.

14. Common Mistakes to Avoid

• Indexing every column "just in case". This slows writes and wastes memory without helping real queries.
• Wrapping indexed columns in functions. WHERE LOWER(email) = ? or WHERE YEAR(created_at) = 2026 cannot use a plain index on that column. Use an expression index or rewrite as a range.
• Wrong column order in composite indexes. An index on (created_at, customer_id) does little for WHERE customer_id = ?.
• Leading wildcards. LIKE '%phone' forces a scan. Use full-text search for this kind of query.
• Type mismatches. Comparing a VARCHAR column with a number can cause an implicit conversion that disables the index.
• Forgetting foreign key indexes. Joins and cascading deletes on unindexed foreign keys can be painfully slow.
• Duplicate indexes. An index on (a) is usually redundant when an index on (a, b) already exists.

15. Best Practices

• Design indexes from your actual queries: list the most frequent and slowest ones, then index for them.
• Verify every new index with EXPLAIN ANALYZE on realistic data volumes.
• Prefer one well-designed composite index over several single-column indexes for common multi-column filters.
• Use covering indexes for very hot queries so the table does not need to be read.
• Monitor index usage, and drop indexes that are never used (PostgreSQL's pg_stat_user_indexes view shows this).
• Keep table statistics fresh so the optimiser makes good decisions.
• Create indexes on large live tables without blocking writes, using options such as CREATE INDEX CONCURRENTLY or online DDL.
• Manage indexes through versioned migrations, never by hand in production.

16. Summary

• A database index is a sorted structure that lets the database find rows without scanning the whole table.
• Most indexes are B+ trees: shallow, balanced trees that make lookups take O(log n) steps and support ranges and sorting.
• A clustered index stores the rows themselves in key order; secondary indexes point to the rows.
• Composite indexes follow the leftmost prefix rule, so column order matters.
• Indexes speed up reads but slow down writes and use storage, so add them based on real queries and verify them with EXPLAIN.

Good indexing is one of the cheapest and most effective performance improvements in any system. Open the FAQ tab for answers to common questions about database indexing.

Frequently Asked Questions (FAQ)