Database Indexing

Database indexes reduce query cost by providing an auxiliary data structure that helps the database locate matching rows without examining every row. They can greatly improve reads, but they add storage overhead and make writes more expensive.

An index is a data structure maintained by the database for one or more table columns. Instead of checking every row to find matching values, the database can use the index to narrow the rows it needs to inspect. A common implementation is a B-tree or B+ tree, although database systems can support other index structures.

For example, an index on `users.email` can make a query such as `SELECT * FROM users WHERE email = ?` much faster when the table is large. The database can traverse the index to find the relevant key and then locate the corresponding table row. Without a suitable index, it may need a full table scan.

Indexes are not automatically useful for every query. The optimizer considers factors such as available indexes, estimated selectivity, table size, and query predicates before choosing an execution plan. An index may be ignored when a scan is estimated to be cheaper, such as when a condition matches a large fraction of the table.

Indexes also have a cost. Each index consumes disk and memory resources, and inserting, updating, or deleting indexed data usually requires corresponding index maintenance. Composite indexes can support queries involving multiple columns, but the column order matters because many B-tree indexes are most effective when predicates use the index's leading columns.

In Java backend applications, indexes are normally created and managed at the database/schema level rather than implemented in Java collections. Developers should examine actual query patterns and execution plans instead of adding indexes indiscriminately.

Key points

• Indexes provide a separate lookup structure that can avoid full table scans.
• B-tree-style indexes are commonly used for equality, range, and ordered lookups.
• Indexes improve many reads but add storage and write-maintenance costs.
• Composite-index column order affects which query predicates can efficiently use the index.
• The database optimizer may choose a table scan even when an index exists.

Interview questions

What is a database index, and why does it improve query performance?

A database index is an auxiliary data structure associated with one or more table columns. It lets the database find candidate rows without inspecting every row in the table. For example, an index on `email` can make an equality lookup much cheaper on a large table. The trade-off is additional storage and work to maintain the index when data changes.

What are the disadvantages of adding too many indexes?

Indexes consume disk space and may consume memory through database caching. Every insert, delete, or update affecting indexed columns can require index maintenance. A large number of indexes can therefore increase write latency and operational cost. Indexes should be based on actual access patterns rather than added indiscriminately.

What is a composite index, and why does column order matter?

A composite index contains multiple columns in a defined order, such as `(last_name, first_name)`. The database can often use it efficiently for predicates involving the leading column and, depending on the query and database, combinations that follow that ordering. A query filtering only on the second column may not receive the same benefit as one filtering on the first column. Therefore, index column order should reflect important query patterns.

Why might a database ignore an index that exists?

The query optimizer chooses an execution plan based on estimated cost. If a predicate matches a large portion of the table, scanning the table can sometimes be cheaper than performing many index lookups followed by row access. Statistics, data distribution, query expressions, and available indexes can also affect the decision. The correct way to investigate is to inspect the query's execution plan rather than assuming the index should be used.

How would you investigate a slow query and decide whether an index is needed?

I would first identify the actual slow query and inspect its execution plan. I would check whether it performs a full scan, how many rows are estimated or actually processed, and which predicates and joins dominate the work. Then I would compare the query pattern with existing indexes and consider a targeted index, including the order of columns for a composite index. After testing the change, I would verify both read performance and the impact on write workload and storage.