Database indexing in HLD - System Design Exercise

Design: Database Indexing System

Design focuses on indexing mechanisms within a database system. Query parsing, transaction management, and full database engine design are out of scope.

Functional Requirements

FR1: Support fast lookup of records by indexed columns

FR2: Allow multiple types of indexes (e.g., B-tree, hash)

FR3: Support efficient insert, update, and delete operations with index maintenance

FR4: Enable queries to use indexes to reduce search time

FR5: Provide ability to create and drop indexes dynamically

FR6: Handle large datasets with millions of records

FR7: Support composite (multi-column) indexes

Non-Functional Requirements

NFR1: Index lookup latency should be under 10ms for 1 million records

NFR2: Index maintenance should not degrade write throughput by more than 20%

NFR3: System availability target is 99.9% uptime

NFR4: Indexes should not consume more than 30% additional storage compared to raw data

NFR5: Support concurrent read and write operations without blocking

Think Before You Design

Questions to Ask

❓ Question 1

❓ Question 2

❓ Question 3

❓ Question 4

❓ Question 5

❓ Question 6

❓ Question 7

Key Components

Index manager module

Data storage engine

Query optimizer to use indexes

Concurrency control for index updates

Index data structures (B-tree, hash, bitmap)

Background index maintenance tasks

Design Patterns

B-tree indexing for range queries

Hash indexing for equality lookups

Composite index design

Write-ahead logging for index durability

Lazy index updates or batch rebuilding

Caching frequently accessed index nodes

Reference Architecture

  +-------------------+       +-------------------+       +-------------------+
  |   Query Processor | <---> |   Index Manager   | <---> |   Storage Engine  |
  +-------------------+       +-------------------+       +-------------------+
           |                           |                           |
           |                           |                           |
           v                           v                           v
  +-------------------+       +-------------------+       +-------------------+
  |  Query Optimizer  |       |  Index Data Store |       |  Data File Store  |
  +-------------------+       +-------------------+       +-------------------+

Components

Query Processor

Database engine component

Receives queries and coordinates execution using indexes

Index Manager

Module within database engine

Creates, maintains, and queries indexes

Storage Engine

Database storage layer

Stores raw data and index data structures on disk

Query Optimizer

Database engine component

Decides when and which indexes to use for queries

Index Data Store

B-tree and hash structures on disk

Stores index nodes and metadata

Data File Store

Disk files or SSD storage

Stores actual table data records

Request Flow

1. Client sends query to Query Processor

2. Query Processor passes query to Query Optimizer

3. Query Optimizer checks available indexes in Index Manager

4. If suitable index exists, Query Optimizer plans index scan

5. Query Processor requests Index Manager to perform index lookup

6. Index Manager traverses index data structure (e.g., B-tree) in Index Data Store

7. Index Manager returns matching record pointers to Query Processor

8. Query Processor fetches records from Storage Engine's Data File Store

9. Results are returned to client

10. For write operations, Index Manager updates indexes concurrently with data writes

Database Schema

Entities: - Table: stores data records - Index: metadata about each index (name, columns, type) - IndexNode: nodes of B-tree or hash buckets storing keys and pointers Relationships: - Table has many Indexes - Index consists of many IndexNodes - IndexNodes link to Table records via pointers

Scaling Discussion

Bottlenecks

Index maintenance slows down write-heavy workloads

Index size grows large, increasing disk and memory usage

Concurrent index updates cause locking and contention

Query optimizer may choose suboptimal indexes as data grows

Index rebuilds take long time on large datasets

Solutions

Use asynchronous or lazy index updates to reduce write latency

Implement index compression and partial indexes to save space

Use fine-grained locking or lock-free data structures for concurrency

Collect statistics regularly to help optimizer choose best indexes

Support online index rebuilds and incremental index maintenance

Interview Tips

Time: Spend 10 minutes understanding indexing needs and constraints, 15 minutes designing components and data flow, 10 minutes discussing scaling and trade-offs, 10 minutes for Q&A.

Explain why indexes improve read performance

Discuss trade-offs between read speed and write overhead

Describe common index data structures and their use cases

Show understanding of concurrency and consistency in index updates

Mention how query optimizer leverages indexes

Address scaling challenges and practical solutions

Practice

1. What is the primary purpose of a database index?

easy

A. To increase the size of the database

B. To speed up data retrieval by allowing quick lookups

C. To store backup copies of data

D. To encrypt the database contents

Solution

1. Step 1: Understand what an index does

   An index helps the database find data faster by creating a quick lookup structure.

2. Step 2: Identify the main benefit

   This quick lookup reduces the time needed to search large tables.

3. Final Answer:

   To speed up data retrieval by allowing quick lookups -> Option B

4. Quick Check:

   Index = Faster data search [OK]

Hint: Indexes speed up searches by creating shortcuts [OK]

Common Mistakes:

• Thinking indexes store extra data copies
• Confusing indexes with backups
• Assuming indexes encrypt data

2. Which of the following is the correct syntax to create an index on the column user_id in SQL?

easy

A. CREATE INDEX idx_user ON users (user_id);

B. INDEX CREATE user_id ON users;

C. CREATE users INDEX ON user_id;

D. MAKE INDEX user_id IN users;

Solution

1. Step 1: Recall SQL syntax for creating indexes

   The standard syntax is CREATE INDEX index_name ON table_name (column_name);

2. Step 2: Match the syntax with options

   CREATE INDEX idx_user ON users (user_id); matches the correct syntax exactly.

3. Final Answer:

   CREATE INDEX idx_user ON users (user_id); -> Option A

4. Quick Check:

   CREATE INDEX ... ON ... (column) [OK]

Hint: Remember: CREATE INDEX name ON table(column) [OK]

Common Mistakes:

• Swapping table and column names
• Using wrong keyword order
• Missing parentheses around column

3. Given a table orders with an index on order_date, what will be the output of the query plan for SELECT * FROM orders WHERE order_date = '2023-01-01';?

medium

A. Full table scan without using the index

B. Ignoring the order_date column completely

C. Sorting all rows by order_date before filtering

D. Index seek on order_date to quickly find matching rows

Solution

1. Step 1: Understand how indexes affect query plans

   An index on order_date allows the database to quickly locate rows matching the date.

2. Step 2: Identify the expected query plan

   The database will perform an index seek to find matching rows efficiently, not scan the whole table.

3. Final Answer:

   Index seek on order_date to quickly find matching rows -> Option D

4. Quick Check:

   Indexed column = index seek [OK]

Hint: Indexed WHERE columns use index seek, not full scan [OK]

Common Mistakes:

• Assuming full table scan despite index
• Confusing sorting with filtering
• Ignoring index usage in query plan

4. A developer created an index on a column but notices no improvement in query speed. What could be a likely reason?

medium

A. The database automatically disables all indexes

B. The index was created with the wrong SQL syntax

C. The queries do not filter or sort using the indexed column

D. Indexes always slow down queries

Solution

1. Step 1: Analyze index usage conditions

   Indexes only help if queries use the indexed column in WHERE, JOIN, or ORDER BY clauses.

2. Step 2: Identify why no speed improvement occurs

   If queries don't use the indexed column, the index is ignored, so no speed gain.

3. Final Answer:

   The queries do not filter or sort using the indexed column -> Option C

4. Quick Check:

   Index helps only if column used in query [OK]

Hint: Index unused if queries ignore indexed columns [OK]

Common Mistakes:

• Assuming syntax error disables index
• Believing all indexes slow queries
• Thinking database disables indexes by default

5. You have a large table with frequent inserts and queries filtering by status and created_at. Which indexing strategy balances read speed and write overhead best?

hard

A. Create a composite index on (status, created_at)

B. Create separate indexes on status and created_at individually

C. Create no indexes to avoid write overhead

D. Create a full-text index on status and created_at

Solution

1. Step 1: Understand composite vs separate indexes

   A composite index on (status, created_at) helps queries filtering on both columns efficiently.

2. Step 2: Consider write overhead and query patterns

   Separate indexes increase write overhead more than one composite index and may be less efficient for combined filters.

3. Step 3: Exclude unsuitable options

   No indexes hurt read speed; full-text index is for text search, not filtering by status/date.

4. Final Answer:

   Create a composite index on (status, created_at) -> Option A

5. Quick Check:

   Composite index = balanced read/write [OK]

Hint: Composite indexes optimize multi-column filters with less overhead [OK]

Common Mistakes:

• Creating many separate indexes causing slow writes
• Skipping indexes hurting read performance
• Using full-text index for non-text filtering