SQL Indexing, B-Trees & Query Optimization Flashcards

Question 1

Clustered Index

Accepted Answer

An index that defines the physical storage order of data rows within a table. Because physical data can only be sorted in one way, a table can have only **one** clustered index. Primary keys create a clustered index by default in most RDBMS engines (e.g., MySQL InnoDB).

Question 2

Non-Clustered Index

Accepted Answer

A separate index structure that stores sorted key values along with pointers (row locators or primary key values) back to the actual data rows. A single table can support **multiple** non-clustered indexes.

Question 3

B-Tree vs. B+ Tree

Accepted Answer

In a **B-Tree**, keys and data pointers are stored in both internal and leaf nodes. In a **B+ Tree**, data/row pointers exist *exclusively* in leaf nodes, while internal nodes store only search keys. B+ Tree leaf nodes are linked in a doubly-linked list, drastically improving range queries.

Question 4

B+ Tree Node Splitting

Accepted Answer

An operation triggered when inserting a record into a node that has reached its maximum capacity $M$. The node splits into two child nodes, each containing approximately $\lceil M/2 \rceil$ elements, and the median key is promoted to the parent node.

Question 5

Leftmost Prefix Rule (Composite Indexes)

Accepted Answer

For a composite index on columns `(A, B, C)`, the query optimizer can only use the index if the query filtering conditions match from left to right without skipping. A query filtering by `(A)` or `(A, B)` utilizes the index, but filtering by `(B, C)` alone cannot.

Question 6

Covering Index

Accepted Answer

An index that contains **all** columns requested by a SQL query (both in `WHERE`, `SELECT`, and `JOIN` clauses). This allows the query engine to satisfy the request using an **Index-Only Scan** without looking up data from the base table.

Question 7

Table Scan (Sequential Scan)

Accepted Answer

A operation where the database engine reads every page and row of a table sequentially. It occurs when no usable index exists, or when the query engine determines that reading the entire table is faster than random index lookups due to low selectivity.

Question 8

Index Seek vs. Index Scan

Accepted Answer

An **Index Seek** traverses the B-Tree structure directly to locate matching rows in $O(\log N)$ time. An **Index Scan** reads all or part of the index pages sequentially in $O(N)$ time, typically when no leading index key condition is provided.

Question 9

EXPLAIN Execution Plan

Accepted Answer

A diagnostic command (e.g., `EXPLAIN ANALYZE SELECT ...`) that reveals how the query optimizer intends to execute a query. It exposes scan types, join algorithms (e.g., Nested Loop, Hash Join), index usage, cost estimates, and actual execution times.

Question 10

Index Selectivity

Accepted Answer

The measure of uniqueness of data in a column, calculated as:
$$	ext{Selectivity} = \frac{	ext{Unique Values}}{	ext{Total Rows}}$$
High selectivity (close to $1.0$, such as UUIDs or primary keys) indicates ideal candidates for indexing.

Question 11

Implicit Type Conversion Pitfall

Accepted Answer

Occurs when a query compares an indexed column to a value of a different data type (e.g., `WHERE varchar_col = 123`). The database implicitly applies a conversion function to the column for every row, invalidating index usage and triggering a full table scan.

Question 12

SARGable Queries

Accepted Answer

**S**earch **A**rgument **A**ble queries are structured to allow the database to use an index. Wrapping an indexed column inside a function (e.g., `WHERE YEAR(created_at) = 2023`) makes it non-SARGable. Rewriting it as `WHERE created_at >= '2023-01-01'` restores SARGability.

Question 13

Fill Factor

Accepted Answer

A configuration percentage that determines how full the engine makes leaf-level index pages when creating or rebuilding an index. Reserving free space (e.g., Fill Factor = 80%) reduces expensive page splits caused by future `INSERT` and `UPDATE` operations.

Question 14

Bookmark Lookup (Key / RID Lookup)

Accepted Answer

The process where the database engine uses a row locator from a non-clustered index to retrieve additional non-indexed columns from the underlying clustered index (Key Lookup) or heap (RID Lookup).

Question 15

Hash Index

Accepted Answer

An index structure that maps key values to row locations using a hash table. It delivers $O(1)$ performance for exact equality lookups (`=`), but cannot be used for range scans (`<`, `>`, `BETWEEN`) or pattern matching (`LIKE`).

Question 16

Partial Index (Filtered Index)

Accepted Answer

An index built over a subset of rows defined by a predicate, created with a `WHERE` clause:
```sql
CREATE INDEX idx_unprocessed 
ON orders (created_at) 
WHERE status = 'PENDING';
```
Reduces index footprint and maintenance overhead for targeted queries.

Question 17

GIN vs. GiST Indexes (PostgreSQL)

Accepted Answer

**GIN** (Generalized Inverted Index) maps component values (e.g., JSONB keys, array elements, text tokens) to row IDs, making it optimal for multi-value searches. **GiST** (Generalized Search Tree) handles complex dynamic structures like geometric shapes (PostGIS) and range types.

Question 18

Write Amplification in Database Indexes

Accepted Answer

The performance penalty incurred on write operations (`INSERT`, `UPDATE`, `DELETE`). Every additional index on a table requires the engine to modify both the underlying table and the index structures, increasing disk I/O and CPU overhead.

Question 19

Foreign Key Indexing

Accepted Answer

The practice of manually indexing foreign key columns. While relational databases enforce relational integrity constraints, many (like PostgreSQL and SQL Server) do **not** automatically index foreign keys, leading to poor `JOIN` performance and lock escalation during parent table updates.

Question 20

Skip Scan (Loose Index Scan)

Accepted Answer

An optimization technique where the engine skips non-matching values within a composite index key prefix to jump directly to target sub-keys, allowing queries to utilize composite indexes even when skipping initial index columns.

SQL Indexing, B-Trees & Query Optimization

Card Preview

Related Flashcard Sets

Organic Chemistry - Nucleophilic Substitution & Elimination Mechanisms

MIT 8.01 - Classical Mechanics & Newtonian Dynamics

French A1/A2 - Essential Daily Vocabulary & Grammar Foundations

Rust Systems Programming - Ownership, Lifetimes & Borrowing