Indexes are specialized data structures maintained on disk and in memory that allow the database engine to locate records in $O(log N)$ or $O(1)$ time rather than performing costly $O(N)$ full table scans.
In MySQL, the two most fundamental index data structures are B-Tree (specifically B+Tree) and Hash Indexes. Choosing and optimizing indexes requires understanding their low-level mechanics.
1. B+Tree Indexes: The Relational Workhorse
In MySQL InnoDB, all standard indexes are implemented as B+Trees (a variation of the balanced B-Tree):
Balanced Tree Height: The tree is balanced; every path from root to leaf has identical depth (typically 3 to 4 levels even for tens of millions of rows).
Internal Nodes: Store key search pointers only (maximizing branching factor).
Leaf Nodes: Store actual data or row pointers, and are linked together via bi-directional doubly linked lists.
1 [ Root Node ]
2 / [ Branch ] [ Branch ]
3 / / [Leaf]<--->[Leaf]<--->[Leaf]<--->[Leaf]
4 │ │ │ │
5 (Doubly-linked leaves allow blazing fast range scans!)
Why B+Trees Dominate RDBMS Storage:
Point Lookups: $O(log N)$ lookup time.
Range Queries: Blazing fast for BETWEEN, >, <, and LIKE 'prefix%' because leaf nodes are sequentially linked.
Sorting: Pre-sorted leaf nodes eliminate the need for in-memory sorting (filesort) during ORDER BY.
2. Hash Indexes: Instant $O(1)$ Point Lookups
Hash indexes use an internal hash table where key values are passed through a hash function to compute a direct memory bucket address:
Unbeatable $O(1)$ search performance for exact equality matches (= or <=>).
Fatal Weaknesses for General SQL:
Zero Range Scan Capability: Because hash codes randomize order, hash indexes cannot be used for <, >, BETWEEN, or ORDER BY.
Cannot Match Partial Prefixes: You cannot search on the first 3 characters of a string.
InnoDB's Secret Weapon: The Adaptive Hash Index (AHI)
MySQL InnoDB does not permit users to create manual Hash indexes directly. Instead, InnoDB includes an internal feature called the Adaptive Hash Index (AHI):
InnoDB monitors B+Tree index searches in real-time.
If it notices certain index pages are queried repeatedly with equality lookups, it automatically builds a Hash index in memory on top of the B+Tree buffer pool!
This gives developers the best of both worlds: B+Tree versatility on disk with Hash index speed in memory!
1-- Check Adaptive Hash Index status
2SHOWGLOBALSTATUSLIKE'Innodb_adaptive_hash%';
3
4-- Toggle AHI in MySQL configuration
5SETGLOBAL innodb_adaptive_hash_index =ON;
Structural Comparison
Feature
B+Tree Index
Hash Index
Equality Lookups (=)
Excellent: $O(log N)$
Instant: $O(1)$
Range Queries (<, >, BETWEEN)
Supported natively
Completely unsupported
Sorting (ORDER BY)
Pre-sorted on leaf nodes
Requires full filesort
Prefix Matching (LIKE 'abc%')
Supported
Unsupported
MySQL Engine Support
InnoDB, MyISAM, MEMORY
MEMORY engine only
Interactive Quiz• Knowledge Check
Multiple Choice Questions
Question 1
What type of tree structure does MySQL InnoDB use for its primary and secondary indexes?
Question 2
Why are B+Trees superior to Hash Indexes for standard relational queries?
Question 3
What is the time complexity of an exact equality lookup in a Hash Index?
Question 4
What is the InnoDB Adaptive Hash Index (AHI)?
Question 5
Can a B+Tree index accelerate a query filtering with LIKE '%term'?
Next Lesson
Clustered vs Secondary Indexes in MySQL InnoDB
Continue learning with hands-on practice, examples, and exercises in the upcoming topic.