1.9 MySQL Index Implementation

1. Underlying Index Implementation

• In the InnoDB storage engine, each index corresponds to a B+ tree.

2. Why Use a B+ Tree

First, think about why a tree structure is used instead of an array or linked list.

2.1. Why a Tree

• An array has fast lookup, O(1), but insert/delete efficiency is low, O(n).
• A linked list has fast insert/delete, O(1), but slow lookup, O(n).
• A hash table has O(1) access efficiency, but does not support range lookup.
• A tree combines characteristics of arrays and linked lists and makes a trade-off between lookup and insert/delete efficiency, which suits databases where lookup and modification are frequent.

2.2. Why a B-Tree Instead of a Balanced Binary Tree

• B Tree.md

2.3. Why a B+ Tree Instead of a B-Tree

• B Tree.md

2.4. Summary

First, array VS linked list VS hash table VS tree. Then binary search tree VS B-tree family. The former is an in-memory tree and needs all data to be loaded into memory to achieve O(log n) efficiency, but database data is very large, so this is impossible. We can only read data in batches. According to the principle of spatial locality in disk I/O, several blocks are read at once. We need a tree that can read a large amount of data at once. Then B-tree VS B+ tree. The former stores data in every node in addition to keys, which is unfavorable for reading more keys at once for filtering. The latter stores data at the final level, and the leaf level is linked, making range lookup convenient.

3. InnoDB and MyISAM Indexes

InnoDB and MyISAM Index Comparison.md

4. References

• Discussing B/B+ Trees from MongoDB and MySQL - CSDN