SQLite 的 B-Tree 是怎么让查询变快的？大一也能看懂数据库索引原理

你八成用过 SQLite,只是自己没意识到:微信的聊天记录、浏览器的 Cookie、手机上不少 App 的本地数据,底下都是它。数据库课上老师会讲 B-Tree、讲索引,但大多数人第一次真正体会到「索引」俩字的分量,是在一个百万行的表上没建索引、查询卡了十几秒,然后加了条 CREATE INDEX,同样的查询变成几毫秒。

十几秒到几毫秒,上千倍的差距,中间没有任何魔法,只有一种叫 B-Tree 的数据结构在干活。这篇文章就把它讲明白——不堆数学公式,用你能用上的方式讲。看完你会知道:为什么有序比无序快得多、为什么 B-Tree 偏偏选「胖矮」的树形、以及怎么用 EXPLAIN QUERY PLAN 亲手验证索引有没有生效。

适合人群:学过一点 SQL(哪怕只会 SELECT),对「为什么快」好奇的大一大二同学 你需要:能跑 sqlite3 命令就行,装 Python 就自带

一、先搞懂问题:没有索引时,查询在干什么?#

先建立一个直觉:数据库查询慢,慢在哪。

假设有一张 100 万行的用户表,你执行:

1
SELECT * FROM users WHERE username = 'zhang3';

如果 username 这一列上没有索引,SQLite 只有一条路可走:把整张表从头到尾扫一遍,每读一行就问一次「这行的 username 等于 zhang3 吗?」直到扫完。这种操作叫全表扫描(Full Table Scan)。

听起来很笨,但你想想:数据在磁盘上本来就是一串无差别的行,查询条件又只匹配其中一行,不逐行看一遍,它怎么知道哪行是你想要的?这就好比老师点名,全班名单没排序时,只能从第一页翻到最后一页找人。

全表扫描的时间复杂度是 O(N),数据翻一倍,查询时间跟着翻一倍。几十行无所谓,百万行、千万行时就是灾难。而且磁盘 I/O 很贵——它不是从内存拿数据那种纳秒级的速度,每读一块数据都是实打实的耗时。

要快,思路其实很朴素:别把所有数据都翻一遍,先想办法快速缩小范围。这就要请出索引了。

二、从有序性说起:二分查找为什么快#

在讲 B-Tree 之前,先想想一个生活经验:字典为什么能快速查到字?

因为字典是按拼音排序的。查「程」字你不会从 a 翻到 z,而是直接翻到中间偏后的位置,再看一眼决定往前还是往后。这就是二分查找:每翻一次,剩余候选直接砍掉一半。

对比一下就很直观:

查找方式	100 万条数据大约要看的次数	前提条件
逐个翻(全表扫描)	约 100 万次	无
二分查找	约 20 次	数据必须有序

100 万除以 2,除 20 次就只剩 1 条了——这就是有序的威力,20 万倍和 20 次的差距。

但数组上的二分查找有个致命麻烦:插入太痛苦。往有序数组中间插一个元素,后面的元素全部要后移一位。数据库是又要查、又要频繁写的,纯数组方案撑不住。

链表呢?插入方便了,但链表没法二分——它不支持「跳到中间」。所以问题变成:能不能有一种结构,既保持有序、又方便插入删除、还能快速定位? B-Tree 就是对这个问题最经典的回答。

三、B-Tree:一棵被刻意养「胖」的树#

B-Tree 的思路:把数据组织成一棵多叉的、按块组织的树。它有两个关键设定,缺一不可。

第一,按「页(Page)」存取,一个节点就是一页。

数据库和磁盘打交道,不是按字节抠,而是按块读——SQLite 默认一页 4KB。所以 B-Tree 的每个节点就设计成正好一页大小:一次磁盘 I/O,读回一整个节点,里面的几百个键一次性拿到内存,再在内存里比较,几乎不花时间。

第二,一个节点里放很多键,所以树特别「胖」、特别矮。

每个节点内部是一小段有序的键,中间夹着指向下一层的指针。一个 4KB 的页,装几百个键毫无压力。粗算一下,一个节点分出几百叉,三层结构就能覆盖几亿行数据:

第 1 层(根节点):1 页,几百个分支
第 2 层:几百页,每页又分几百个分支
第 3 层(叶子):几百万页,每页装着实际数据

于是查找任何一条数据,磁盘 I/O 次数 = 树的高度 ≈ 3 次。对比全表扫描几十万次的 I/O,这就是「十几秒变几毫秒」的全部秘密:不是算得更快了,而是跳过去的次数多了。分层查找在数据量大时碾压线性遍历,说的就是这种场景。

顺便一提,「数据库索引为什么用 B-Tree 而不是二叉搜索树」的答案就藏在这里:二叉树每个节点只有 2 叉,100 万行数据树高约 20 层,也就是 20 次磁盘 I/O;B-Tree 三层搞定。矮胖永远比瘦高省磁盘,磁盘 I/O 次数才是数据库真正的命门。

四、一次查找 + 一次插入,到底发生了什么#

光有结构还不够,B-Tree 能长期保持高效,靠的是一套自维护机制。挑两件最核心的说。

查找:从根节点开始,拿目标键和节点内的键比一比,决定走哪个分支,落到下一层再比,重复到叶子。整个过程像在商场找店:先看楼层索引图锁定楼层,再看楼层导览锁定位置,两次指路就到位,不需要把每层每个店都逛一遍。

插入与分裂:新数据按大小插到对应的叶子页。但页的容量是有限的——当一页塞满再插入时,就从中间劈开,变成两页,再把中间那个键上提到父节点当路标。这叫节点分裂(split)。父节点也可能因此被塞满,继续往上分裂,最坏情况根节点分裂、树长高一层。

这套机制妙在哪:树是向上长的。根节点分裂才长高,而绝大多数分裂发生在叶子层,所以树高增长极其缓慢——几亿行数据的树,高度大概率还是个位数。插入再多,查找依然是「每层一次 I/O」的水平。

下面两张图对照着看:

一次三层的 B-Tree 查找路径:根节点到内部节点再到叶子节点,高亮每次磁盘 I/O 读到的页

五、五分钟实验:亲手验证索引生效#

理解原理之后,最爽的部分是自己动手验证。整个实验五分钟,但印象会比看十篇文章都深。

第一步:造一张没有索引的表。

1
sqlite3 test.db

1
CREATE TABLE users (id INTEGER PRIMARY KEY, username TEXT, score INTEGER);
2
-- 用递归 CTE 快速插入 100 万行
3
WITH RECURSIVE cnt(x) AS (
4
  SELECT 1 UNION ALL SELECT x+1 FROM cnt WHERE x < 1000000
5
)
6
INSERT INTO users (username, score)
7
SELECT 'user' || x, abs(random() % 100) FROM cnt;

第二步:看一眼查询计划。

EXPLAIN QUERY PLAN 会告诉你 SQLite 打算怎么执行这条查询,不用真执行:

1
EXPLAIN QUERY PLAN SELECT * FROM users WHERE username = 'user500000';

输出里出现 SCAN users ——SCAN 就是全表扫描,一百万行一格格爬。

第三步:建索引,再看。

1
CREATE INDEX idx_username ON users (username);
2
EXPLAIN QUERY PLAN SELECT * FROM users WHERE username = 'user500000';

输出变成 SEARCH users USING INDEX idx_username (username=?) ——SEARCH 加 USING INDEX,说明它顺着 B-Tree 直接定位去了。

再给 score 建个索引,对比两种条件,你能看清「索引对什么条件有用」:

1
CREATE INDEX idx_score ON users (score);
2
EXPLAIN QUERY PLAN SELECT * FROM users WHERE score > 90;

score > 90 同样能走索引——B-Tree 的叶子是按 score 排序的,大于 90 的数据在树上是一段连续区间,顺着扫这一段就行。这就是为什么范围查询也吃索引:排序结构不但能定位「等于」,还能定位「区间」。

查询方式	EXPLAIN 关键词	100 万行大约的行读取量
无索引等值查询	`SCAN users`	~1,000,000
有索引等值查询	`SEARCH ... USING INDEX`	~20(树高次 I/O + 1 行)
有索引范围查询	`SEARCH ... USING INDEX`	满足条件的行数

把表补一句题外话:索引也不是越多越好,后面会讲。

六、三个大一大二最容易踩的索引误区#

知道「要建索引」只是及格线,这几个坑才是拉开差距的地方:

1. 对索引列套函数,索引直接失效。

1
WHERE upper(username) = 'USER1'   -- 走不了 idx_username
2
WHERE username = 'USER1'          -- 能走

索引存的是 username 原始值的顺序,套了 upper() 之后,SQLite 没法在有序结构里查「upper 之后等于 USER1 的值」,只能老老实实全表扫。同理,列上做运算、隐式类型转换(拿 TEXT 列和数字比)都会踩这个坑。

2. 模糊查询 LIKE '%xxx' 基本没用。

通配符开头时,前缀是未知的——而 B-Tree 定位靠的正是前缀。LIKE 'user%' 可以走索引(前缀 user 是确定的,相当于区间查询),LIKE '%user' 只能全表扫。

3. 无脑给每列都建索引。

每个索引都是一棵独立的 B-Tree,写入(INSERT/UPDATE/DELETE)时每棵树都要同步维护,空间也翻着涨。查询快了,写入慢了——这是一笔 trade-off,不是免费午餐。经验法则:按真实查询建索引,WHERE 和 ORDER BY 里高频出现的列优先,用不上的坚决不建。

还有一条「心法」:索引列尽量单调递增(比如自增 id、时间戳),新数据总落在树的最右边,很少触发中间分裂;而用随机值(比如随机 UUID)当主键,插入位置全随机,页分裂会频繁很多,写入性能肉眼可见地下滑。这也是很多老手选主键时会绕开随机 UUID 的原因。

七、结语:从「会用」到「知道为什么」#

回头看,索引加速的全部逻辑其实就三句话:数据有序才能二分定位;按页组织才能少吃磁盘 I/O;B-Tree 用「胖矮」的树形把这两点同时做到了。

这篇文章只能算入门——B-Tree 还有 range scan 的页内遍历、WAL 日志、SQLite 实际使用的 B+Tree 变体(数据全存在叶子层、叶子之间串成链表)等进阶话题,值得你顺着兴趣继续挖。好消息是,工具你已经有了:EXPLAIN QUERY PLAN 随时能告诉你查询在干什么。

下次写课程项目,如果发现列表页越刷越卡,别急着换语言、加机器——先跑一句 EXPLAIN,看看 SCAN 在哪。从「能用」到「知道为什么快」,这一步往往就是课设和别人拉开差距的地方。

想继续玩的话,附两份材料:

SQLite 官方文档 Planning —— 比 SQLite 本身的历史还长一点的经典文档
SQLite 官方 QUERY PLAN 用法 —— 本文第五节的官方原版

音乐