B+ 树索引

为什么是 B+ 树而不是哈希或红黑树

B+ 树的设计目标是最小化磁盘 I/O 次数。树的每个节点大小与操作系统页大小对齐（通常 16KB），一次 I/O 读取一整页，所以每次读磁盘能处理的数据量远大于内存中的二叉树节点。典型的 B+ 树高度只有 3-4 层，一亿行数据只需 3 次 I/O 即可完成查找。

哈希索引等值查询更快（O(1) vs O(log n)），但完全不支持范围查询（BETWEEN、ORDER BY、>）。红黑树高度比 B+ 树高得多，内存中表现好，但每次访问新节点都是一次随机 I/O，在磁盘场景下远不如 B+ 树。[1]

B 树（Rudolf Bayer，1970 年）的内部节点也存储数据记录；B+ 树将所有数据记录都放在叶节点，内部节点只存储键值用于路由。B+ 树的优势在于：叶节点构成有序双向链表，范围查询只需找到起始叶节点然后顺序扫描，极其高效；同样大小的节点能放更多键值，树更矮，查找路径更短。

MySQL InnoDB 的 B+ 树叶节点大小默认 16KB，单个叶节点可以存储约 1000 个键值。MySQL 8.0 起支持降序索引（CREATE INDEX idx ON t(col DESC)），让 ORDER BY col DESC 不再需要额外排序步骤。