Part 1: MySQL 9 InnoDB Internals: B+Tree Indexes, Composite Keys & EXPLAIN Profiling

1. InnoDB Storage Engine Anatomy: Clustered vs. Secondary Indexes

Unlike MyISAM or heap tables that store rows in unorganized heap files and point to them via row IDs, InnoDB is an index-organized storage engine. In InnoDB, the table is the index:

• Clustered Index: Every InnoDB table has exactly one clustered index, strictly keyed by the Primary Key. The leaf nodes of the clustered B+Tree do not store pointers; they store the complete, actual physical row data (columns, MVCC roll pointers, transaction IDs).
• Secondary Indexes: All additional indexes created on non-primary columns (e.g. INDEX(email) or INDEX(status, created_at)) are secondary indexes. The leaf nodes of a secondary index do not contain raw row data; they store only the indexed column values plus the matching row's Primary Key.

2. B+Tree Mechanics: Fan-Out, Page Splitting & Depth

InnoDB arranges disk storage in 16KB pages. In a B+Tree, internal non-leaf nodes contain navigation keys and 6-byte page pointers. Because a 16KB page can hold hundreds of keys, the fan-out factor is exceptionally high:

// Capacity Calculation for 16KB InnoDB Pages:
Average Key + Pointer Size: ~16 bytes
Fan-out per page: 16,384 bytes / 16 bytes ≈ 1,000 pointers

B+Tree Height 1 (Root only): ~1,000 rows
B+Tree Height 2 (Root + 1 Level): ~1,000 * 1,000 = 1,000,000 rows
B+Tree Height 3 (Root + 2 Levels): ~1,000 * 1,000 * 1,000 = 1,000,000,000 rows!

Even in a table with hundreds of millions of rows, InnoDB locates any row by Primary Key in only 3 to 4 disk page lookups. If those pages are cached in the InnoDB Buffer Pool in RAM, query latency is measured in microseconds!

The Dangers of Random Primary Keys (UUIDv4): When sequential auto-incrementing integers or ULIDs are used as primary keys, new rows are appended predictably to the end of pages, keeping page fill factor at a healthy ~93%. However, inserting random 36-character UUIDv4 strings forces MySQL to insert data in the middle of existing pages, causing catastrophic Page Splitting, memory fragmentation, and massive write amplification.

3. The Leftmost Prefix Rule in Composite Indexes

A composite index spans multiple columns, such as INDEX(status, created_at, user_id). MySQL sorts the index entries hierarchically: first by status; then for identical status values, by created_at; then for identical timestamps, by user_id.

Under the Leftmost Prefix Rule, MySQL can only use the index if the query filters include columns starting from the leftmost position without gaps:

-- Given: INDEX idx_status_date_user (status, created_at, user_id)

-- 1. FULL INDEX USAGE: Uses all 3 columns
SELECT * FROM orders WHERE status = 'shipped' AND created_at >= '2026-01-01' AND user_id = 42;

-- 2. PARTIAL INDEX USAGE: Uses status and created_at
SELECT * FROM orders WHERE status = 'shipped' AND created_at >= '2026-01-01';

-- 3. MINIMAL INDEX USAGE: Uses status only
SELECT * FROM orders WHERE status = 'shipped';

-- 4. CANNOT USE INDEX! Leftmost column (status) is omitted:
SELECT * FROM orders WHERE created_at >= '2026-01-01' AND user_id = 42;
-- Result: Full Table Scan (ALL), disastrous for 10M rows!

4. Multi-Valued Indexes on JSON Arrays in MySQL 9

Modern backend applications frequently store polymorphic attributes or tag sets inside JSON columns (e.g. {"tags": ["php", "laravel", "database"]}). In older database versions, querying whether a JSON array contained a specific element required a full table scan.

MySQL 9 supports Multi-Valued Indexes defined directly on JSON arrays:

-- Creating a Multi-Valued Index on a JSON Array column
ALTER TABLE blogs ADD INDEX idx_json_tags ( (CAST(attributes->'$.tags' AS CHAR(32) ARRAY)) );

-- High-speed index lookup using MEMBER OF()
EXPLAIN ANALYZE
SELECT id, title FROM blogs
WHERE 'laravel' MEMBER OF(attributes->'$.tags');

5. Modern Profiling with EXPLAIN (ANALYZE, FORMAT=TREE)

Legacy EXPLAIN tables only showed static cost estimates. MySQL 9 introduces deep runtime instrumentation with EXPLAIN ANALYZE, actually executing the query and outputting the real execution tree with microsecond timing and row counts:

EXPLAIN ANALYZE
SELECT id, title, published_at
FROM blogs
WHERE series_id = 15 AND is_free = 1
ORDER BY published_at DESC
LIMIT 10;

-> Limit: 10 row(s) (actual time=0.038..0.042 rows=10 loops=1)
    -> Index scan on blogs using idx_series_free_date (reverse)
       (cost=1.25 rows=10) (actual time=0.036..0.040 rows=10 loops=1)

Observe the output: actual time=0.038ms and Index scan ... (reverse). Because our composite index matches both the WHERE clauses and the ORDER BY clause, MySQL executes zero sorting passes in memory (Using filesort is completely eliminated).

6. Index Merge Optimization: Why Composite Indexes Win

When a query contains multiple WHERE conditions on columns that each possess standalone single-column indexes, MySQL attempts to use Index Merge (displayed in EXPLAIN as type: index_merge, Extra: Using intersect(...)).

While Index Merge is better than a full table scan, it incurs substantial CPU overhead because MySQL must traverse two separate B+Trees, load the row ID bitmaps into memory, calculate bitwise intersections or unions, and then perform clustered index lookups. Replacing multiple single-column indexes with one properly ordered composite index reduces execution time by up to 80% because all criteria are evaluated during a single tree traversal!

7. Native Descending Indexes in MySQL 9

In applications displaying paginated activity streams or chronological audit logs, queries frequently sort in descending order (ORDER BY created_at DESC). In MySQL 5.7 and older engines, indexes were always stored in ascending order; reading them in reverse required backward index scans, which are significantly slower due to InnoDB page pointer layout.

MySQL 9 fully supports Descending Indexes:

-- Optimize reverse pagination with mixed sort orders:
CREATE INDEX idx_user_activity ON activity_logs (user_id ASC, created_at DESC);

-- Executes with zero filesort and optimal forward B+Tree traversal!
SELECT id, action, created_at
FROM activity_logs
WHERE user_id = 100
ORDER BY created_at DESC
LIMIT 20;

8. Invisible Indexes: Zero-Downtime Schema Evolution

Over years of feature development, databases accumulate unused or redundant indexes. Every index degrades write throughput because InnoDB must maintain every secondary B+Tree on every write.

However, dropping an index in production is risky: if an undocumented reporting query relied on it, dropping it causes an instant query stall. MySQL 9 provides Invisible Indexes:

-- Hide index from query optimizer without dropping the data:
ALTER TABLE blogs ALTER INDEX idx_old_legacy INVISIBLE;

-- If no slow queries are flagged in Prometheus/Grafana over 7 days:
ALTER TABLE blogs DROP INDEX idx_old_legacy;

9. Prefix Indexing & UTF8MB4 Key Length Budgeting

In MySQL 9 running in strict utf8mb4 mode, each character requires up to 4 bytes in memory. The maximum permitted key length for an InnoDB secondary index on dynamic format tables is 3,072 bytes. Creating a composite index across several VARCHAR(255) columns (255 * 4 = 1,020 bytes per column) can quickly exceed the 3,072-byte ceiling!

To optimize index memory density, backend engineers employ Prefix Indexing:

-- Index only the first 64 characters of long slug or URL columns:
CREATE INDEX idx_article_slug_prefix ON blogs (slug(64));

-- Or create a deterministic generated SHA-256 hash column for exact equality lookups:
ALTER TABLE webhook_events
ADD COLUMN payload_hash BINARY(32) GENERATED ALWAYS AS (UNHEX(SHA2(payload, 256))) STORED,
ADD INDEX idx_payload_hash (payload_hash);

10. The InnoDB Adaptive Hash Index (AHI)

While B+Trees provide logarithmic search complexity O(log N), hash tables deliver constant time O(1) lookups. To accelerate lookups on heavily queried B+Tree pages, the InnoDB storage engine includes an internal self-tuning monitor called the Adaptive Hash Index (AHI).

When InnoDB notices that certain B+Tree pages in the Buffer Pool are accessed repeatedly with the exact same search pattern, it automatically builds an in-memory hash index mapping key values directly to memory page buffers. This allows frequently read rows (such as session tokens or platform settings) to be served in nanoseconds with zero B+Tree traversal!