Index Fundamentals and Data Structures

Database indexes function as specialized sorted data structures designed to accelerate data retrieval operations. In storage systems like MySQL, data persists physically on disk blocks. Without an index, locating a specific record requires a full table scan, sequentially traversing every disk page to find the target row—a process with O(N) complexity. An index creates a separate lookup structure holding the key value and a pointer to the physical location of the row. This allows the database engine to locate data with logarithmic time complexity O(log N), analogous to using a book's glossary to find a page number rather than reading every page.

Evolution of Indexing Structures

To understand MySQL indexing, one must examine the data structures that support it.

• Binary Search on Arrays: While efficient for static data, inserting into a sorted array requires shifting subsequent elements, resulting in high write overhead.
• Binary Search Trees (BST): BSTs allow faster insertion and lookup. However, in the worst-case scenario (e.g., inserting sorted data), a BST degenerates into a linked list with O(N) lookup time.
• Balanced Trees (AVL): To prevent skew, AVL trees maintain a balance factor, ensuring the depth difference between left and right subtrees never exceeds one. While solving the skew issue, strict balancing can still lead to high rotational costs during frequent updates.

MySQL primarily utilizes the B+Tree structure (a variation of the B-Tree) for its indexes. In a B+Tree, all data records are stored in the leaf nodes, while non-leaf nodes store only keys. This maximizes the number of keys per node, reducing the tree height and minimizing disk I/O. Furthermore, leaf nodes are linked via a linked list, optimizing range scans.

Index Classifications

In InnoDB, the default storage engine, indexes are categorized by their logical properties:

• Normal Index: The basic index type with no constraints on uniqueness.
• Unique Index: Enforces uniqueness on the key values. A Primary Key is a special type of unique index that also disallows NULL values.
• Fulltext Index: Designed for searching text content. It utilizes an inverted list structure to facilitate efficient keyword searches within large text fields (CHAR, VARCHAR, TEXT).

Code Example: Creating a Fulltext Index

CREATE TABLE content_archive (
    id INT AUTO_INCREMENT PRIMARY KEY,
    article_body TEXT,
    FULLTEXT KEY ft_idx_body (article_body)
) ENGINE=InnoDB;

SELECT * FROM content_archive 
WHERE MATCH(article_body) AGAINST('database performance' IN NATURAL LANGUAGE MODE);

Index Usage Principles and Strategies

1. Cardinality and Selectivity

Index efficiency correlates directly with column cardinality—the ratio of distinct values to total rows (COUNT(DISTINCT col) / COUNT(*)). High cardinality (e.g., UUID, ID) yields better filtering than low cardinality columns (e.g., Gender, Boolean). If the optimizer determines that scanning a large portion of the index is nearly as expensive as scanning the table, it may ignore the index.

2. Leftmost Prefix Matching

For composite indexes (indexes spanning multiple columns), the structure is sorted first by the leftmost column, then the next, and so on. An index on (surname, given_name) is sorted by surname. Therefore, queries can utilize the index only if they filter by surname, or surname and given_name. Filtering by given_name alone renders the index ineffective.

Code Example: Composite Index

-- Create composite index
ALTER TABLE users ADD INDEX idx_contact_info (surname, given_name, phone);

-- Effective: Uses the leftmost prefix
SELECT * FROM users WHERE surname = 'Smith';

-- Effective: Uses full prefix
SELECT * FROM users WHERE surname = 'Smith' AND given_name = 'John';

-- Ineffective: Skips the first column
SELECT * FROM users WHERE given_name = 'John';

3. Covering Indexes

A "table lookup" (or "ref lookup") occurs when a secondary index is used to find the Primary Key, followed by a lookup in the clustered index to retrieve non-indexed columns. A covering index occurs when all columns required by the query (SELECT and WHERE) are contained within the index itself. This eliminates the need for the second random I/O access.

Code Example: Covering Index

-- Query hits the index without accessing the data row
EXPLAIN SELECT surname, phone FROM users 
WHERE surname = 'Smith' AND given_name = 'John';
-- Extra output: Using index

4. Prefix Indexes

For long text columns (e.g., URLs, email addresses), indexing the entire value consumes significant disk space and I/O. A prefix index creates an index on the leading N characters. The length N should be chosen to maximize selectivity while minimizing size.

-- Calculate selectivity for different lengths
SELECT COUNT(DISTINCT LEFT(url, 10)) / COUNT(*) FROM page_data;

-- Create index based on optimal length
ALTER TABLE page_data ADD INDEX idx_url_prefix (url(12));

5. Index Condition Pushdown (ICP)

ICP is an optimization where the storage engine evaluates parts of the WHERE clause against the index before accessing the full table rows. Without ICP, the storage engine retrieves rows matching the index range and passes them to the Server layer for further filtering. With ICP, filtering happens at the engine level, significantly reducing I/O.

Scenario: Index on (last_name, first_name). Query: WHERE last_name = 'Smith' AND first_name LIKE '%John%'.

Without ICP, the engine fetches all rows where last_name = 'Smith' and returns them to the server. With ICP, the engine inspects the first_name in the index entry; if it does not contain 'John', the row is skipped entirely.

-- Enable ICP (default in modern versions)
SET optimizer_switch='index_condition_pushdown=on';

-- Check execution plan
EXPLAIN SELECT * FROM employees 
WHERE last_name = 'Smith' AND first_name LIKE '%John%';
-- Extra: Using index condition

Clustered vs. Non-Clustered Indexes

Clustered Index

In InnoDB, the Clustered Index is the table itself. The leaf nodes of the clustered index B+Tree contain the actual data rows.

• Structure: Typically defined via the Primary Key. If no PK exists, InnoDB selects a unique NOT NULL key. If none exists, it generates a hidden 6-byte row ID.
• Pros: Fast access to data via PK; excellent for range scans.
• Cons: Insertion speed depends on order (sequential is best). Updating the PK is expensive as it requires physically moving the row.

Non-Clustered (Secondary) Indexes

Secondary indexes in InnoDB store the indexed key value and the Primary Key value in their leaf nodes. To retrieve a row using a secondary index:

1. Search the secondary index B+Tree to find the Primary Key.
2. Search the clustered index B+Tree using the Primary Key to find the data row.

This two-step process is the "table lookup" or "bookmark lookup."

Index Creation Best Practices

• Target High-Impact Queries: Create indexes for columns frequently used in WHERE, JOIN, and ORDER BY clauses.
• Avoid Redundancy: More indexes increase maintenance overhead during INSERT, UPDATE, and DELETE operations.
• Cardinality Matters: Avoid indexing columns with very low distinctness (e.g., is_deleted flags).
• Composite Index Order: Place the most selective (highest cardinality) column first, and ensure queries respect the leftmost prefix rule.
• Optimize for I/O: Use shorter keys (prefix indexes) to fit more index entries in memory, reducing disk reads.
• Primary Key Selection: Use monotonically increasing values (like Auto Increment) for the Primary Key. Random values (like UUIDs) cause page fragmentation and splits, degrading insert performance.

Scenarios Where Indexes Are Ignored

The MySQL Cost-Based Optimizer (CBO) may decide not to use an index in the following cases:

• Functions on Columns: Applying functions to indexed columns prevents index usage.

  -- Avoid
  SELECT * FROM orders WHERE YEAR(created_at) = 2023;
  -- Use range scan instead
  SELECT * FROM orders WHERE created_at >= '2023-01-01';
  

• Implicit Type Conversion: Comparing a string column to a number forces a conversion that invalidates the index.

  -- Index on phone (varchar) is ignored
  SELECT * FROM users WHERE phone = 1234567890;
  

• Leading Wildcards: LIKE '%term' prevents index usage; LIKE 'term%' can use a range scan.
• Negative Queries: !=, <>, NOT IN, and NOT LIKE generally result in full scans unless the optimizer can transform the query efficiently.