MySQL索引数据访问时间复杂度及BTree插入策略问询

当然存在索引访问复杂度超过O(logn)甚至逼近O(n)的场景，你提到的有序插入导致BTree单侧生长就是最典型的情况之一，我来详细拆解这个问题：

一、哪些场景会让BTree索引性能退化到O(n)级别？ #

• 持续有序插入数据：比如用自增ID作为主键、或者批量插入按时间戳/固定递增规则排序的数据时，BTree会一直往同一侧（通常是右侧）的叶子节点添加数据。当节点满了就分裂出新节点，新节点继续接在同一侧，最终整个树会形成类似“链表”的结构——每个非叶子节点只有一个子节点。这时候不管是查询还是插入，都需要遍历几乎所有层级的节点，实际时间复杂度就会逼近O(n)。
• 极端数据倾斜的索引：如果某个索引列的取值重复度极高（比如90%以上的数据都是同一个值），或者只有极少数不同取值，BTree的分支结构几乎起不到筛选作用，查询时需要扫描绝大多数叶子节点，性能表现也会和O(n)的线性扫描差不多。

二、MySQL针对这类问题的处理策略 #

InnoDB引擎早就考虑到了这种情况，做了不少针对性优化：

• 自增主键的专属优化：对于自增主键的顺序插入，InnoDB会预分配叶子节点的空间，避免频繁的节点分裂。而且它可以直接定位到当前最右侧的叶子节点，不需要遍历整个树的层级。即使树的结构看起来是“单侧延伸”，但因为每个节点能存储大量键值（默认一个节点大小是16KB，能存上千个整数类型的主键），树的高度依然是log级别的，实际性能不会真的跌到O(n)。
• BTree的自动平衡机制：当BTree的不平衡程度达到阈值时，InnoDB会触发节点旋转与重新平衡操作。不过对于持续的有序插入，它不会每次插入都做平衡（那样会带来极高的开销），而是通过节点分裂的规则来控制树的高度——分裂出来的新节点会直接衔接在原节点的同侧，但因为每个节点的容量足够大，树的高度增长依然是缓慢的log级。
• 自适应哈希索引（Adaptive Hash Index）：InnoDB会自动对频繁访问的索引页建立哈希映射，对于热点的有序数据访问，哈希索引可以直接定位到目标数据页，把访问复杂度降到O(1)。这个优化是引擎自动完成的，不需要手动配置。
• 手动重建索引：如果是非自增的自定义索引出现了严重的单侧生长或碎片化，可以在业务低峰期执行OPTIMIZE TABLE 表名或者ALTER TABLE 表名 FORCE INDEX(索引名)来重建索引，让BTree恢复平衡。新版本MySQL支持Online DDL，执行时不会完全锁表，对业务影响更小。

最后补充一句：其实严格来说，即使是单侧生长的BTree，只要每个节点能存储多个键值，它的时间复杂度依然是O(log_k n)（k是每个节点的键值数量），只是k的大小会影响实际性能。只有当每个节点只能存1个键值时，才会真的退化成O(n)，而InnoDB的节点设计从根源上避免了这种极端情况。

内容的提问来源于stack exchange，提问作者Manouchehr Rasouli