What is the maximum number of disk seeks required to find a row in a B-Tree index covering 10 million rows?

B-Trees are balanced; height h satisfies 2^h ≥ rows, so ~log(10M) ≈ 23 bits, but practical B-factor reduces this to 3–4 disk accesses.

What do leaf nodes in a B-Tree index store?

Leaf nodes hold index values plus pointers (addresses) to actual row locations; only leaf nodes touch the heap.

Why is a B-Tree called 'balanced'?

Balance means no path from root to leaf is significantly longer than another, guaranteeing logarithmic search time for any key.

You have a composite index (user_id, email). Which query will use this index most effectively?

Left-prefix rule: index (user_id, email) is usable for user_id alone or user_id+email. Query starting with user_id uses both columns fully.

Given composite index (last_name, first_name), can you efficiently filter by first_name alone?

Composite indexes are sorted by left columns first. Without matching the left prefix, the database cannot skip rows efficiently.

What is index cardinality?

High-cardinality columns like email are selective (few duplicates), making indexes on them useful. Low-cardinality (e.g., boolean flags) are less selective.

You have 50M orders, 5K with status='pending'. Should you create a full or partial index on status?

Partial index is 10,000x smaller, fits in cache, reduces write overhead, and satisfies nearly all queries on pending orders.

A partial index uses WHERE is_verified = FALSE. Can this index be used for WHERE is_verified = TRUE?

Partial index WHERE clause filters which rows are indexed. A query on opposite condition excludes most indexed rows, forcing full table scan.

Your query is ORDER BY created_at DESC LIMIT 10. Should you create an index ASC or DESC on created_at?

B-Tree can traverse forward or backward efficiently. DESC index matches DESC query, avoiding expensive in-memory sort of results.

What is a 'filesort'?

Filesort loads results into memory and sorts them using CPU; slow for large result sets. Proper indexes avoid this.

If a table has 5 indexes and you INSERT one row, how many total writes occur?

Database must update table and all 5 indexes for the new row. Each index insertion modifies B-Tree nodes, multiply write I/O.

You have a write-heavy table with millions of UPDATEs/sec. How many indexes should it have?

Write-heavy tables suffer from index maintenance overhead. Minimize indexes to those essential for critical queries.

What is write amplification in the context of indexing?

One app INSERT triggers index updates for every index, multiplying disk I/O. This ratio is write amplification.

In a URL shortener, what is the most critical query for performance?

Redirect lookup runs millions of times/day, directly impacting user experience. Must complete in milliseconds. UNIQUE index on short_code essential.

For URL shortener user dashboard (list user's URLs sorted by date), which index is best?

Composite (user_id, created_at DESC) satisfies WHERE user_id=X ORDER BY created_at DESC; scans only this user's rows in chronological order.

An expired URL cleanup query runs nightly: DELETE FROM urls WHERE expires_at < NOW(). Should it use a partial or full index?

Most URLs don't expire (expires_at IS NULL). Partial index only covers expirable URLs, saving space and write overhead.

To display top 100 players globally by score, which index is best?

Score DESC index lets database scan top scores in order without filesort; returns LIMIT 100 results from first leaf nodes.

For per-game leaderboards (SELECT top 100 WHERE game_id=X ORDER BY score DESC), what index is optimal?

Composite (game_id, score DESC) filters to game_id in leaf nodes, then scans scores in order; single-index approach requires merge.

You want to find a player's rank in a game (e.g., 'ranked 47th'). What's the index strategy?

UPSERT to player_best_scores avoids millions of rows; composite PK index enables fast score lookup; rank query counts via score index efficiently.

Unread notification badge runs on every page load. Should it use full or partial index?

Partial index is perfect: badges query unread only, index scales with active count not total notifications, auto-shrinks as users read.

Fetching unread notifications sorted newest first: SELECT * FROM notifications WHERE user_id=X AND is_read=FALSE ORDER BY created_at DESC. Best index?

Partial composite index scans exactly matching rows (user=X, unread) in order by time; no filesort or unrelated rows touched.

When a user marks a notification as read (UPDATE is_read=TRUE), what happens to the partial index WHERE is_read=FALSE?

Partial index predicate is re-evaluated; after UPDATE, is_read=FALSE is false, so row exits index automatically. Elegant cleanup.

Which statement best describes why B-Trees are superior to a simple sorted array for database indexes?

Arrays need bulk shifts on insert; B-Trees rebalance locally. Indexes must handle frequent writes; B-Trees excel.

You have queries: (1) WHERE a=X, (2) WHERE a=X AND b=Y, (3) WHERE b=Y. What's the best index strategy?

Composite (a,b) handles queries 1–2 via left-prefix. Query 3 needs separate index on b since it's not a left prefix of (a,b).

A partial index on (email) WHERE is_verified=FALSE indexes 1M unverified users out of 100M total. For a search query on verified users, this index is:

Partial index WHERE is_verified=FALSE excludes all verified rows. Querying verified users cannot use this index; must scan excluded rows.

Your query is ORDER BY created_at ASC, created_at_DESC? Which index direction is faster?

B-Trees traverse efficiently in both directions. ASC index scanned forward or backward both O(log n); direction choice is a minor optimization.

An analytics table receives 100K INSERTs/sec. Currently 8 indexes. Is this problematic?

Write amplification is multiplicative. 100K inserts become 800K total updates (100K table + 700K index). Limit to 2–3 critical indexes for high-volume writes.

You want to prevent duplicate short_codes in a URL shortener. Best approach?

UNIQUE index is the standard approach: enforces data integrity at database level, can't be bypassed, and indexes for speed simultaneously.

In a competitive game, players compete in 'seasons'. Index strategy for leaderboard queries across all seasons and per-season?

Composite (season_id, score DESC) is flexible: all-seasons scan traverses seasons in order then scores within each; per-season fast via left-prefix.

A user has 10K notifications (1K unread). Partial index WHERE is_read=FALSE is created. When deleting all 1K unread, what happens to query performance?

Partial index is perfect for this: updates remove rows from it automatically. After bulk mark-as-read, partial index shrinks, improving future badge queries.

Database Indexes: Making Queries Fast — System Design Concept

🍪 TechCookies

Free

📚Database Indexes: Making Queries FastFree

11 sections

~32 min total

30 quick quizzes

3 SD challenges linked

0 of 11 done·~30 min left

Concepts›Database Indexes: Making Queries Fast›What is Database Indexes: Making Queries Fast?

0 / 11

11 sections~32 min

What is Database Indexes: Making Queries Fast?

Database indexes accelerate query lookups using B-Tree structures, balancing read speed against write cost

Read

~3 min

⋯

How Indexes Work: The B-Tree Analogy

B-Trees are self-balancing tree structures enabling logarithmic search; leaf nodes point to table rows

ReadQuizCode

~3 min

⋯

Single-Column vs Composite Indexes

Composite indexes follow left-prefix rule; only leading column prefixes unlock the index efficiently

ReadQuizCode

~3 min

⋯

Partial Indexes

Indexes filtered by WHERE clause reduce size and maintenance cost by covering only relevant rows

ReadQuizCode

~3 min

⋯

Index on Sort Columns (created_at DESC)

Indexes in sorted order eliminate expensive filesorts; DESC direction matches ORDER BY descending queries

ReadQuizCode

~3 min

⋯

The Cost of Over-Indexing (Write Slowdown)

Each index multiplies write cost; excess indexes hurt INSERT/UPDATE/DELETE performance severely

ReadQuizCode

~3 min

⋯

Relevant System Design Questions

Apply index patterns to production systems: URL shorteners, leaderboards, notifications

Read

~3 min

⋯

URL Shortener

Redirect lookups are critical; UNIQUE index on short_code dominates, plus composite for user queries

ReadQuizCode

~3 min

⋯

Game Scoreboard

Score DESC index enables fast leaderboard queries; composite with game_id for multi-game ranking

ReadQuizCode

~3 min

⋯

Notification System

Partial index on unread notifications shrinks automatically as users read, avoiding bloat

ReadQuizCode

~3 min

⋯

Practice test

30 questions

~10 min

Section 1 of 11Read

What is Database Indexes: Making Queries Fast?

Database indexes accelerate query lookups using B-Tree structures, balancing read speed against write cost

~3 min read

Imagine you walk into a massive library with 10 million books, and someone asks you to find a book titled "The Silent Shore". Without any system, you'd have to check every single book one by one — that could take hours. But if the library has an alphabetical card catalog, you can jump straight to the "S" section and find it in seconds. Database indexes work exactly the same way. They are special data structures that allow the database engine to find rows quickly without scanning every row in a table. This guide will walk you through how indexes work under the hood, when to use them, when to avoid them, and how they apply to real-world system design problems.

Mark this section complete.

Notes

🔍

Loading…