What Is Database Indexing?

A database index is a data structure that helps a database locate rows more efficiently without scanning an entire table.

Indexes significantly improve the performance of SELECT queries, especially for large tables containing millions of rows.

However, indexes also consume additional storage and slightly increase the cost of INSERT, UPDATE, and DELETE operations because they must be maintained whenever data changes.

Almost every relational database, including PostgreSQL, MySQL, Oracle, and SQL Server, uses indexes extensively to optimize query execution.

Why Do We Need Indexes?

Suppose a customers table contains one million rows.

SELECT * FROM customers WHERE email = 'john@example.com';

Without an index, the database examines every row until it finds the matching customer.

Customer 1 Customer 2 Customer 3 ... Customer 1,000,000

This operation is known as a Full Table Scan. Now suppose an index exists on the email column.

CREATE INDEX idx_customer_email ON customers(email);

The database's query optimizer automatically decides whether using the index is more efficient than performing a full table scan.

           Index
             |
     +-------+-------+-------+
     |       |       |
     |  alice@example.com
     |  john@example.com
     |  peter@example.com
     v
   Row Location

The database reads only a small portion of the table, significantly reducing query execution time.

How an Index Works?

Most relational databases implement indexes using a B-Tree data structure.

A B-Tree stores indexed values in sorted order, allowing the database to quickly navigate to the desired value instead of scanning every row in the table.

Rather than comparing every row sequentially, the database repeatedly eliminates large portions of the search space by comparing the search value with nodes in the tree until it reaches the matching entry.

            [M]
           /   \
         [F]   [T]
        /   \  /   \
     A-D  G-L N-S U-Z

For example, when searching for "John", the database first compares it with the root node (M). Since John comes before M, it follows the left branch.

It then compares the value with the next node (F) and continues traversing the tree until it reaches the correct range containing John.

Because each comparison eliminates a large portion of the remaining values, only a few levels of the tree need to be traversed, even for tables containing millions of rows.

This makes index lookups significantly faster than a full table scan.

Clustered and Non-Clustered Indexes

Indexes are commonly categorized as Clustered and Non-Clustered.

Clustered Index

A clustered index determines the physical order in which rows are stored on disk. Since data can be physically stored in only one order, a table can have only one clustered index.

Clustered Index 1 2 3 4 5 6 7

Rows are physically organized according to the indexed column. Some database systems, such as SQL Server, use clustered indexes by default for primary keys.

Others, such as PostgreSQL, store table data separately from indexes while still supporting physical clustering through the CLUSTER command.

Non-Clustered Index

A non-clustered index stores indexed values separately from the table along with pointers to the corresponding rows.

         Email Index

alice@example.com ---> Row 25
john@example.com  ---> Row 302
peter@example.com ---> Row 821

A table can have multiple non-clustered indexes because they do not determine the physical storage order.

Primary Index and Secondary Index

Indexes are also classified based on the columns they are built on. A Primary Index is created on the primary key, ensuring that every row can be uniquely identified and retrieved efficiently.

A Secondary Index is created on one or more non-primary-key columns to improve the performance of frequently executed queries.

For example, consider a customers table where users are often searched by city.

CREATE INDEX idx_customer_city
ON customers(city);

Instead of scanning every row in the table, the database uses the secondary index to quickly locate all customers belonging to the requested city. This significantly improves the performance of queries such as:

SELECT *
FROM customers
WHERE city = 'London';

Primary indexes are typically created automatically when a primary key is defined, whereas secondary indexes must be created explicitly based on application query patterns.

Composite Index

A Composite Index contains multiple columns.

CREATE INDEX idx_customer_city_status ON customers(city, status);

This index is useful for queries such as:

SELECT * FROM customers WHERE city='Delhi' AND status='ACTIVE';

The order of columns in a composite index is important.

An index on (city, status) efficiently supports queries filtering by city or by city and status, but it generally does not help queries filtering only by status.

Unique Index

A Unique Index enforces uniqueness by preventing duplicate values.
CREATE UNIQUE INDEX idx_email ON customers(email); 
Attempting to insert another customer with the same email results in an error. Unique indexes are commonly used for email addresses, usernames, employee IDs, and other business identifiers.

Impact on Write Operations

Although indexes significantly improve read performance, they also increase the cost of insert, update, and delete operations.

Whenever a row is modified, the database must not only update the table itself but also update every index that references the affected columns.

As the number of indexes increases, the amount of work required for each write operation also increases.

        Insert Row
            |
     +------+------+------+------+
     |      |      |      |
     v      v      v      v
Update  Update  Update  Update
 Table  Index 1 Index 2 Index 3

For example, if a table has one primary index and three secondary indexes, inserting a single row requires updating the table as well as all four indexes.

Similarly, updating an indexed column requires the corresponding index entries to be modified, while deleting a row removes its entries from every affected index.

For this reason, indexes should be created only for columns that are frequently used in WHERE, JOIN, ORDER BY, or GROUP BY clauses.

When Are Indexes Used?

Database indexes are most effective for queries that search, sort, or join large amounts of data. WHERE JOIN ORDER BY GROUP BY
Indexes provide little benefit for small tables or queries that retrieve a large percentage of rows because a full table scan may be more efficient.

Indexes in NoSQL Databases

Indexes are not limited to relational databases. Most NoSQL databases also use indexes to locate data efficiently without scanning every document or record.

The implementation varies depending on the database model. For example, MongoDB primarily uses B-Tree indexes for document lookups.

db.customers.createIndex(
    { email: 1 }
);

db.customers.find({
    email: "john@example.com"
});

Instead of scanning every document in the collection, MongoDB uses the index to quickly locate the matching document.

Cassandra organizes data primarily using partition keys and clustering columns. Secondary indexes are available but are generally intended for specific query patterns rather than general-purpose lookups.

CREATE TABLE customers (
    customer_id UUID,
    city TEXT,
    name TEXT,
    PRIMARY KEY (city, customer_id)
);

In this example, rows are partitioned by city and ordered by customer_id, allowing Cassandra to efficiently retrieve all customers belonging to a particular city.

Elasticsearch uses an Inverted Index, which maps terms to the documents containing them instead of mapping keys to rows.

{
  "title": "Spring Boot Microservices"
}

When this document is indexed, Elasticsearch stores entries similar to:

spring  ---> Document 1
boot    ---> Document 1
microservices ---> Document 1

Searching for the term "Spring" immediately identifies the matching documents without scanning every document in the index, making inverted indexes highly efficient for full-text search.

Although these databases use different indexing techniques, they all share the same objective: to reduce the amount of data that must be scanned and improve query performance.

Summary

A database index is a specialized data structure that enables the database to locate rows quickly without scanning entire tables.

Indexes such as Primary, Composite and Unique optimize different query patterns, while the query optimizer automatically determines whether using an index is beneficial.

Although indexes greatly improve read performance, they introduce additional storage and write overhead.