为什么添加索引后会提升数据库查询效率

1. 没有索引时

假设有一张用户表：

user -------------------------------- id name age 1 Tom 18 2 Jack 20 3 Lucy 22 ... 10000000 ...

执行：

SELECT * FROM user WHERE name = 'Lucy';

如果name没有索引：

数据库只能：

第一行 -> 第二行 -> 第三行 ...

逐条扫描。

这个过程叫：

全表扫描（Full Table Scan）

时间复杂度：

O(N)

1000万条数据：

最坏需要比较1000万次

同时会产生大量磁盘IO。

2. 添加索引后

例如：

CREATE INDEX idx_name ON user(name);

MySQL(InnoDB)默认采用：

B+Tree

结构类似：

root / \ A-H I-Z / \ Jack Lucy

查询：

SELECT * FROM user WHERE name='Lucy';

数据库会：

根节点 ↓ 中间节点 ↓ 叶子节点

直接定位到数据。

不需要扫描全部数据。

时间复杂度：

O(logN)

3. 为什么效率高

核心原因：

减少磁盘IO

数据库最耗时的不是CPU：

而是：

磁盘IO

例如：

CPU计算：纳秒级 内存访问：微秒级 磁盘访问：毫秒级

差距几千倍甚至几万倍。

B+Tree会把大量数据组织成：

多叉树

例如：

每个节点可存1000个key

1000万数据：

第一层：1000 第二层： 1000 × 1000 =100万 第三层： 1000 × 1000 × 1000 =10亿

也就是说：

1000万数据 只需要3层树

查询：

root ↓ middle ↓ leaf

仅需：

3次磁盘IO

即可定位。

4. 为什么MySQL不用红黑树

很多面试官会追问。

红黑树：

O(logN)

看起来一样。

但是：

1000万数据

红黑树高度：

log₂(10000000) ≈ 24

需要：

24次磁盘IO

而B+Tree：

3~4次IO

即可完成查询。

所以数据库选择：

B+Tree

而不是：

红黑树

5. 为什么不用Hash索引

Hash结构：

Tom -> hash1 Lucy -> hash2 Jack -> hash3

等值查询：

where name='Lucy'

非常快：

O(1)

但是：

where age > 20 where age between 20 and 30 order by age

无法利用Hash索引。

而B+Tree支持：

• 等值查询
• 范围查询
• 排序
• 分组
• 最左前缀匹配

因此MySQL默认选择B+Tree。

6. 为什么B+Tree比B树更适合数据库

B树：

数据分散在所有节点

B+Tree：

数据全部放叶子节点

并且：

叶子节点双向链表连接

1 -> 2 -> 3 -> 4 -> 5

所以范围查询：

where age between 20 and 30

只需要：

找到20 ↓ 顺着叶子链表扫描到30

效率极高。

面试标准回答

索引能够提升查询效率，本质原因是利用B+Tree数据结构将原来的全表扫描从O(N)降低为O(logN)。
没有索引时数据库需要逐行扫描数据，而建立索引后可以通过B+Tree快速定位目标记录。
同时B+Tree是一种多路平衡查找树，树高很低，千万级数据通常只需要3~4层，因此查询只需3~4次磁盘IO即可完成，大幅减少磁盘访问次数。
此外B+Tree叶子节点通过链表连接，天然支持范围查询、排序和最左前缀匹配，这也是MySQL InnoDB采用B+Tree作为默认索引结构的主要原因