Database Indexing

Database performance can make or break modern large scale applications. Imagine searching for a user profile by email in a table containing tens of millions of records. Without optimization, the database engine must inspect every single row sequentially from start to finish. For large tables, this full table scan introduces massive latency, consuming CPU and storage bandwidth.

Database indexes solve this fundamental challenge. By maintaining auxiliary data structures optimized for search operations, indexes allow database systems to locate requested records in O(log N) or O(1) time complexity without scanning the entire dataset. From catalog lookups in ecommerce systems to transactional record fetching in financial applications, indexes serve as the foundation of fast data access.

In system design interviews, understanding database indexing is vital. Candidates must know when to apply indexes, which columns benefit most, and how to select the right index data structure based on read versus write access patterns.

Planning the Approach

When evaluating database indexing in a system design interview, follow a structured framework:

1. Analyze query access patterns to distinguish point lookups from range scans, sorting requirements, and text searching.
2. Calculate read and write volume ratios to balance search speed gains against write amplification costs.
3. Choose the optimal index structure (such as B Tree, LSM Tree, Hash, Geospatial, or Inverted index) tailored to workload demands.
4. Apply advanced optimization strategies, including composite indexing, left prefix rules, and covering indexes to minimize table heap lookups.

Step 1: Requirements and Estimations

Functional Requirements

• Point Lookups: Retrieve single records instantly using unique attributes like user identifiers or emails.
• Range Queries: Retrieve sets of records bounded by timestamps, numerical values, or alphabetical ordering.
• Geospatial Proximity Search: Locate nearby entities based on coordinate distance calculations.
• Full Text Search: Execute relevance based keyword searches across large text document collections.

Non Functional Requirements

• Low Read Latency: Ensure index lookup times execute in sub millisecond timeframes.
• Write Throughput Stability: Manage write amplification so insertion and update operations remain responsive.
• Memory Efficiency: Keep primary index working sets within RAM memory buffers to minimize disk IO operations.

Back of the Envelope Estimations

Consider a relational table storing 100 million user accounts:

• Table Row Size: 500 bytes per record, yielding a total table size of 50 Gigabytes.
• Unindexed Full Table Scan: Reading 50 Gigabytes from disk at 500 Megabytes per second sequential read speed requires 100 seconds per query.
• Indexed Lookup with B Tree: Assuming a page size of 8 Kilobytes and 100 entries per node (fanout of 100), the B Tree height is log100(100,000,000) which equals 4 levels.
• Resulting Disk IO: Navigating 4 tree levels requires only 4 block reads, completing lookups in under 5 milliseconds.

Step 2: Schema and Entities

Understanding indexed database schemas requires examining how secondary keys map to physical records.

CREATE TABLE users (
    user_id UUID PRIMARY KEY,
    email VARCHAR(255) UNIQUE NOT NULL,
    status VARCHAR(50) NOT NULL,
    created_at TIMESTAMP WITH TIME ZONE NOT NULL,
    location_lat DECIMAL(9,6),
    location_lng DECIMAL(9,6)
);

CREATE TABLE orders (
    order_id UUID PRIMARY KEY,
    user_id UUID NOT NULL REFERENCES users(user_id),
    amount DECIMAL(10,2) NOT NULL,
    order_date TIMESTAMP WITH TIME ZONE NOT NULL,
    status VARCHAR(50) NOT NULL
);

Indexed representations track key values alongside row pointers (row identifiers or primary keys). For example, an index on users(email) maps each email string directly to its corresponding storage block.

Step 3: API and Query Design

Efficient API design relies on underlying queries that hit targeted indexes instead of triggering table scans.

1. Point Lookup Query

SELECT user_id, status FROM users WHERE email = 'alice@example.com';

Index Strategy: A unique B Tree index on email provides instant point lookup functionality.

2. Range Query with Filtering and Sorting

SELECT order_id, amount, order_date 
FROM orders 
WHERE user_id = 'c4a8d0e2-1234-4567-89ab-cdef01234567' 
  AND status = 'COMPLETED' 
ORDER BY order_date DESC 
LIMIT 20;

Index Strategy: A composite B Tree index defined on (user_id, status, order_date DESC) satisfies filtering and ordering in a single pass.

Step 4: High Level Design

Architecture Diagram Generation Prompt: Create a high level architecture diagram showing a database storage engine layout. Display the write path leading through Write Ahead Logs, in memory MemTables, and flushed on disk SSTables for LSM structures. Show the read path utilizing Buffer Pools, B Tree leaf pages, heap data pages, Bloom filters, and secondary indexes.

Physical Storage and Memory Buffers

Database systems read and write storage data in fixed size units called pages (typically 4 Kilobytes to 16 Kilobytes).

1. Buffer Pool: An in memory cache storing frequently accessed data and index pages. When a query requests a record, the database checks the buffer pool first before issuing disk operations.
2. Clustered Index: Determines the physical storage order of rows on disk. Relational engines like MySQL InnoDB store table rows directly inside the leaf nodes of the primary key B Tree.
3. Non Clustered Index (Secondary Index): Maintained as a separate structure storing index keys alongside pointers to the corresponding primary key or physical heap location.

Step 5: Deep Dives and Production Case Studies

Deep Dive 1: B Tree Indexes

B Trees (and their variants like B+ Trees) serve as the standard index structure for relational databases like PostgreSQL, MySQL, and Oracle.

Structural Characteristics

• Balanced Tree Architecture: All leaf nodes reside at identical depths, guaranteeing predictable log time search paths.
• High Node Fanout: Each internal node holds hundreds of keys and child pointers, matching database storage page boundaries and keeping tree height low.
• Sorted Leaf Linkage: In B+ Trees, leaf nodes contain data records or row pointers and link directly to sibling nodes, allowing efficient range scans.

Production Suitability

B Trees excel at equality lookups (WHERE id = 5) and range queries (WHERE age BETWEEN 20 AND 30). Because nodes maintain sorted order, B Trees naturally service ORDER BY and GROUP BY operations without requiring separate sorting passes.

Deep Dive 2: LSM Trees (Log Structured Merge Trees)

Traditional B Trees require random disk writes during updates, which can bottleneck write intensive workloads. LSM Trees restructure storage access to turn random writes into sequential disk operations.

Internal Workflow

1. Write Ahead Log (WAL): Incoming write requests write sequentially to an append only log file on disk to guarantee durability.
2. MemTable: Simultaneously, data inserts into an in memory sorted data structure (such as a skip list).
3. SSTable (Sorted String Table): When the MemTable fills up, it flushes sequentially to disk as an immutable SSTable file.
4. Compaction: Background threads continuously merge and compact overlapping SSTables, removing deleted or stale record versions.

Handling Read Amplification

Because records spread across multiple SSTable files, reads might require searching several files on disk. Production systems like Apache Cassandra, RocksDB, and Google Bigtable utilize Bloom Filters (probabilistic in memory data structures) to quickly verify if an SSTable contains a specific key before reading disk blocks.

Deep Dive 3: Hash Indexes

Hash indexes utilize hash tables to map key values directly to array buckets holding row references.

Trade Offs

• Strengths: Delivers O(1) constant time performance for point lookups, making it extremely fast for exact equality queries.
• Limitations: Does not support range searches, inequality comparisons, or prefix matching because hash values destroy natural key sorting order.
• Production Usage: Employed in caching engines like Redis and specialized in memory hash indexes in PostgreSQL.

Deep Dive 4: Geospatial Indexes

Standard one dimensional index structures like B Trees cannot efficiently evaluate two dimensional spatial queries (such as finding drivers within a 5 kilometer radius).

Key Geospatial Techniques

1. Geohash: Encodes latitude and longitude pairs into alphanumeric strings representing hierarchical grid cells. Nearby locations share matching string prefixes, allowing standard B Tree range scans.
2. Quadtree: Recursively subdivides two dimensional space into four quadrants whenever point density exceeds node capacity. Excellent for in memory spatial indexing.
3. R Tree: Groups spatial objects into hierarchical minimum bounding rectangles. Used extensively in PostGIS for spatial operations.

Deep Dive 5: Inverted Indexes

Inverted indexes power search engines like Elasticsearch, Apache Lucene, and OpenSearch.

Mechanism

Instead of mapping documents to words, an inverted index maps individual terms to lists of document identifiers (posting lists) where those terms appear.

"database" -> [Doc1, Doc3, Doc7]
"indexing" -> [Doc1, Doc2, Doc3]

When searching for queries like "database indexing", the search engine fetches the posting lists for both terms and executes set intersection operations to identify matching documents instantly.

Deep Dive 6: Advanced Index Optimization Patterns

Composite Indexes and Left Prefix Rules

A composite index covers multiple columns, such as INDEX idx_user_status (user_id, status).

Under the Left Prefix Rule, queries must filter by the leftmost columns of the composite index to utilize it effectively. A query filtering only by status cannot use idx_user_status. Additionally, place high cardinality equality columns first, followed by range condition columns.

Covering Indexes and Index Only Scans

A covering index contains all columns requested by a query. When a query selects columns fully present in the index structure, the database engine performs an Index Only Scan, bypassing heap table access entirely and cutting disk IO in half.

Partial and Filtered Indexes

Partial indexes index a subset of rows satisfying a specific predicate, such as CREATE INDEX idx_unprocessed ON tasks(created_at) WHERE status = 'PENDING'. This drastically reduces index storage footprints and write overhead while accelerating targeted background queries.