Database indexing in HLD - System Design Guide

Problem Statement

When a database grows large, searching for data without any shortcuts means scanning every record. This causes slow query responses and high resource use, making the system inefficient and frustrating for users.

Solution

Database indexing creates a special data structure that acts like a fast lookup guide. Instead of scanning all records, the database uses the index to quickly find the location of the desired data, speeding up queries significantly.

Architecture

User Query

↓

Index Structure

Index Structure

↓

Data Records

Data Records

This diagram shows how a user query is first directed to the database, which uses the index structure to quickly locate the data records without scanning the entire dataset.

Trade-offs

✓ Pros

→

Speeds up data retrieval by avoiding full table scans.

→

Reduces CPU and I/O load during queries.

→

Improves user experience with faster response times.

→

Supports efficient sorting and filtering operations.

✗ Cons

→

Consumes extra storage space for the index data structures.

→

Slows down write operations like inserts, updates, and deletes due to index maintenance.

→

Requires careful design to avoid unnecessary or redundant indexes.

Use indexing when the database has large tables with frequent read queries that filter or sort on specific columns, especially when query response time is critical.

Avoid indexing small tables with mostly write operations or when the query patterns do not benefit from indexes, as the overhead may outweigh the benefits.

Real World Examples

Amazon

Amazon uses indexing on product catalogs to quickly retrieve items matching search filters and sort orders, enabling fast and relevant search results.

Twitter

Twitter indexes tweets by user and hashtags to efficiently serve timelines and search queries without scanning all tweets.

LinkedIn

LinkedIn applies indexing on user profiles and connections to speed up complex queries for recommendations and network searches.

Alternatives

Full Table Scan

Reads every record sequentially without any shortcut or index.

Use when: Choose when tables are very small or queries retrieve most of the data, making indexing overhead unnecessary.

Materialized Views

Precomputes and stores query results for fast access instead of indexing base tables.

Use when: Choose when queries are complex aggregations or joins that benefit from precomputed results.

Caching

Stores frequently accessed query results in fast memory rather than indexing the database.

Use when: Choose when read patterns are highly repetitive and data freshness requirements allow caching.

Summary

Database indexing creates fast lookup structures to avoid scanning all records during queries.

Indexes improve read performance but add storage cost and slow down writes due to maintenance.

Proper indexing depends on data size, query patterns, and balancing read/write trade-offs.