NOTE
MySQL Index Implementation
B+tree organization, clustered and secondary indexes, page locality, and lookup complexity.
This is a historical learning note and may contain outdated or incomplete understanding.
InnoDB’s common indexes are B+trees organized in pages. Internal nodes guide searches; leaf pages contain ordered entries and are linked for range traversal. High fan-out keeps tree height small for large datasets.
The clustered index stores rows at primary-key leaves, while secondary-index leaves reference primary-key values. Real lookup cost depends on cache locality, page reads, selectivity, covering behavior, and whether a secondary lookup must return to the clustered tree.