Indexes

An index is a data structure (commonly a B-tree or B+ Tree) that makes data retrieval faster by avoiding full table scans — much like the index at the back of a book. Indexes dramatically speed up reads and sorting, but they must be updated on every write, adding overhead and storage.

1. Learning Objectives

By the end of this lesson, you will be able to:

• Explain the fundamental trade-off of database indexes (read latency vs. write throughput and storage consumption).
• Differentiate between clustered and non-clustered indexes, and describe how they store keys and physical records.
• Analyze the structural characteristics of B+ Trees and LSM-Trees, and justify which is appropriate for read-heavy vs. write-heavy access patterns.
• Apply the leftmost prefix rule to design composite indexes that optimize multi-column filter, join, and sort operations.
• Utilize database profiling tools (such as EXPLAIN and EXPLAIN ANALYZE) to identify Index Seeks, Index Scans, and Table Scans.
• Diagnose index-related issues in production, including index bloat, index write overhead, and query sargability.

2. Prerequisites

Before diving into database indexing, you should be comfortable with:

• Relational Database Basics: Understanding tables, columns, primary keys, and foreign keys.
• SQL Query Syntax: Writing and reading common SQL statements using WHERE, JOIN, ORDER BY, and GROUP BY.
• Basic Data Structures: Familiarity with Binary Search Trees (BST), hash tables, and logarithmic search complexity (O(log N)).
• Storage Mediums: Conceptual understanding of memory hierarchies, pages, disk I/O cost, and physical block accesses.

3. Why This Topic Matters

At scale, databases are the most common bottleneck in any software architecture. Without indexing, querying a table with millions or billions of rows requires the storage engine to read every single data page from disk (a full Table Scan). For a large dataset, this can turn a sub-millisecond retrieval into a minutes-long operation, saturating CPU, blocking database connections, and causing system-wide timeouts.

Mastering indexes is essential for designing high-performance systems. In online transaction processing (OLTP) systems, where latency requirements are strict, proper indexing ensures fast lookups. Conversely, in write-heavy systems (like logging and telemetry), over-indexing can degrade write performance, exhausting disk queue depth and creating resource contention. System design interviews frequently probe candidates on indexing trade-offs to assess their ability to scale database systems under realistic workloads.

4. Real-world Analogy

Imagine walking into a large public library containing 100,000 books. You are looking for a book on "B+ Trees in Database Engines."

Without an Index (Table Scan): You would have to walk through every shelf, picking up every book, checking its title, and putting it back, until you find the book you need. If the book is at the very end of the library, you will have inspected all 100,000 books. This is highly inefficient.

With an Index (B+ Tree Seek): You walk up to the library's card catalog. The cards are arranged alphabetically by topic. You quickly flip to "Database Engines" (which takes seconds because the cards are sorted), find the card for "B+ Trees," note its shelf location (e.g., Row 42, Shelf B, Position 7), and walk directly to that shelf to pick up the book. The card catalog is an index: it is a separate physical structure, kept in a specific sorted order, mapping keys (book titles) to locations (shelf numbers).

5. Core Concepts

To design efficient database indexes, you must understand these core terminologies:

Clustered Index

A clustered index dictates the physical layout of the table data on disk. When a table has a clustered index, the data rows themselves are stored in the leaf nodes of that index. Because physical data can only be sorted in one order, a table can have only one clustered index (usually the primary key).

Non-Clustered (Secondary) Index

A secondary index is a separate data structure stored away from the actual table data. The leaf nodes of a secondary index do not contain the actual data rows. Instead, they contain the indexed key values and a pointer or reference back to the corresponding data row (the Clustered Index Key or a physical Row ID).

Composite Index

Also known as a compound or concatenated index, this is an index built on multiple columns (e.g., CREATE INDEX idx_user_status ON users(status, created_at)). It is optimized for queries that filter or sort by these columns in combination.

Leftmost Prefix Rule

A composite index is sorted hierarchically from left to right. This means an index on (A, B, C) is sorted first by A, then by B within matching A values, and finally by C within matching A, B values. Consequently, the query planner can use this index for searches filtering on (A), (A, B), or (A, B, C), but not for queries filtering only on (B) or (C).

Index Seek vs. Index Scan

• Index Seek: The database engine traverses the tree structure from the root to locate specific matching records (highly efficient, logarithmic cost).
• Index Scan: The database engine traverses the entire leaf level of the index from start to finish. This is slower than a seek, but still faster than a full Table Scan if the index is smaller than the table.

Covering Index

An index that contains all the columns requested in the query (both in the SELECT and WHERE clauses). When a covering index is used, the storage engine retrieves all the needed data directly from the index page itself, completely skipping the secondary lookup step to the physical table.

6. Visualization

The interactive diagram below visualizes index structures and lookup paths:

The flowchart below contrasts the difference between a direct Clustered Index search and a Non-Clustered (Secondary) Index search that requires an additional pointer lookup:

7. How It Works

Let's walk through the lifecycle of database lookup operations and index management step-by-step.

1. Querying Without an Index (Full Table Scan): When a query like SELECT * FROM users WHERE email = 'alice@example.com' runs without an index, the database storage engine reads the data blocks sequentially from the disk into the memory buffer pool. It checks the email field of every row. This requires O(N) operations and massive physical I/O.
2. Index Creation: When you execute CREATE INDEX idx_users_email ON users(email), the database reads the table, extracts the email values alongside their physical storage pointers (row IDs or primary keys), sorts these values, and constructs a balanced search tree (typically a B+ Tree) on disk.
3. Point Lookup with Index (Index Seek): When the query runs again, the optimizer recognizes the index on email. The storage engine starts at the root node of the index tree. It performs binary-like comparisons on the key, traversing down internal nodes until it hits the specific leaf node containing 'alice@example.com'.
4. Row Reference Resolution (Bookmark Lookup): If the index is non-clustered, the leaf node provides the primary key or row ID pointer for 'alice@example.com'. The storage engine then performs a second quick lookup in the clustered index (or heap space) to retrieve the complete data row (e.g., user name, password hash, created timestamp).
5. Range Query Traversal: For queries like WHERE age BETWEEN 21 AND 25, the engine performs a seek to find the first leaf node matching 21. In a B+ Tree, leaf nodes are linked in a doubly-linked list. The engine simply walks sequentially along this list to retrieve values 22, 23, 24, and 25, avoiding any further vertical tree traversals.
6. Index Maintenance during Write Operations: When a row is inserted, updated, or deleted, the database automatically modifies the index. For an insert, it locates the correct leaf page. If the page is full, it splits the page, redistributes keys, and adjusts parent node pointers to keep the tree balanced.

8. Internal Architecture

A database index is composed of several architectural layers. The table below details the components, their responsibilities, and how they fail:

Component	Responsibilities	Failure / Performance Issue
Root Node	The entry point of the index tree. Directs traversal to lower levels. Always kept in RAM buffer cache.	High concurrency bottleneck if multiple threads block waiting to latch the root node.
Internal/Branch Nodes	Store routing keys and block pointers. Guide searches from the root to leaf nodes.	Can get fragmented or bloated if underlying keys are constantly updated.
Leaf Nodes	Contain the indexed keys and data pointers (or clustered row data). Linked to adjacent leaves.	Page Splits: Inserting random keys (e.g., UUIDv4) forces leaf pages to split, leading to physical fragmentation and empty space.
Buffer Pool / Cache	RAM allocation where index pages are cached. Avoids reading blocks from physical disk.	Cache Eviction: If indexes exceed the buffer pool size, pages must be continually swapped to disk, causing disk thrashing.
Write-Ahead Log (WAL)	Records index structure updates sequentially before applying them, ensuring durability.	Heavy updates can saturate disk I/O channels with WAL writes, choking overall system throughput.

9. Request Lifecycle

Here is the detailed flow of a query request utilizing database indexes:

1. Query Parsing and Analysis: The SQL query arrives from the application server. The engine checks syntax and parses it into an abstract syntax tree (AST).
2. Query Optimization and Planning: The database cost-based optimizer (CBO) analyzes the table statistics (e.g., estimated row count, data distribution, and index cardinality). It estimates the disk cost of a Table Scan vs. utilizing available indexes.
3. Index Selection: The optimizer chooses the index with the lowest cost. If a composite index matches the columns in the WHERE clause in a valid order, it is selected.
4. Index Traversal (Seek): The execution engine requests the root node of the selected index. It traverses down the tree using pointers, fetching branch pages from the RAM Buffer Pool (or disk if they have been evicted).
5. Key Matching and Row Pointer Extraction: Once the leaf page is reached, the matching keys are extracted along with their physical row addresses (or clustered keys).
6. Data Page Fetching (Bookmark Lookup): If required fields are not present in the index (non-covering index), the storage engine reads the actual data pages from disk/cache to retrieve the full row.
7. Result Compilation: The database engine sorts (if needed), filters, and streams the selected rows back to the client application.

10. Deep Dive

Let's explore the mathematical, structural, and performance nuances of different indexing architectures.

B-Trees vs. B+ Trees

While textbooks mention standard B-Trees, relational databases (PostgreSQL, MySQL, SQL Server) almost exclusively use B+ Trees. The key differences are:

• Data Storage: Standard B-Trees store data pointers in both internal nodes and leaf nodes. B+ Trees store data records (or pointers to them) only in leaf nodes. Internal nodes contain only routing keys.
• Branching Factor (Fan-out): Because internal nodes in a B+ Tree do not store data pointers, they are smaller and can fit many more routing keys per database page. A higher fan-out means a wider, flatter tree, reducing the tree height (typically 3 or 4 levels even for millions of rows), which minimizes disk seeks.
• Range Scans: In a standard B-Tree, range scans require traversing up and down the tree branches recursively. In a B+ Tree, leaf nodes are linked sequentially (often as a doubly-linked list), enabling efficient, sequential single-pass scans once the first key is located.

Log-Structured Merge-Trees (LSM-Trees)

For write-heavy applications (e.g., time-series databases, log aggregators, and NoSQL stores like Cassandra or RocksDB), B+ Trees present a bottleneck: writing to random locations in the B+ Tree triggers slow, random disk updates and page splits. LSM-Trees solve this by converting random writes into sequential writes:

• MemTable: Incoming writes (inserts/updates) are written to a sequential commit log on disk (for durability) and inserted into an in-memory sorted structure called the MemTable.
• SSTables (Sorted String Tables): When the MemTable is full, it is flushed to disk as an immutable SSTable. Because the SSTable is written in one continuous append, disk I/O is fully sequential.
• Compaction: Over time, multiple SSTables accumulate on disk. A background thread runs "compaction" to merge these sorted files, removing duplicate or deleted records and creating optimized, larger sorted tables. Reads must search the MemTable and then check multiple SSTables (often using Bloom Filters to avoid empty lookups), making LSM reads slower than B+ Tree reads in exchange for much faster writes.

Hash Indexes

Hash indexes construct a hash table over the indexed column. They offer O(1) point lookups, but have substantial limitations:

• No support for range queries (e.g., WHERE age > 30) because hash functions destroy order.
• No support for partial key matches (composite keys must match fully).
• Cannot optimize ORDER BY statements.

Specialized Indexes: GIN and GiST

• GIN (Generalized Inverted Index): Used for multi-valued fields like arrays, JSONB documents, or full-text documents. A GIN index maps individual elements (like tags in an array or words in a document) to the rows containing them.
• GiST (Generalized Search Tree): Used for custom, multi-dimensional structures. GiST is ideal for geospatial data (e.g., finding points within a polygon) and range data.

11. Production Example

Let's look at how large-scale companies use and scale indexing:

1. Slack: Scaling Document Searches with GIN and Elasticsearch

Slack stores millions of chats. To perform rapid searches across text and custom JSON payloads, their storage layer relies on PostgreSQL GIN indexes and Elasticsearch. A standard B-Tree cannot look inside an array or match arbitrary substrings efficiently. By using GIN (Inverted Indexes), Slack splits incoming search strings into separate lexemes and maps them back to the exact database messages, achieving fast search times across multi-tenant data stores.

2. Uber: Handling Write-Heavy Telemetry Data

Uber originally used MySQL (with standard InnoDB B+ Trees) to store ride telemetry and driver locations. However, the high frequency of incoming updates meant that MySQL had to repeatedly update indexes across a massive dataset, causing heavy write amplification, locking issues, and disk write exhaustion. Uber migrated their storage layer to a custom, schema-less system (built on top of Cassandra/LSM-Tree models) that writes updates sequentially, minimizing disk page rewrites.

3. Amazon: DynamoDB Global Secondary Indexes (GSIs)

Amazon's DynamoDB uses partitioning to scale. To query data by fields other than the primary partition key, DynamoDB replicates the main table's data to a new storage area sorted by a different key: a Global Secondary Index (GSI). These GSIs are updated asynchronously. Write throughput on GSIs must be budgeted separately, showing that indexes in distributed databases have tangible replication, network, and storage costs.

12. Advantages

• Accelerated Read Performance: Drops lookup latency from O(N) linear time to O(log N) logarithmic time, turning table scans into fast tree seeks.
• Optimized Sorting and Grouping: Speeds up ORDER BY and GROUP BY queries by avoiding expensive in-memory temporary sorting (filesort) if the index already maintains matching records in the requested order.
• Fast Joins: Speeds up relational joins (JOIN operations) by allowing the database engine to quickly look up matching rows in the foreign key table.
• Constraint Enforcement: Enforces data integrity requirements (e.g., UNIQUE constraints and Primary Keys rely on underlying unique indexes).
• Reduced Disk I/O: Avoids loading unnecessary data blocks from persistent storage into RAM.

13. Limitations

• Write Overhead: Every single write operation (INSERT, UPDATE, DELETE) must also write updates to the index structures. This degrades write throughput.
• Storage Overhead: Indexes require substantial physical storage. In many production databases, index storage can match or even exceed the size of the actual raw data table.
• Index Bloat and Fragmentation: As rows are updated and deleted, pages inside B+ Trees become fragmented with empty spaces (dead tuples). This reduces index scan performance and requires periodic rebuilding (e.g., REINDEX or VACUUM).
• Planning Overhead: Having too many indexes increases the complexity and time required for the query optimizer to evaluate and decide on the best query execution plan.

14. Trade-offs

When designing an index, consider these classic architectural trade-offs:

• Read Latency vs. Write Throughput: Adding indexes speeds up read queries but slows down inserts and updates. For highly transactional OLTP databases, select indexes selectively. For analytical databases (OLAP), build extensive indexes (or use column stores) to accelerate deep query scans.
• Index Size vs. Memory Buffer Space: Ideally, all database indexes should fit entirely in memory (RAM). If they don't, queries will cause index pages to be swapped in and out of the disk page buffer, degrading performance. Choose which columns to index based on their query frequency.
• Natural Sequential vs. Random Primary Keys (Auto-Incrementing Integer vs. UUID): Using auto-incrementing integers as a primary (clustered) key ensures sequential inserts, appending data to the end of the B+ Tree. This minimizes page splits. However, in distributed systems, UUIDs are preferred to avoid collisions. Using random UUIDs causes random inserts inside the tree, leading to heavy page splits, low page fill factor, and high physical disk I/O.

15. Performance Considerations

To maximize index performance, you must understand how the database planner evaluates columns:

• Cardinality: The count of unique values in a column. Columns with high cardinality (like email, usernames, or IDs) are excellent index candidates. Columns with low cardinality (like gender, boolean statuses, or country codes) make poor index candidates because the query planner will likely ignore the index and run a full Table Scan.
• Index Selectivity: Selectivity is calculated as (Matching Rows / Total Rows). An index is highly selective if queries matching the key retrieve a tiny fraction of the total rows (e.g., < 5%). Lower selectivity makes indexing less effective.
• Index Fill Factor: You can configure the percentage of space on each leaf page to fill during index creation (default is often 90-100%). Leaving a lower fill factor (e.g., 80%) reserves free space on pages to accommodate subsequent insertions, preventing expensive page splits at the cost of using more storage.

16. Failure Scenarios

Here are critical real-world database failures caused by indexing issues:

• Write Amplification Death Spiral: In a database table with 15 indexes, every single insert triggers 15 physical index writes. During a traffic spike, disk write latency escalates, causing thread pooling, connection timeouts, and application failure.
• Index Corruption: Disk errors, hardware faults, or database engine bugs can cause an index to lose sync with the physical table. Queries using the index may return incomplete or corrupt records, requiring a table-blocking REINDEX command to repair.
• Memory Eviction (Thrashing): As data grows, the total index size exceeds the RAM buffer pool. The database starts swapping index pages to disk. A single query that used to take 5 milliseconds now takes 2 seconds because it has to perform multiple random disk reads to fetch index blocks.
• Stale Planner Statistics: If the database statistics are not updated (e.g., via ANALYZE), the optimizer might choose a Table Scan even when a perfect index is available, causing sudden query performance degradation.

17. Best Practices

• Index Columns in Search, Join, and Sort Operations: Focus your indexing strategy on columns that appear inside WHERE clauses, JOIN conditions, and ORDER BY / GROUP BY clauses.
• Keep the Clustered Key Small: Since every secondary index leaf node references the clustered key, a large clustered key (e.g., a long composite string) makes every secondary index larger, ballooning overall memory usage.
• Use Partial (Filtered) Indexes: If you only query a subset of rows, create a filtered index (e.g., CREATE INDEX idx_active_users ON users(id) WHERE status = 'active'). This keeps index size small and efficient.
• Utilize Covering Indexes: Eliminate secondary lookup overhead by using INCLUDE (in SQL Server/Postgres) to attach non-key columns directly to the index leaf nodes.
• Order Composite Index Columns Wisely: Place the most selective and equality-filtered columns first (leftmost), followed by range-filtered and sorted columns.
• Regularly Monitor Index Usage: Query database catalog tables (like pg_stat_user_indexes in Postgres) to find and drop unused indexes.

18. Common Mistakes

• Indexing Every Column: Beginners often index every column in a table, thinking it speeds up all queries. This degrades write throughput and wastes storage.
• Creating Non-SARGable Queries: Wrapping indexed columns in functions (e.g., WHERE UPPER(email) = 'ALICE@EXAMPLE.COM' or WHERE DATE(created_at) = '2026-06-26') prevents the optimizer from performing an Index Seek. The engine must scan the entire index or table to compute the function for every row. (Fix: Use functional indexes or rewrite queries like WHERE created_at >= '2026-06-26 00:00:00' AND created_at < '2026-06-27 00:00:00').
• Ignoring the Leftmost Prefix Rule: Creating a composite index on (A, B) and then querying only by B. This query cannot use the index effectively.
• Indexing Low-Cardinality Columns: Indexing a column with very few unique values (e.g., is_deleted boolean) and expecting the database planner to use it for standard queries.

19. Implementation (Only If Applicable)

The following Python implementation demonstrates how database engines manage secondary indexes using sorted keys (simulating a B+ Tree leaf level) pointing to physical memory addresses, and benchmarks the lookups against a full Table Scan.

20. Interview Questions

Easy

Q: What is the main trade-off of database indexing?

A: The main trade-off is read speed vs. write speed and storage. Indexes speed up data retrieval (reads) significantly, but they slow down insertion, deletion, and modification (writes) because the database must keep the index structures synchronized. Additionally, indexes consume extra physical disk space and memory buffers.

Medium

Q: What is a composite index? Given an index on (A, B, C), which queries can make use of this index?

A: A composite index is an index constructed on multiple columns. Under the leftmost prefix rule, queries can use the index if they filter or sort by columns matching the index order from left to right starting with the first column.

• WHERE A = 1 — Yes (uses prefix A).
• WHERE A = 1 AND B = 2 — Yes (uses prefix A, B).
• WHERE A = 1 AND B = 2 AND C = 3 — Yes (uses A, B, C).
• WHERE B = 2 AND C = 3 — No (does not contain A, the leftmost column).
• WHERE A = 1 AND C = 3 — Partial (uses column A to seek, but must scan or filter manually on C since B is missing).

Hard

Q: Compare B+ Trees and LSM-Trees. Under what circumstances would you select each for a large-scale system?

A: The comparison centers on read vs. write workloads:

• B+ Trees:
  • Structure: Flattish balanced trees storing data pointers at the leaf levels.
  • Performance: Fast, predictable O(log N) reads and point updates. Write operations require updating pages in random order, which triggers page splits and high disk fragmentation.
  • Best for: Read-heavy OLTP databases (e.g., PostgreSQL/MySQL relational tables for user profiles or accounts).
• LSM-Trees:
  • Structure: Consist of an in-memory MemTable and multiple sorted, immutable disk files (SSTables) reorganized by a background compaction thread.
  • Performance: Write performance is high and sequential, avoiding random I/O. Read performance is slower because it might require searching the MemTable and multiple SSTables (optimized using Bloom filters).
  • Best for: Write-heavy systems (e.g., telemetry, timeseries metrics, activity streams, and NoSQL stores like Cassandra, Bigtable, or RocksDB).

21. Practice Exercises

Try these exercises on your own to reinforce your indexing design skills:

Easy

Design a SQL table schema for a products table containing: id (PK), sku (UUID string), name (string), and price (decimal). Write the exact SQL statements to index this table so that you can look up products by sku and query active sales sorted by price.

Medium

Analyze the following query execution plans. Explain why Plan B is faster than Plan A, and identify what index should be added to migrate a database engine from Plan A to Plan B:

• Plan A: Index Scan using idx_users_status on users (cost=0.42..154.23 rows=50 width=8) -> Filter: (country = 'US')
• Plan B: Index Seek using idx_users_status_country on users (cost=0.04..12.30 rows=50 width=8)

Hard

Assume a high-frequency system records user coordinates (latitude, longitude) every second. Write-heavy telemetry writes these coordinates, but users frequently query for neighboring drivers within a 5-mile radius. Formulate a comprehensive database indexing strategy that handles high-write speeds while supporting fast geo-spatial searches.

22. Challenge Problem

Design Scenario: Ride-Hailing Geospatial Indexing

You are the lead architect for a global ride-sharing application. The database receives 100,000 updates per second of GPS coordinates from active drivers. Simultaneously, riders request a list of the 10 closest drivers within a 2-mile radius.

A typical B+ Tree index on (latitude, longitude) fails because the coordinate queries require a two-dimensional range search, and updating the B+ Tree 100,000 times per second causes massive write contention and disk latency.

Explain how you would design a geospatial indexing system using Geohashes, Uber H3 grid cells, or quadtrees. Discuss where this index should reside (in-memory caching layer vs. disk-based storage engine) and how you would balance write amplification with query latencies.

23. Summary

An index is a fundamental database data structure that trades storage space and write performance to accelerate data read operations. Relational databases primarily leverage B+ Trees to achieve fast point lookups and sequential range queries. Write-heavy, distributed systems utilize LSM-Trees to convert slow, random disk writes into fast, sequential appends. Choosing the right index columns, respecting composite order rules, and avoiding non-SARGable query syntax is key to keeping databases scalable, responsive, and resource-efficient.

24. Cheat Sheet

This table serves as a quick revision guide for different database indexing technologies:

Index Type	Underlying Structure	Read Complexity	Write Complexity	Best Use Case
Clustered	B+ Tree (data in leaf nodes)	O(log N)	O(log N) (with page splits)	Primary Keys, Sequential IDs
Non-Clustered	B+ Tree (pointers in leaf nodes)	O(log N) + Seek lookup	O(log N)	Secondary filters (email, status)
Hash Index	Hash Table	O(1)	O(1) average	Exact match point lookups (no ranges)
LSM-Tree	MemTable + SSTables + Compaction	O(log N) (multiple seeks)	O(1) (sequential appends)	Write-intensive logs, metrics, telemetry
Inverted (GIN)	Map of elements to doc IDs	O(log N) per key term	High write cost	Full-text search, arrays, JSONB keys

25. Quiz

Select the best answer for each question. Answers and explanations are provided below.

1. Why can a database table have only one clustered index?
   • A: Because secondary indexes are stored in RAM, while clustered indexes are stored on disk.
   • B: Because a clustered index physically dictates the ordering of the rows on disk, and data can only be physically sorted in one order.
   • C: Because primary keys must be unique.
   • D: Because database engines only support one index per table.
2. Which data structure is preferred for general relational database indexing and why?
   • A: Standard Binary Search Trees because they have O(log N) lookup complexity.
   • B: Hash Tables because they provide O(1) reads for all types of queries.
   • C: B+ Trees because their high fan-out minimizes disk block reads, and linked leaf nodes allow efficient range queries.
   • D: LSM-Trees because they provide the fastest read performance across large datasets.
3. What happens during a "Page Split" in a B+ Tree index?
   • A: The database partition engine splits the database into two sharded nodes.
   • B: A full page is split into two pages to accommodate a new write, causing disk fragmentation and overhead.
   • C: The query optimizer splits a complex SQL statement into two subqueries.
   • D: The memory buffer pool page is swapped out to disk.
4. With a composite index on (first_name, last_name, age), which of the following queries CANNOT use this index?
   • A: WHERE first_name = 'John' AND last_name = 'Doe'
   • B: WHERE first_name = 'John'
   • C: WHERE last_name = 'Doe' AND age = 30
   • D: WHERE first_name = 'John' AND age = 30
5. What is a covering index?
   • A: An index that covers every table inside the database system.
   • B: An index that contains all columns referenced in the query, allowing the database to satisfy the read query entirely from the index without fetching actual table pages.
   • C: An index that is used during automated backup recovery operations.
   • D: An index that spans across multiple sharded databases.
6. Which query is "SARGable" (capable of utilizing an Index Seek)?
   • A: WHERE UPPER(username) = 'BOB'
   • B: WHERE join_date >= '2026-01-01'
   • C: WHERE YEAR(join_date) = 2026
   • D: WHERE substring(phone, 1, 3) = '555'
7. How do LSM-Trees achieve fast write throughput?
   • A: By storing all index data entirely in RAM.
   • B: By writing updates to an in-memory MemTable and flushing them to disk as sorted sequential appends, avoiding slow random disk updates.
   • C: By skipping the database logging phase (WAL).
   • D: By eliminating index lookups during database transactions.
8. If a column has very low cardinality (e.g., a boolean flag like 'is_processed'), how will the database optimizer likely treat queries filtered by this column?
   • A: It will perform a fast Index Seek.
   • B: It will ignore the index and run a full Table Scan.
   • C: It will split the table into two partitions.
   • D: It will throw a database query timeout error.
9. What is the purpose of the "Linked Leaf List" in a B+ Tree?
   • A: To map secondary indexes to the primary clustered key.
   • B: To speed up point lookups.
   • C: To allow the query engine to scan a range of keys sequentially without repeatedly traversing down from the root node.
   • D: To prevent the tree from ever splitting.
10. What index parameter can be customized to minimize page splits during heavy write workloads?
    • A: Cardinality
    • B: Selectivity
    • C: Fill Factor
    • D: Leftmost Prefix

---

Answer Key & Explanations

1. B - Physical data rows can only be ordered in one way on disk, so only one clustered index can exist per table.
2. C - B+ Trees have a high branching factor (high fan-out) which reduces tree height (and therefore disk I/O), and the linked leaf list allows rapid sequential range scans.
3. B - When a page is full and a new insert occurs, the page splits, which causes fragmentation and write overhead.
4. C - A query filtering by last_name and age violates the leftmost prefix rule because it misses the first column of the index (first_name).
5. B - A covering index contains all the data fields requested by the SELECT and WHERE clauses, avoiding the need to execute a bookmark lookup to the table heap page.
6. B - Wrapping columns in functions (like UPPER() or YEAR()) prevents Index Seeks (non-SARGable). WHERE join_date >= '2026-01-01' leaves the column clean and is SARGable.
7. B - LSM-Trees write data to MemTables and flush them as SSTables sequentially, reducing random write overhead.
8. B - Low cardinality means the index cannot effectively narrow down the rows, so the query planner will choose a Table Scan.
9. C - The leaf nodes are linked in a list to allow efficient range scans without having to backtrack up the tree.
10. C - Adjusting the fill factor (e.g., to 80%) leaves space on each index page, accommodating new rows without immediately triggering page splits.

26. Further Reading

• Designing Data-Intensive Applications by Martin Kleppmann (Chapter 3: Storage and Retrieval, covers B-Trees, LSM-Trees, and indexes in-depth).
• Database Internals by Alex Petrov (Part I: Storage Engines, covers B-Tree structures and LSM implementation details).
• Use The Index, Luke! (use-the-index-luke.com) by Markus Winand (A comprehensive guide to database indexing for developers).
• PostgreSQL Documentation on Index Types (B-Tree, Hash, GiST, GIN, BRIN).

27. Next Lesson Preview

In the next lesson, we will explore Database Replication and Partitioning (Sharding). We will study how to distribute data across multiple physical machines to scale read queries, improve fault tolerance, and partition datasets too large to fit on a single storage node.