在 MySQL 中，你很难找到一个直接被称作“二叉查找树”的物理索引结构。MySQL 的默认存储引擎 InnoDB 使用的是B+ 树，而非二叉查找树（Binary Search Tree, BST）。不过，二叉查找树是理解所有树状索引的基础，MySQL 的索引演化也是从二叉查找树的思想出发，逐步改进到多路平衡树。因此，本回答将从二叉查找树的核心原理讲起，分析它为何无法胜任数据库索引，再展开 MySQL 最终采用的 B+ 树，以及二叉查找树变体在 MySQL 内部可能的存在形式。
🌳 一、二叉查找树（BST）的本质
二叉查找树是一种有序的二叉树，每个节点包含一个键，并且满足：
- 左子树上所有节点的键值小于其根节点的键值。
- 右子树上所有节点的键值大于其根节点的键值。
查找效率：平均 O(log N)，最坏 O(N)（退化成链表时）。
动态更新：插入和删除也保持相同的复杂度。
例如，对于序列 [4, 2, 6, 1, 3, 5, 7]，构建的 BST 如下：
4 / \ 2 6 / \ / \ 1 3 5 7查找 5 只需 3 次比较。
❌ 二、为什么数据库不用二叉查找树？
尽管 BST 在内存中表现良好，但数据库存储在海量磁盘上，瓶颈完全不同。
1. 磁盘 I/O 次数与树高成正比
数据库索引通常存储在磁盘上，每次节点访问需要一次磁盘 I/O。二叉树的高度随数据量 N 呈对数增长，最坏可能退化为线性高度。假设 100 万行数据，平衡 BST 高度约 20，最坏情况 100
