Databases
Indexing Strategies
Indexing is the process of creating supplementary data structures to enable fast lookups without scanning entire tables. It matters because disk I/O is the primary bottleneck in database performance, and indices drastically reduce the number of pages read during query execution. You reach for indexing whenever read performance on specific columns becomes a limiting factor in your system's overall latency.
The Fundamental Problem of Full Table Scans
To understand indexing, one must first grasp the physical reality of how data resides on disk. When a database performs a full table scan, it must load every single page of a table into memory to check if the record matches the filter criteria. If a table has millions of rows, this process involves moving gigabytes of data from slow storage to the processor, which is catastrophically inefficient. An index functions like the index at the back of a textbook: instead of reading every page to find a topic, you look up the page number in the index. By maintaining a smaller, sorted secondary data structure that points to the physical location of the row on disk, we transform an O(N) operation into an O(log N) or even O(1) operation. This reduction in I/O operations is the singular reason indexing is the most effective tool for performance tuning in relational systems.
-- Typical slow table scan: must check every row
SELECT * FROM orders WHERE customer_id = 550;
-- The database reads the entire table storage to filter this request.Clustered Indexes: Organizing the Physical Data
A clustered index determines the physical order of data within the table. Since data can only be sorted in one way on a disk, a table can have only one clustered index. By default, most systems use the primary key for this. When you retrieve a record via a clustered index, the engine traverses a B-Tree structure directly to the leaf node where the actual row data is stored. This makes range scans incredibly fast, as the records are physically contiguous on the storage medium. When you design a schema, you should choose a clustered index key that is monotonically increasing, such as a timestamp or an auto-incrementing integer. If the clustered key is random, it forces the database to perform frequent page splits, where it must reorganize existing data to fit a new row into the middle of a disk block, leading to massive performance degradation and increased storage fragmentation.
-- Defining a clustered index on a primary key
CREATE TABLE accounts (
account_id INT PRIMARY KEY, -- Automatically creates a clustered index
username TEXT NOT NULL
); -- Records are physically sorted by account_id on disk.Secondary Indexes and the Cost of Lookups
Secondary indexes are structures that exist separately from the main table data. They contain a copy of the indexed column's value and a pointer back to the primary key or physical row ID. This allows for rapid searching on non-primary columns, such as email addresses or timestamps. However, secondary indexes come with a significant cost: the 'Double Lookup'. First, the database searches the secondary index tree to find the pointer. Then, it performs a second read to jump to the actual row in the clustered index to fetch the remaining columns. This is why you must balance the number of indexes. Every secondary index must be updated during every 'insert', 'update', or 'delete' operation. Excessive indexing bloats your database size and slows down write-heavy applications. Always index only what is necessary to satisfy your most frequent read queries to maintain optimal system health.
-- Creating a secondary index for fast lookups by email
CREATE INDEX idx_user_email ON users(email);
-- The database now maintains a separate tree structure for email lookups.Composite Indexes: Leveraging Order and Selectivity
Composite indexes involve indexing multiple columns together. The ordering within the index is critical. Databases utilize the 'Left-Prefix' rule: an index on (A, B) can satisfy queries filtering on A or on (A, B), but it cannot be used for queries filtering only on B. This happens because the B-Tree is sorted primarily by column A, and B is only sorted relative to A. Therefore, when designing composite indexes, you should place the column with the highest selectivity (the one that filters out the most rows) first. If you have a query that filters by 'status' and 'created_at', and status has only three values while created_at is unique for every row, putting 'status' first provides almost no benefit. By placing the most restrictive column first, you shrink the search space as quickly as possible, ensuring that the engine ignores the maximum amount of irrelevant data during the search.
-- A composite index on two columns
CREATE INDEX idx_order_status_date ON orders(status, created_at);
-- This index is useful for 'status = X' and 'status = X AND created_at = Y'.Covering Indexes and Eliminating Lookups
A covering index is a specialized design technique where every column requested in the 'SELECT' clause is included in the index itself. Because all the data is contained within the index structure, the database does not need to perform a second lookup to the main table storage. This is essentially a 'read-only' cache of the columns you access most frequently. When a query is 'covered' by an index, the database engine returns the result directly from the B-Tree leaves. This provides a massive performance boost, especially for read-heavy analytical queries. While this significantly increases write latency due to the extra data payload held in the index, the trade-off is often worth it for high-read-volume systems. When designing your queries, identify common request patterns and include all relevant columns in a composite index to achieve this coverage and minimize unnecessary disk access.
-- Covering index: includes all columns needed for the query
CREATE INDEX idx_cover_user ON users(email, last_login);
-- The SELECT query will be satisfied entirely by the index leaf nodes.
SELECT email, last_login FROM users WHERE email = 'test@example.com';Key points
- Indexes serve to reduce total disk I/O by enabling faster search paths than linear table scans.
- A table can only have one clustered index, which defines the physical order of the data on disk.
- Secondary indexes require a double lookup, first finding the pointer and then fetching the row data.
- B-Tree indexes follow the Left-Prefix rule, meaning index columns must be used in the order they are defined.
- High cardinality columns should generally be placed earlier in a composite index for better selectivity.
- Every additional index slows down write operations like inserts and updates due to maintenance overhead.
- Covering indexes allow for query execution without ever accessing the original table data blocks.
- Database engineers must carefully weigh read-speed gains against the storage and write costs of new indexes.
Common mistakes
- Mistake: Indexing every single column. Why it's wrong: It increases storage overhead and significantly slows down write operations because every index must be updated. Fix: Only index columns frequently used in WHERE, JOIN, or ORDER BY clauses.
- Mistake: Ignoring composite index ordering. Why it's wrong: Composite indexes follow the leftmost-prefix rule; if you search by a column that isn't the first in the index, the index is ignored. Fix: Place the most selective or frequently queried column at the leftmost position.
- Mistake: Overusing indexes on low-cardinality columns. Why it's wrong: Indexes on columns like 'gender' or 'boolean status' don't help the engine filter data effectively, wasting resources. Fix: Use indexes only on high-cardinality columns where the query result returns a small fraction of the total rows.
- Mistake: Neglecting the impact of updates on indexes. Why it's wrong: Frequent updates to indexed columns cause index fragmentation and locking contention, degrading system performance. Fix: Avoid indexing columns that change very frequently unless necessary for specific read-heavy query patterns.
- Mistake: Using functions on indexed columns in queries. Why it's wrong: Applying a function like YEAR(date) to an indexed column prevents the database from performing an index seek, forcing a full table scan. Fix: Query the raw value directly or use a generated functional index.
Interview questions
What is a database index, and why do we use them in system design?
A database index is a specialized data structure, typically a B-Tree or Hash table, that allows the database engine to locate records without performing a full table scan. In system design, we use indexes to significantly reduce the time complexity of read operations. Without an index, the system must inspect every row in a table to find a match, which is an O(n) operation. By using an index, we reduce this to O(log n), allowing the system to scale to millions of rows while maintaining sub-millisecond response times for common queries.
What is the difference between a Clustered Index and a Non-Clustered Index?
A clustered index determines the physical order of data in the table, meaning the leaf nodes of the index contain the actual row data. Because of this, a table can only have one clustered index. A non-clustered index, conversely, is a separate structure that stores the key values and pointers to the actual data rows. In system design, you choose a clustered index for columns frequently used in range queries, while non-clustered indexes are ideal for supporting specific lookup filters to minimize IO overhead during search operations.
When should you use a Composite Index, and what is the 'Leftmost Prefix' rule?
A composite index covers multiple columns, which is essential when a query filters on several fields simultaneously. The 'Leftmost Prefix' rule dictates that for an index defined on columns (A, B, C), the database can only use the index if the query includes the first column, A. If you query only by B or C, the index is ignored. This is a critical design constraint; we must order our columns in composite indexes from most selective to least selective to ensure the engine discards the largest number of irrelevant rows early in the scan.
Compare the use of B-Tree indexes versus Hash indexes in a high-scale system.
B-Tree indexes are the industry standard because they support equality lookups, range queries (e.g., 'BETWEEN' or '>'), and sorting operations. They maintain data in a balanced tree, ensuring predictable performance. Hash indexes are faster for point lookups—providing O(1) average time complexity—but they cannot perform range scans or partial key lookups because the hash function loses the natural ordering of keys. I would choose a B-Tree for general-purpose relational queries and a Hash index only for specific caching or key-value lookups where range queries are strictly unnecessary.
How does indexing impact write performance in a write-heavy system?
Every index adds overhead to write operations because each 'INSERT', 'UPDATE', or 'DELETE' statement requires the database to update both the data table and every associated index tree. This can lead to write amplification. In a system design scenario, if we have a table with ten indexes, a single row insertion could trigger eleven separate writes. To mitigate this, we must balance read optimization with write latency. If the system is write-heavy, we should limit the number of indexes, drop unused indexes, or move historical data to an unindexed archival store to maintain high ingestion throughput.
What is a Covering Index, and how can it improve system performance?
A covering index is an index that includes all the columns referenced in a query, allowing the database to return results directly from the index structure without ever accessing the underlying table heap. By avoiding the 'bookmark lookup' or 'RID lookup' back to the base table, we eliminate significant random IO. For example, if a query is `SELECT user_id, status FROM orders WHERE status = 'active'`, an index on `(status, user_id)` covers the query completely. This is a powerful optimization in system design for high-traffic read-heavy tables where minimizing IOPS is critical to reducing latency.
Check yourself
1. A table has a composite index on (last_name, first_name). Which query will effectively utilize this index?
- A.SELECT * FROM users WHERE first_name = 'John'
- B.SELECT * FROM users WHERE last_name = 'Doe'
- C.SELECT * FROM users WHERE email = 'test@example.com'
- D.SELECT * FROM users WHERE last_name = 'Doe' AND age = 25
Show answer
B. SELECT * FROM users WHERE last_name = 'Doe'
The index follows the leftmost-prefix rule. Option 2 works because it uses the leftmost column. Option 1 fails because it skips the leftmost column. Option 3 fails as the column is not in the index. Option 4 works, but Option 2 is the most direct application of the leftmost-prefix rule.
2. Why does adding too many indexes to a high-throughput write-heavy system lead to performance degradation?
- A.The indexes consume too much RAM during read operations.
- B.The database must lock the entire table whenever a row is read.
- C.Every write operation requires a corresponding update to each index structure.
- D.Indexes cause the query optimizer to choose a random execution plan.
Show answer
C. Every write operation requires a corresponding update to each index structure.
Every index is a separate data structure that must be updated synchronously when data is inserted, updated, or deleted. Option 1 is false because RAM is used for caching, not exclusively for indexes. Option 2 is incorrect as modern DBs use row-level locking. Option 4 is incorrect as optimizers are deterministic.
3. When is it optimal to use a covering index?
- A.When the query needs to modify large amounts of data.
- B.When all columns in the SELECT clause are present in the index.
- C.When the table contains millions of rows of text data.
- D.When the table has no primary key defined.
Show answer
B. When all columns in the SELECT clause are present in the index.
A covering index allows the database to retrieve all required data directly from the index tree without performing a costly 'bookmark lookup' to the actual table data. Options 1, 3, and 4 do not describe scenarios where index-only retrieval provides the specific benefit of avoiding heap access.
4. What is the primary trade-off of creating a B-Tree index on a column?
- A.Decreased disk space usage and faster write speeds.
- B.Faster read performance for point queries at the cost of slower write performance.
- C.Unlimited horizontal scaling of the database server.
- D.Automatic conversion of all queries into join operations.
Show answer
B. Faster read performance for point queries at the cost of slower write performance.
B-Tree indexes provide O(log n) lookup times for read operations but introduce overhead for every write. Option 1 is wrong because indexes increase space usage and slow down writes. Options 3 and 4 are irrelevant to the fundamental nature of B-Tree structures.
5. Which scenario makes a database index highly ineffective?
- A.Using a high-cardinality column in an equality filter.
- B.Querying a small subset of rows from a large table.
- C.Searching for a value in a column where every entry is identical.
- D.Joining two tables on their primary key columns.
Show answer
C. Searching for a value in a column where every entry is identical.
Indexes rely on the ability to distinguish between rows; if all entries are identical (zero cardinality), the index provides no filtering benefit, resulting in a full scan. High cardinality (Option 1) and small result sets (Option 2) are ideal for indexing, and joining on keys (Option 4) is the most efficient use of indexes.