InnoDB 存储引擎选择 B+树 作为其底层的索引数据结构，是经过对磁盘I/O特性、数据库查询模式（等值查询、范围查询）以及存储效率进行深度权衡后的必然结果。 要理解为什么选 B+树，最清晰的方法是看看为什么不选其他数据结构，以及 B+树到底解决了什么核心痛点。 --- 核心痛点：磁盘 I/O 非常慢 数据库的数据是存在磁盘上的。相比于内存，磁盘读取非常慢。操作系统和数据库引擎在读取磁盘时，为了提高效率，通常按“块”或“页（Page）”来读取（InnoDB 默认一页为 16KB）。 索引设计的终极目标就是：在查找数据时，尽量减少磁盘的 I/O 次数。 --- 第一轮淘汰赛：为什么不用 Hash、二叉树、红黑树？ 1. 哈希表（Hash Table） 优点：等值查询（，）极快，时间复杂度 $O(1)$。 致命缺点：不支持范围查询（，，）和排序。因为哈希计算后数据是无序散列的，而数据库中有大量的范围查询。 2. 二叉查找树（BST） / 红黑树（Red-Black Tree） 优点：支持等值查询和范围查询。 致命缺点：树太高了，导致磁盘 I/O 次数过多。这两种树每个节点最多只有 ...
播面