一、先造一张五万行的表

建一张 score(id, name, val) 的表，插五万行，库文件 1040.0 KB。 五万行不算大，但足够让「全表扫」和「走索引」拉开差距。 为什么用 val 这个字段查？ 因为它是数字，分布均匀，最能体现索引的效果——换成性别这种只有两个值的字段，索引几乎没用。

这一点值得先记下：索引对「取值多的字段」有用，对「取值少的字段」没用。只有两个值的字段， 扫一半和扫全部差不多。

二、不建索引：全表扫

查 val = 12345，用了 4.264 毫秒，执行计划是 SCAN score。 「SCAN」就是逐行看。五万行看一遍才找到，所以慢。 更关键的是它跟数据量成正比： 数据涨到五百万行，就是一百倍时间。这也是「系统上线后越用越慢」最常见的原因。

注意这里没有「运气好早点找到」这回事——数据库不知道 12345 在哪一行，它只能一行行试。 这和 6.1 的线性搜索是同一件事，只不过一个是代码里循环，一个是数据库在读磁盘页。

三、建一个索引，再查一次

给 val 建索引，同一个查询变成 0.035 毫秒，计划变成 SEARCH score USING INDEX idx_val (val=?)。 快了 122.5 倍。 而且这个倍数会随数据量增大而增大。 计划里那三个词值得认：「SEARCH」是走索引找、「USING INDEX」是说用了哪个索引、 (val=?) 是说用哪个条件去定位。

索引为什么能这么快？因为它是一棵排好序的树（B 树），叶子节点指向真正的行。 查的时候顺着树往下走几层就到。 这就是 3.5 那棵二叉搜索树的思路，只是换成了一次能分很多叉的版本——分叉多了，层数就少， 磁盘读的次数就少。

四、排序也吃索引

索引不只加速「查等于」，还加速「排序」。 有索引时 ORDER BY val LIMIT 10 只要 0.037 毫秒， 计划是 SCAN score USING COVERING INDEX idx_val。 删掉索引后同一个查询变成 7.999 毫秒，计划多了一句 USE TEMP B-TREE FOR ORDER BY。

「COVERING INDEX」是说索引里已经有要的列，根本不用回表——顺着索引读前十个就完。 而那句 USE TEMP B-TREE 是「临时搭一张表来排」：把五万行全排一遍再取前十个。 排五万行只为了要十个，这就是浪费。

五、数据库问的不是「怎么排得快」，是「能不能不排」

课上问的是「哪种排序快」，数据库问的是另一个问题：「这个顺序能不能提前存好？」 提前存好，就不用每次排。索引就是「提前排好的那份顺序」。 这是本课一个视角的转换：排序算法是「一次性的活」，索引是「把活存下来反复用」。 前者省时间，后者省重复劳动。

所以「给哪些字段建索引」这个问题，等价于「哪些顺序值得存下来」。 答案取决于你的查询：天天按它排序、按它查等值的字段，就值得。 再往上一层：这就是 6.1 那个「先排序再二分」的持久化版本。一次排序的成本被分摊到无数次查询里。

六、索引不是越多越好

索引是副本，所以它有三个代价：

第三条容易被忽略：索引多了，优化器要在更多选项里挑，偶尔会挑错。 挑错的时候只能靠重写查询或者强制指定索引来救。 所以判断标准是一句话：查得多还是写得多。读多写少的表多建，天天大批量写入的表少建。 这条和教材专题里那句「关系型数据库靠排序和搜索吃饭」是一件事——它吃的就是「把顺序存好」这笔账。

七、动手 Demo：五万行的表：建不建索引，差一百多倍

用 sqlite3 现造一张五万行的表，先不建索引查一次，把执行计划打出来。 再给 val 建索引，同一个查询再跑一次。 最后测 ORDER BY ... LIMIT 10：有索引和删掉索引各跑一遍。

import sqlite3, os, time

def fresh(path):
    if os.path.exists(path):
        os.remove(path)
    db = sqlite3.connect(path)
    db.execute('CREATE TABLE score(id INTEGER PRIMARY KEY, name TEXT, val INT)')
    db.executemany('INSERT INTO score(name, val) VALUES(?, ?)',
                   [('n%d' % i, i) for i in range(50000)])
    db.commit()
    return db

def plan(db, sql):
    return [r[-1] for r in db.execute('EXPLAIN QUERY PLAN ' + sql)]

def timed(db, sql, n=5):
    best = 9e9
    for _ in range(n):
        t = time.perf_counter()
        db.execute(sql).fetchall()
        best = min(best, time.perf_counter() - t)
    return best * 1e3

db = fresh('_idx56.db')
q = 'SELECT * FROM score WHERE val = 12345'
print('无索引 %.3f 毫秒' % timed(db, q), plan(db, q))
db.execute('CREATE INDEX idx_val ON score(val)')
print('有索引 %.3f 毫秒' % timed(db, q), plan(db, q))

o = 'SELECT * FROM score ORDER BY val LIMIT 10'
print('排序 有索引 %.3f 毫秒' % timed(db, o), plan(db, o))
db.execute('DROP INDEX idx_val')
db.commit()
db2 = sqlite3.connect('_idx56.db')
print('排序 无索引 %.3f 毫秒' % timed(db2, o), plan(db2, o))

实跑输出：

--------------------------------------------------------------------
数据库里的排序与搜索：索引到底是什么
--------------------------------------------------------------------


  ① 先造一张五万行的表
  --------------------------------------------------------------------
  建表 score(id, name, val)，插入 50000 行，库文件 1040.0 KB

  ② 不建索引，查一个数
  --------------------------------------------------------------------
  查 val = 12345：4.264 毫秒
  执行计划：SCAN score
  「全表扫」三个字就说明它在逐行看。5 万行看一遍，数据涨到 500 万行就是 100 倍时间。

  ③ 建一个索引，再查一次
  --------------------------------------------------------------------
  建完索引再查：0.035 毫秒
  执行计划：SEARCH score USING INDEX idx_val (val=?)
  快了 122.5 倍
  索引就是一棵排好序的树（B 树），叶子节点指向真正的行。
  查的时候不用扫全表，顺着树往下走几层就到——这就是第 15 章那个二叉搜索树，
  只是换成了一次能分很多叉的版本。

  ④ 排序也吃索引
  --------------------------------------------------------------------
  有索引时 ORDER BY val LIMIT 10：0.037 毫秒
  计划：SCAN score USING COVERING INDEX idx_val
  删掉索引后：7.999 毫秒
  计划：SCAN score / USE TEMP B-TREE FOR ORDER BY
  有索引时，数据本来就是按 val 排好的，取前 10 个直接拿；
  没索引就得把 5 万行全排一遍再取前 10 个——
  计划里那句 USE TEMP B-TREE 就是「临时搭一张表来排」的意思。
  这就是「数据库里的排序」和「算法课上的排序」最大的差别：课上问「怎么排得快」，
  数据库问「能不能不排」——答案是把顺序提前存好。

  ⑤ 索引不是越多越好
  --------------------------------------------------------------------

| 代价 | 具体是什么 |
|---|---|
| 占空间 | 索引本身要存一份排好序的副本 |
| 拖慢写入 | 每插一行，所有索引都要跟着改 |
| 选错索引 | 优化器可能挑一个更慢的走法 |

  所以建索引要看「查得多还是写得多久」。
  读多写少的表多建，
  天天大批量写入的表少建——这条和教材专题里那句「关系型数据库靠排序和搜索吃饭」是一件事。

①timed 里跑五次取最快， 不是取平均——第一次要摊掉连接和缓存的初始化，取平均会把那个成本算进去。 ②plan 用的是 EXPLAIN QUERY PLAN，它只报计划不真跑，所以能安全地反复调。 ③删掉索引后必须新开一个连接再查计划。 同一个连接会缓存旧计划，不新开就还报 USING COVERING INDEX——这个坑很容易踩。 ④三个关键数字：无索引 4.264 毫秒、有索引 0.035 毫秒（快 122.5 倍）、 排序有索引 0.037 对无索引 7.999。具体值随机器变，倍数不会翻盘。

30 秒实验

1. 把 WHERE val = 12345 换成 WHERE val > 40000，看索引还有没有用（会变慢还是变快）。
2. 给 name 也建一个索引，再测插入五万行要多久，看「拖慢写入」有多少。
3. 把表改成只有两个取值（比如 val 只存 0 和 1），看索引还剩多少效果。

常见误区

1. 「索引越多查询越快。」索引占空间、拖慢写入，还可能导致优化器选错。
2. 「建了索引，所有查询都会走它。」取值范围太大、或者条件里对字段做了运算，索引就用不上。
3. 「数据库的排序和课上学的没关系。」索引本身就是一棵排好序的树，建索引就是提前做一次排序。

第 6 章到此结束。 搜索和排序都讲完了，下一章换一批「不那么像算法」的算法：解方程的、算面积的、筛质数的，还有递归。

• ☐ （本篇完，下一篇 7.1 牛顿法与高斯消元）

相关笔记

• 线性搜索与二分搜索
• 希尔排序与快速排序
• 15 数据库 · 索引
• 🧮 写给大家看的算法书 · 索引