Purpose of Indexing

Indexing employs data structures to accelerate record retrieval, analogous to a book's table of contents. Instead of scanning all entries, the engine checks if query conditions match an index, using it to locate relevant data efficiently. Without an index, a full table scan becomes necessary, examining each record sequentially.

For a column value_col with an index, a binary search tree is maintained on disk. Each node stores a (key, pointer) pair: key is value_col's value, pointer references the row's disk address. For example, a root node might be (34, 0x07). Searching for value_col=89 traverses the tree: compare 89>34, move right to 89, match found. The pointer then retrieves the row. This reduces disk I/O, boosting query speed.

Index Characteristics: Benefits and Drawbacks

Overview

MySQL defines an index as a data structure aiding efficient data retrieval. Essentially, it's an ordered structure enabling advanced search algorithms to locate data faster.

Advantages

• Reduced I/O: Like library catalogs, indexes minimize database read operations.
• Uniqueness Enforcement: Unique indexes ensure row uniqueness.
• Join Acceleration: Speeds up parenet-child table joins via reference integrity.
• Group/Sort Efficiency: Cuts time for grouped/sorted queries by reducing CPU load.

Disadvantages

• Maintenance Overhead: Index creation and updates consume time, scaling with data volume.
• Storage Consumption: Each index occupies disk space, potentially exceeding data file size.
• Write Performance Impact: Inserts/updates/deletes require index maintenance, slowing write operations.

InnoDB Index Evolution

Pre-Index Lookup Mechanisms

SELECT [columns] FROM sample_table WHERE column = x;

Single Page Lookup

With few records in one page:

• Primary Key Search: Use page directory's binary search to find the slot, then traverse the group.
• Non-Primary Key Search: Traverse the single linked list sequentially (inefficient).

Multi-Page Lookup

For large datasets across pages:

1. Locate the target page.
2. Search within the page. Without indexes, traverse the doubly linked list of pages, checking each sequentially—highly inefficient.

B+ Tree Design Iterations

Initial Table Setup

CREATE TABLE sample_table(
    id INT,
    value INT,
    flag CHAR(1),
    PRIMARY KEY(id)
) ROW_FORMAT = Compact;

Simplified row format includes: record_type (0=normal, 1=directory, 2=min, 3=max), next_record (offset), column values, and metadata.

Iteration 1: Directory Record Pages

Create a directory mapping page numbers to their minimum primary keys. Store directory items in a dedicated page (e.g., page 30), with record_type=1. Search steps:

1. Binary search directory page 30 for key range.
2. Access target page (e.g., page 9) and locate the record.

Iteration 2: Multiple Directory Pages

When a directory page fills (e.g., page 30 holds 4 items), split into new pages (e.g., page 32 for new directories). Search now involves:

1. Identify relevant directory page (e.g., page 30 for keys <320).
2. Locate target directory item.
3. Access user record page.

Iteration 3: Directory of Directories

Introduce a higher-level directory page (e.g., page 33) managing directory pages (30, 32). This forms a B+ tree: leaf nodes store user records, non-leaf nodes store directory items.

B+ Tree Structure

• Leaf Nodes: Store complete user records (all columns, including hidden ones).
• Non-Leaf Nodes: Store index columns + child page pointers.
• Height: Typically 2-4 levels. With 16KB pages, 3 levels can index ~1 billion records (1000 items/page × 1000 pages/level × 100 records/leaf page).

Index Types in InnoDB

Clustered Index

Stores data in leaf nodes ("index-is-data"). Sorts records by primary key:

• Page-Level: Records sorted in a singly linked list.
• Page Order: Pages sorted in a doubly linked list by primary key.
• Advantages: Faster data access, efficient primary key sorting/ranges.
• Disadvantages: Insert order dependency (auto-increment IDs preferred), high update cost for primary keys, secondary index lookups require two tree traversals.
• Limitations: One per table (default: primary key; else unique non-null column; else implicit 6-byte ID).

Secondary Index (Non-Clustered)

Built on non-primary columns (e.g., value_col). Leaf nodes store primary keys, requiring a "bookmark lookup" to fetch full records. Multiple secondary indexes allowed.

Composite Index

Multi-column index (e.g., (value_col, flag_col)). Sorts first by value_col, then flag_col within equal value_col groups. More efficient than separate indexes.

InnoDB B+ Tree Notes

• Root Page Stability: Root node page number remains fixed post-creation; splits promote root to directory page.
• Unique Directory Entries: Secondary index directory items include (index value, primary key, page number) to avoid ambiguity.
• Minimum Page Capacity: Each page holds ≥2 records to maintain tree balance.

MyISAM Indexing

Uses B+ trees with leaf nodes storing data record addresses (non-clustered). Data and index files are separate. Lacks adaptive hash indexes but supports spatial indexes.

Index Costs

• Space: Each index is a B+ tree (pages × 16KB).
• Time: Write operations trigger tree maintenance (splits, merges).

Data Structure Selection Rationale

Hash vs. B+ Tree

• Hash: O(1) for equality, poor for ranges/sorting/partial matches.
• B+ Tree: O(log n) for all operations, supports ranges/sorting/composites. Preferred for most cases; InnoDB uses adaptive hash indexes for hot data.

Tree Variants

• Binary Search Tree: High height → more I/O.
• AVL Tree: Balanced but still tall for large datasets.
• B-Tree: Multi-way branching reduces height. Internal nodes store keys + child pointers.
• B+ Tree: Optimized for databases—leaf nodes link sequentially, internal nodes store only keys/pointers.

InnoDB Storage Structure

Pages

• Unit: 16KB (default), basic I/O unit.
• Structure: File Header (38B), Page Header (56B), Infimum/Supremum Records, User Records, Free Space, Page Directory, File Trailer (8B).
• Page Directory: Uses slots (group max record offsets) for binary search within pages.

Extents, Segments, Tablespaces

• Extent: 64 contiguous pages (1MB), reduces random I/O for range scans.
• Segment: Collection of extents (e.g., leaf/non-leaf segments for indexes).
• Tablespace: Logical container for segments (system, user, undo, temporary).

Row Formats

• COMPACT: Variable-length fields store lengths in reverse order; NULL values marked in a bitmap.
• DYNAMIC/COMPRESSED: Handle overflow via off-page storage (20B pointers to external pages).

Index Creation Guidelines

When to Create Indexes

• Columns with uniqueness constraints (unique/primary keys).
• Frequent WHERE/GROUP BY/ORDER BY/DISTINCT clauses.
• JOIN columns (consistent types across tables).
• Low-cardinality columns (avoid, e.g., gender).
• Small tables (<1000 rows, often no index needed).

Best Practices

• Limit indexes per table (≤6).
• Perfer shorter data types for keys (e.g., INT over BIGINT).
• Use prefix indexes for long strings (balance length vs. selectivity).
• Avoid redundant/duplicate indexes (e.g., separate indexes on same column).
• Order composite indexes by frequency (leftmost prefix rule).

Index Types

• Single-Colum: On one field (e.g., INDEX (value_col)).
• Composite: On multiple fields (e.g., INDEX (value_col, flag_col)).
• Unique: Enforces uniqueness (UNIQUE INDEX (email_col)).
• Full-Text: For text search (FULLTEXT INDEX (content_col)).

Creation Syntax

-- Create table with index
CREATE TABLE sample_table(
    id INT PRIMARY KEY,
    value INT,
    INDEX idx_value (value)
);

-- Add index to existing table
ALTER TABLE sample_table ADD INDEX idx_value (value);
CREATE INDEX idx_value ON sample_table(value);

-- Drop index
ALTER TABLE sample_table DROP INDEX idx_value;
DROP INDEX idx_value ON sample_table;

MySQL 8.0 Features

• Descending Indexes: Explicit sort order (e.g., INDEX (a ASC, b DESC)).
• Invisible Indexes: Temporarily disable indexes for testing (ALTER TABLE t ALTER INDEX i INVISIBLE;).

// Example: Array vs. HashSet search efficiency
import java.util.*;

public class SearchComparison {
    public static void arraySearchTest() {
        int[] numbers = new int[100000];
        for (int i = 0; i < numbers.length; i++) numbers[i] = i + 1;
        long start = System.currentTimeMillis();
        for (int j = 1; j <= 100000; j++) {
            for (int num : numbers) if (num == j) break;
        }
        System.out.println("Array search time: " + (System.currentTimeMillis() - start) + "ms");
    }

    public static void hashSetSearchTest() {
        Set<Integer> hashSet = new HashSet<>();
        for (int i = 0; i < 100000; i++) hashSet.add(i + 1);
        long start = System.currentTimeMillis();
        for (int j = 1; j <= 100000; j++) hashSet.contains(j);
        System.out.println("HashSet search time: " + (System.currentTimeMillis() - start) + "ms");
    }

    public static void main(String[] args) {
        arraySearchTest();      // ~800ms
        hashSetSearchTest();    // ~5ms
    }
}