SQL数据库选择B树作为主流索引结构，核心是为了适配磁盘存储特性和查询性能需求，在查询效率、存储成本、维护成本之间找到最优平衡。B树是一种多路平衡查找树，它的设计从根源上解决了传统索引结构的多个性能痛点。
B树索引的核心设计特性
B树索引的结构设计围绕减少磁盘IO次数展开，主要有以下几个关键特点：
- 多路分支降低树高度：和二叉树每个节点最多两个子节点不同，B树的每个节点可以存储多个关键字和对应子节点指针，通常一个节点的大小会和磁盘页大小对齐，比如16KB，这样树的高度可以控制在很低的范围，一般3到4层就能存储千万级甚至亿级的数据量。
- 平衡树结构保证查询稳定：B树是严格平衡的，所有叶子节点的深度相同，不管查询哪个关键字，需要的磁盘IO次数基本一致，不会出现极端情况下查询性能骤降的问题。
- 支持范围查询高效执行：B树的叶子节点之间通过指针有序连接，范围查询时不需要回溯上层节点，只需要找到起始关键字后顺着叶子节点链表遍历即可，非常适合SQL中常见的范围查询场景。
对比其他结构的优势
我们可以对比其他常见的数据结构，来看B树索引的适配性：
| 数据结构 | 树高度 | 范围查询效率 | 磁盘IO适配性 |
|---|---|---|---|
| 二叉树 | 非常高，存储大量数据时高度可达几十层 | 需要中序遍历，效率较低 | 差，每个节点数据量小，IO次数多 |
| 哈希表 | 无树结构 | 不支持，只能做等值查询 | 一般，等值查询快但场景受限 |
| B树索引 | 很低，通常3-4层 | 高效，叶子节点有序链表支持 | 好，节点大小和磁盘页对齐 |
B树索引的工作示例
我们以MySQL的InnoDB引擎为例，查看B树索引的查询逻辑，假设我们有一张用户表，在id字段上建立了B树索引：
-- 创建用户表，id为主键，自动建立B树索引
CREATE TABLE user (
id INT PRIMARY KEY,
name VARCHAR(50),
age INT
) ENGINE=InnoDB;
-- 插入测试数据
INSERT INTO user VALUES (1, '张三', 20);
INSERT INTO user VALUES (5, '李四', 25);
INSERT INTO user VALUES (3, '王五', 22);
INSERT INTO user VALUES (8, '赵六', 28);
INSERT INTO user VALUES (6, '孙七', 24);
-- 执行范围查询，利用B树索引的有序性
SELECT * FROM user WHERE id BETWEEN 3 AND 6;
上述查询的执行过程是：先从B树的根节点开始，找到id=3所在的叶子节点，然后顺着叶子节点的有序指针向后遍历，直到遇到id大于6的节点为止，整个过程只需要很少的磁盘IO就能完成。
B树索引的维护成本优势
除了查询性能，B树索引的维护成本也更低。当数据发生插入、删除、更新时，B树会通过节点的分裂、合并操作来维持平衡，不需要对整个索引结构进行大规模调整，维护过程的时间复杂度是O(log n)，即使数据量很大，索引的维护也不会对数据库性能造成太大影响。
另外B树索引的关键字是有序存储的，除了支持等值查询和范围查询，还可以支持ORDER BY、GROUP BY等排序相关的操作，很多时候可以避免额外的排序开销，进一步提升SQL语句的执行效率。