一、三张表：一行一个事实

做一个最小的图书馆：作者、书、借阅三张表。

二、查询：投影、选择、连接

表拆开了，查的时候就得拼。SQL 那一大堆关键字，其实就是三种操作在组合：

三、索引：拿空间和建表时间换查找

十万行数据，要找其中一行，最笨的办法是从头翻。平均要翻五万行才碰上一半的机会。

四、冗余、范式、事务：三件不同的事

第一件：冗余。把三张表拍平成一张宽表，作者名跟着每本书重复一遍。 「张三」在宽表里出现 4 次，在 authors 里只出现 1 次。 后果不只是占地方。改张三的国籍，宽表要改 4 处；改漏一处，库里就有两个互相矛盾的答案。 这叫更新异常，范式就是专门拆它的。 第二件：范式。它的全部内容说出来很朴素——把「只跟一个东西有关」的信息拆出去，各自一张表。 拆到每一列都只依赖主键，就不会有同一个事实写好几遍。 第三件：事务。两个人转账，A 扣 200 再给 B 加 200。 Demo 里把第一步做完就停：A=300、B=300，总额从 800 变成 600。 凭空少了两百块，这个状态在真实系统里绝对不能出现。 办法是先写日志再改数据。崩了照日志重放： 「A-200、B+200」已经记下，重启后把没做完的 B 补上，总额回到 800。 A 和 D 就是原子性和持久性，C 是一致性，I 是隔离性。 四个字母说起来一句话，做起来是数据库最贵的部分。

五、动手 Demo：一行一个事实，查的时候再拼起来

五段：建三张表、三种连接查询、索引与全表扫描对比、宽表的冗余代价、事务与日志。 没有装任何数据库。表就是 list，连接就是两层 for，索引就是自己排的序。 这样每一步的代价都能数出来。

def join(A, B, ka, kb):            # 嵌套循环连接：左表每行比右表每一行
    out = []
    for a in A:
        for b in B:
            if a[ka] == b[kb]:
                out.append(a + b)  # 拼成一行宽记录
    return out


def bsearch(xs, k):                # 排好序之后，二分只要十七次
    lo, hi, n = 0, len(xs) - 1, 0
    while lo <= hi:
        n += 1
        mid = (lo + hi) // 2
        if xs[mid] == k:
            return n
        if xs[mid] < k:
            lo = mid + 1
        else:
            hi = mid - 1
    return n

实跑输出：

--------------------------------------------------------------------
一行一个事实，查的时候再拼起来
--------------------------------------------------------------------
==============================================================

[1] 三张表：作者、书、借阅

  每张表就是一张二维表，每行一个事实，每列一个属性：

    表名      列                                行数
    authors   id, name, country                 5
    books     id, title, author_id, year        20
    loans     book_id, reader, date             120

  books 里的 author_id 指向 authors 的 id，这就是外键。
  它不存作者名字，只存一个编号——这一点后面第 4 段还要算账。

  authors 表全部五行：

    id   name      country
    1    张三      中国
    2    李四      中国
    3    Smith     美国
    4    Tanaka    日本
    5    王五      中国

  books 表前五行：

    id   title                     author_id  year
    1    第一行代码                1          2015
    2    算法导论                  4          2008
    3    深入理解计算机系统        3          2017
    4    图解人工智能              1          2014
    5    数据库系统概念            2          2000

  **三张表各自只说自己那一摊事。**
  **作者换国籍只改 authors 一行，二十本书一个字都不用动。**

[2] 查询：把表连起来再筛

  SQL 那几句 select／from／where／group by，其实就是三种操作的组合：
  **投影（挑列）、选择（挑行）、连接（拼表）。**
  这里不用数据库，三种操作各写十行函数，跑三个查询。

  查询一：美国作者写的、2005 年以后的书
    连接 books 与 authors：20 行乘 5 行 = 100 次比较，拼出 20 行
    筛掉国籍和年份之后剩 5 行：
      深入理解计算机系统        2017  Smith
      编译原理                  2020  Smith
      深度学习                  2006  Smith
      人月神话                  2016  Smith
      重构                      2008  Smith

  查询二：每个作者有几本书（分组计数）
    作者      国籍    本数
    张三      中国    4
    李四      中国    2
    Smith     美国    7
    Tanaka    日本    4
    王五      中国    3

  查询三：从没被借过的书（反连接）
    20 本书里有 14 本被借过，6 本一次都没借出去：
      重构                      2008
      程序员的自我修养          2003
      现代操作系统              2010
      数据密集型应用系统设计    1999

  **三次查询，同一批表，拼法完全不同。**
  **这就是关系模型的好处：数据只存一份，想看什么当场拼。**
  **代价也在那儿——第一种拼法做了 100 次比较，只有 20 行有用。**

[3] 索引：不建索引就一行行翻

  100000 行数据，随机取 100 个键去找，数「比了几次」：

    办法            平均比较次数  建表代价        一次查找
    全表扫描        51898.5       0               顺序走
    排序加二分      15.6          1660964 次比较  跳到中间
    哈希表          1.0           100000 次插入   直接跳

  100 次查找的实测耗时（三轮取最小，单位毫秒）：
    全表扫描        1262.287
    排序加二分      1.079
    哈希表          0.029

  **全表扫描要翻五万行才碰上一半的机会，二分只要十七次。**
  **注意建表代价那一列：二分不是白来的，排序本身是 n log n。**
  **所以索引适合「建一次、查很多次」；只查一次的表，建索引反而亏。**

[4] 冗余：一张大宽表会付什么代价

  把三张表拍平成一张宽表，作者的名字和国籍跟着每一本书重复一遍：

    结构        总行数        名字出现次数    说明
    3 张表      5+20+120      5               每个名字一行
    1 张宽表    20            20              每本书一行

  **作者「张三」在宽表里出现 4 次，在 authors 里出现 1 次。**
  现在把「张三」的国籍从中国改成新加坡，两种结构各要改几处：
    改 authors 一行     1 处
    改宽表              4 处

  **冗余的代价不止是占地方，更是「同一件事有好几份拷贝」。**
  **改漏一处，库里就出现两个互相矛盾的答案——这叫更新异常。**
  **范式的全部内容，就是把这些「只跟一个东西有关」的信息拆出去各自一张表。**

[5] 事务：要么全成，要么全不成

  两个账户，初始 A=500、B=300，总额 800。

  转账 200：先扣 A，再给 B。中途断电会怎样？
    只做了第一步：A=300、B=300，总额 600 —— 少了 200。

  办法是先把「要干什么」写进日志，再改数据；崩了照日志重放或撤销：
    日志已写：[A-200, B+200]，只执行了一半，此时总额 600。
    重启后照日志补完：A=300、B=500，总额 800。

  **A 和 D 就是原子性和持久性：一半的转账不许存在，写下的日志不许丢。**
  **C 是一致性（总额守恒），I 是隔离性（外面看不到中间那半步）。**
  **四个字母说起来简单，做起来是数据库最贵的那部分。**

  五段连起来：**关系模型把数据存成表，一行一个事实**；
  **查询是投影、选择、连接三种操作拼出来的**；
  **索引拿空间和建表时间换查找速度**；
  **冗余会带来更新异常，范式就是拆掉它**；
  **而事务保证「一半的操作」永远不会留在库里。**

第 1 段那三张表要看「哪一列不在里面」。books 没有作者名， 只有编号——这就是规范化的第一步，也是后面所有好处的来源。 第 2 段三个查询值得比着看：同样的数据，拼法完全不一样。 查询三那个「反连接」尤其典型——它问的是「不存在」，而 SQL 里这类问题最容易写错。 第 3 段那张表的第三列（建表代价）比第二列更重要。 只看「快了多少」会得出「全都建索引」的错误结论。 第 5 段那个总额 600 是这一节最该记住的数。 它说明「一半的操作」是一个真实存在、必须被消灭的状态。

30 秒实验

1. 把第 2 段查询一的年份从 2005 改成 2020，重跑。 结果会只剩一两条—— 筛选越严，连接那 100 次比较显得越浪费，这也是优化器要重排执行顺序的原因。
2. 把第 4 段宽表的作者列删掉、只留编号，重跑。 「改几处」立刻从 4 变成 1——这就是范式在做的事，一步到位。
3. 把第 3 段的 N 从 10 万改成 100 万，重跑。 二分只多几次比较，扫描要慢十倍——对数增长和线性增长的差别，越大规模越明显。

常见误区

1. 以为「数据库就是存数据的地方」。存谁都会， 数据库真正在解决的是「改一处不能出现两个答案」和「一半的操作不许留下」这两件事。
2. 以为「建索引越多越好」。每个索引都要在每次插入、删除时同步更新。 写多的表建一堆索引，写会慢到没法用。
3. 以为「范式越高越好」。真实系统常常故意反范式—— 报表查询不想每次都连接五张表，就直接存一份冗余。这是权衡，不是错误。
4. 以为「加了事务就不会出错」。事务保证的是「要么全成、要么全不成」， 它不保证业务逻辑对。转账写成「两边都加钱」，事务跑得再好也照样出错。

下一节换个问法：不要求「精确匹配某一行」，而是「这几万篇里哪几篇最相关」。 数据库回答「有没有」，检索回答「有多像」——这是两种完全不同的索引。

• ☐ （本节完，下一节 12.2 检索）

相关笔记

• 结构分析
• 检索
• 语义网络和语义网
• 📘 图解人工智能 · 索引