花了几个周末把CMU 15-445（cmu15445）的前三讲啃完了，趁着记忆还热乎赶紧整理成笔记。这门课在数据库圈子里什么分量不用我多说，Andy Pavlo亲自带队，所有课件、作业、考试都公开，号称“数据库系统领域的CSAPP”。我这次整理的是lec1到lec3：关系模型、SQL语言、存储层设计，刚好是整门课的地基三件套。无论你是准备秋招面试补数据库底层知识，还是工作中被慢SQL虐过想搞清楚DBMS内部到底在干嘛，前几讲都值得反复咀嚼。这篇笔记不是复读幻灯片，我尽量把Andy课上反复强调的核心逻辑、我踩过的理解误区、以及能直接映射到日常工作的点都写清楚。
说实话，第一次看lec1-3的时候，我犯了一个错误：以为就是讲SQL和建表，随便扫一眼就过去了。真正静下心跟完才发现，这三节课的信息密度极高，尤其是存储层那部分，直接决定了后面缓冲区管理、索引结构、并发控制能不能听懂。所以这篇笔记我按“关系模型 → SQL → 存储布局”的顺序拆开讲，每一步都尽量解释清楚背后的为什么，而不是只记结论。
1. 内容整体设计与思路拆解
1.1 为什么cmu15445前三讲是整门课的承重墙
数据库系统这门课看起来知识点很散，实际上有一条清晰的主线：数据怎么存、怎么查、怎么并发、怎么恢复。lec1-3对应的就是“数据怎么存”和“怎么查”的入门形态，后面的所有高级话题几乎都在前三讲的假设之上做文章。
比如lec3讲的页（page）和记录（record）布局，到后面讲索引时，你会反复遇到这些概念：B+树的叶子节点本质上就是某种形式的页，节点分裂时要移动记录，如果对slotted page不熟悉，看索引实现会像看天书。同理，没有理解关系代数是SQL的“编译前形态”，就无法真正明白为什么SQL声明式写法能表达各种复杂查询，也更难理解查询优化器在做什么——它做的事其实就是把你写的SQL翻译成关系代数执行树，再想办法换一种成本更低的等价代数表达式。
我的建议是：前三讲宁可放慢速度，也一定要做到“合上视频能自己画出页布局图、能写出关系代数表达式、能默写出SQL执行顺序”。这一遍的深度，决定了你后面是听得懂还是听得懵。
1.2 课程节奏与lec1-3的内容边界
2023秋季这门课的实际录制版本里，lec1是课程导论加关系模型，lec2是SQL和关系代数，lec3是存储结构。按Andy自己的说法，他会在前几讲快速把关系模型交代清楚，然后立刻进入SQL实操，因为SQL是后面的所有作业（比如Project 1的存储、Project 2的哈希索引）要用的基础工具。
需要注意，这里的关系模型和“关系型数据库”里的“关系”是一个意思，但和“关系代数”不同。关系模型描述的是数据结构本身——一张表、一个元组、一个属性；关系代数描述的是怎么操作这些结构。lec1讲前者，lec2讲后者。这个区分如果你没留意，后面看你可能会把select操作和SQL的SELECT关键字搞混。
还需要做好一个心理准备：这门课不是让你学会用某个数据库工具的，而是让你能自己写出一套数据库。所以前几讲里Andy会反复强调“DBMS不知道你的表长什么样，它只看到字节”，这句话是理解存储设计的钥匙。
1.3 我读这一遍时的目标拆解
我给这次学习定了三个可验证的产出目标：
- 对每张PPT里的关键图，比如主键外键约束图、页布局示意图，能不看笔记重新画出来并讲清每部分的含义。
- 把lec2里所有SQL示例在SQLite和PostgreSQL里各跑一遍，尤其要试出那些“看起来很对但一执行就报错”的写法，加深记忆。
- 在本地Python里实现一个简化版的slotted page内存结构，验证变长记录插入和删除时槽位怎么移动。
这样的目标比“看完视频”更有意义。看完视频只是输入，能写出来、跑出来、画出来才是真正消化。
2. 第1讲核心：关系模型不是“建表”那么简单
2.1 关系模型的三大组件
Andy在lec1给的框架是：关系模型由结构（structure）、完整性（integrity）、操纵（manipulation）三部分组成。结构就是表、列、行；完整性就是主键、外键、唯一约束这些规则；操纵就是关系代数和SQL能做的那些查询变换。
我第一遍看的时候觉得这太抽象了，后来找到一个类比：你可以把关系模型想象成Excel的“强规则版”。Excel允许你在同一列里塞日期、数字和文字，也允许两行完全相同，但关系模型通过域（domain）和键约束把这些漏洞堵死了。域就是每列必须是某一种类型，主键就是每一行必须有唯一标识，外键就是列与列之间的引用关系必须合法。
这个理解到位后，再看为什么关系模型当年能打败层次模型和网络模型就顺了：层次模型像是一棵严格的树，网络模型像是复杂的网状指针，你想查一个数据必须知道路径怎么走；而关系模型把全部数据摊成二维表，用一套统一的代数语言（SQL）查询，用户不用关心底层存储是怎么组织的。这就是“物理数据独立性”的核心价值——底层存储随便换，你写的查询不用改。
实操笔记：建议自己动手在纸上把“学生表、课程表、选课表”画出来，标出每个表的主键和外键，再想想如果不用外键、全靠应用层逻辑判断，会发生什么诸如脏数据、悬空引用之类的问题。反复画过一遍后你才会真正理解外键约束存在的意义。
2.2 主键、外键、NULL的细节陷阱
主键有两个硬性要求：唯一且非空。这里有一个容易漏的点，就是和UNIQUE约束的区别——UNIQUE列允许NULL，多个NULL不算重复，而主键列压根不允许NULL。MySQL的InnoDB里主键还会自动建聚簇索引，这也意味着磁盘上的数据行物理排列顺序会跟主键密切相关。这些细节远不是建表工具自动生成的SQL能体现的。
外键的语义也值得抠一抠。外键定义的是一个引用完整性约束，比如选课表里的student_id引用学生表的id。我见过很多实际项目为了“省事”故意不建外键，只靠应用层代码保证一致性，看似灵活，实际上在高并发写入时很容易出现孤儿数据，排查起来想死。Andy课上提到的ON DELETE CASCADE / SET NULL / RESTRICT这些外键动作选项，其实就是数据库在帮你处理引用关系变化时的决策，这比全交给应用层更可靠。
还有一个绕不开的话题就是NULL。关系模型里NULL表示“未知”或“不存在”，它不是一个值。这就导致SQL里所有比较都得处理三值逻辑：TRUE、FALSE、UNKNOWN。很多老手写SQL偶尔踩坑，就是因为忘了NULL参与比较时可能直接让整条WHERE条件被过滤掉。最典型的就是NOT IN子查询遇到NULL返回空结果的问题，我见过不止一个团队为这个线上事故挠头。后面第二讲还会再提，但第一讲就应该建立起“NULL是传染源”的警觉。
2.3 关系代数：SQL的“隐形执行计划”
lec1里Andy花了不少篇幅讲关系代数，包括：选择（select，σ）、投影（project，π）、聚合、重命名，以及集合运算（并、交、差）和连接（join）。这些希腊符号第一次见时很容易劝退，但按我自己的经验，它们其实是在教你一种“SQL背后发生了什么”的思考方式。
举一个实际例子：SELECT S.name FROM Student S JOIN Takes T ON S.id = T.student_id WHERE T.course = 'database'; 如果用关系代数写，逻辑顺序是：先从Student表做重命名得到S，从Takes表重命名得到T；接着做连接π(σ(S ⋈ T))，注意选择和投影的执行顺序不同，可能得到完全不同的成本和结果数。查询优化器就是在这些等价表达式中间挑最优的。
我后来的体会是：把关系代数看作“数据库世界的流程图”。当你学会把一条SQL拆成一棵代数树，你才能理解为什么有的SQL写法会触发慢查询——因为你的写法可能迫使优化器做笛卡尔积再过滤，而不是先过滤再连接。Andy在前三讲不直接讲优化器，但他埋的伏笔就在这。
实操建议：给自己出十道关系代数题，比如“找出选了所有课程的学生”“找出选修了同一位老师两门课的学生”，先用SQL写，再尝试翻译成关系代数。你会发现很多用中文很好描述的需求，翻译成代数表达式时逼着你把精确定义想清楚。这个过程非常磨练对SQL语义的理解。
3. 第2讲核心：SQL的声明式思维与执行顺序
3.1 SQL分类与表定义里的约束优先级
lec2从一个很舒服的切入点展开：SQL分DDL（数据定义）、DML（数据操作）、DCL（数据控制）三类。最核心的是CREATE TABLE，其中涉及的约束特别多：PRIMARY KEY、FOREIGN KEY、UNIQUE、NOT NULL、DEFAULT、CHECK。我整理笔记时给它们分了个优先级视角：主键决定行的身份，外键决定行之间的血缘，CHECK列级约束则是给单列上保险丝。
Andy在课上特意强调了一个观点：关系模型虽然是理论，但商业数据库的SQL实现各有差异。比如VARCHAR长度的语义，PostgreSQL里VARCHAR(n)超过n会报错，SQLite却不强制校验长度（SQLite比较宽容，不报错，只是隐式截断或直接忽略长度限制）。我的建议是：建表前先查官方文档，别靠印象。过去我在一个项目里用MySQL的VARCHAR(255)当默认模板，结果后来发现某个列需要存很长的JSON，恰好踩到了行大小限制的坑，折腾了一晚上才定位。这些都反映出对DDL语义的理解不能只停留在“能建表就行”。
另外，表中列的顺序在大部分DBMS里不是随便定的，它影响记录在磁盘上的物理布局。这也是从第一讲延续到第三讲的一条暗线——你以为你只是在写SQL，其实每个列定义都在为存储层设计挖坑或铺路。
3.2 SELECT执行顺序：最值得背下来的那张表
lec2花了很多时间讲SELECT语句的完整语义顺序。网上的执行顺序版本五花八门，我自己整理成这张表：
| 顺序 | 关键字/步骤 | 说明 |
|---|---|---|
| 1 | FROM + JOIN | 确定数据来源，做笛卡尔积再过滤连接条件 |
| 2 | WHERE | 行级过滤，不能使用聚合函数 |
| 3 | GROUP BY | 分组 |
| 4 | HAVING | 分组后过滤，可以使用聚合函数 |
| 5 | SELECT | 投影列，计算表达式，生成别名 |
| 6 | DISTINCT | 去重 |
| 7 | ORDER BY | 排序 |
| 8 | LIMIT/OFFSET | 截断行数 |
这张表最大的用处不是应付考试，而是帮你排查SQL报错。最常见的错就是：在WHERE里用COUNT(*)，或者在SELECT里用了一个没有GROUP BY的普通列。理解了执行顺序，这类报错你根本不会犯，因为你一眼就能看出某个列在分组之后根本不可见。
举个例子，SELECT department, COUNT() FROM employees WHERE salary > 8000 GROUP BY department HAVING COUNT() >= 5 ORDER BY COUNT(*) DESC LIMIT 3。按上面的顺序走一遍：先从employees经过WHERE过滤，然后按部门分组，统计每个组的人数，HAVING过滤掉少于5人的组，SELECT输出部门和人数，排序后取前三。每一步都有明确的数据边界，逻辑就不会乱。
3.3 JOIN、聚合与子查询的实战避坑
JOIN是SQL里的高频热点，但真正容易出错的地方在于外连接时NULL的处理。LEFT JOIN右表没有匹配行时，右表所有列都以NULL填充，此时如果你在WHERE里写了右表某个字段的条件（比如t.course = 'database'），会把原本保留的左表行又过滤掉——很多人所谓“LEFT JOIN结果少了”基本都是这个原因。
正确的做法是：对右表的过滤条件放在ON子句里，而不是WHERE子句里。这个规则我建议直接记成一句口诀：外连接的保留行过滤条件在ON，最终结果过滤条件在WHERE。Andy的课虽然没有像MySQL手册那样单列这一条，但你在做完Project 3的Join算子之后，会从原理上彻底明白这一点。
聚合函数也有一个值得注意的坑：COUNT(column)和COUNT()不一样。COUNT(column)会忽略NULL行，COUNT()统计所有行。项目里统计订单数时，如果用COUNT(coupon_id)，明明有一堆没有用券的订单，结果数量神秘变小，排查起来非常隐蔽。
子查询这块，我自己始终提醒自己的是：能用JOIN表达的查询尽量别用相关的子查询。相关子查询往往会让外部每一行都触发一次内部查询，性能容易爆掉。不过这次说的性能问题是泛指，它跟优化器实现有关，不能一概而论。关键是建好索引、多看看执行计划。
我建议跟读lec2时，顺手把每一个SQL例子都在数据库里跑一遍，特别是尝试用不同写法完成同一个需求（子查询vs JOIN vs EXISTS），看看执行计划有什么不同。这种对比练习积累多了，写SQL才能又快又准。
4. 第3讲核心：数据库怎么在磁盘上“摆”数据
4.1 从存储层次到页的必然性
lec3一上来就丢了一个核心背景：数据库要面对的是磁盘（或SSD）和内存之间的巨大差异。内存访问按纳秒算，随机磁盘访问按毫秒算，SSD也在几十微秒到几百微秒这个量级。这意味着数据库不可能每处理一条记录就去磁盘上找一次，必须把磁盘上的数据组织成固定大小的“页”（page），以页为单位读写。通常一个页是4KB（PostgreSQL默认8KB，MySQL的InnoDB默认16KB）。
这就像你搬家时不可能把每件衣服单独运一趟，一定装箱、打包、整车运输。页就是数据库的“箱子”。所有数据库系统都围绕这个箱子做文章：内存里的缓存是页的缓存，索引的节点是一个个页，事务提交时刷盘也是以页为单位做日志和落盘。
理解了这一点，再看存储设计就顺了：数据库本质上是“一个按页管理文件的软件”，所有上层功能都得落实成“把Page #N放进内存 / 把Page #N写回磁盘”这样的操作。Andy在lec3反复强调“DBMS aims to maximize the number of pages in memory”，其实就是点出后续缓冲区管理器（buffer pool）的全部意义。
4.2 堆文件、链表 vs 页目录
文件组织方式lec3重点讲了堆文件（heap file）的两种实现：链表式和页目录式。链表式就是每个页存着下一页的位置，逻辑简单但想要找到某个页就得从头遍历，随机访问性能不好。页目录式专门维护一个页目录页，相当于一个索引表，记录每个页的位置，能快速找到一个页。
实操联想：日常的文件系统里树状目录和扁平文件各有优劣，数据库的文件组织也是同样的权衡。课程后面还有专题页（如B+树索引页、哈希页），都属于不同形式的数据组织。在笔记里，我把这三层概念串起来：数据文件是页的集合，页是记录的容器，记录是行的实际编码。这三层关系如果你能闭眼画出来，lec3就算过关了。
Andy课堂上还会提到“页头（page header）”保存元数据，比如页的编号、空闲空间起始位置、记录数量、校验和等。每个数据库页都有自己的头部，千万别把页头和表格头搞混——页面头是物理存储层的东西，表格头是逻辑数据模型层面的东西，两者在不同层级解决不同问题。
4.3 Slotted Page：变长记录怎么安家
lec3中最具实操价值的概念就是Slotted Page（槽位页）。它的设计是：在页的头部放一个槽位数组，每个槽位记录对应记录在页内的偏移量；记录从页末尾往前生长，槽位数组从页头往后增长。当删除一条记录时，只是把槽位标记为空或移除，文件本身不立即压缩；当插入新记录时，如果后面空闲空间不足，DBMS可能选择移动已有记录或找新页。
这套设计最直接的实际价值体现在：数据库的UPDATE大多不是原地修改，尤其是变长字段从短变长时，原位置放不下，数据库可能把整条记录搬到新页或者做“先删除后插入”的物理变化。理解这一点的人，在设计表结构时会更有意识地区分定长字段和变长字段，而不是所有列都一律VARCHAR(255)——因为在页内定长记录可以靠偏移量“秒定位”，变长则需要读槽位、跟随指针，成本完全不同。
我强烈建议自己画一张图：左边是页头+槽位数组，右边是变长记录区域，中间是空洞，标出每一条记录和它对应的槽位偏移。这个图看懂后，再去理解PostgreSQL的MVCC为什么需要“过期版本”在不同页里，循环布局的问题就会贯通起来。
4.4 记录内部布局：NULL位图与定长/变长字段
记录内部的布局lec3也给出详细分析。定长记录在页内不需要额外存储元数据就能算出偏移，比如一条记录有3个INT字段，每条占12字节，那第4条记录的起点就是第36字节。变长记录就不一样，它需要保存字段的长度信息或结束位置。
和开发经验对应起来：你为什么经常看到“SELECT *”性能差？因为你可能把一个大VARCHAR或TEXT字段也读出来了，记录长度变大，每页装的记录变少，IO放大。明白了记录内部布局后，你就知道该只select需要的列，避免把大字段拖进page里浪费IO。
NULL的处理也是lew3的重点。一些系统用“NULL位图”（null bitmap）记录哪些字段为NULL，这比在每一行的数据里存一个NULL标记更省空间。MySQL的InnoDB记录头也会包含NULL标志，PostgreSQL则使用HEAP Header加上null bitmap机制。总之，NULL在存储层面并不是你想象的“空字符”，它更接近一个元数据标记。
一个细节让我印象很深：如果表里所有字段都是NOT NULL，DBMS可能不需要为NULL维护任何额外信息，这样每行能省下不少字节。对应到建表实践，就是要明确区分“业务上允许空”和“仅仅是当时没填”，不要把可空性当摆设。该NOT NULL的一定加上，既规范数据，又能变相节省存储并提升扫描性能。
5. 常见问题与排查技巧实录
5.1 我在前三讲踩过的理解误区
第一坑：把“关系”理解成表之间的关联。实际上关系（relation）就是表，关系模型中的“关系代数”和“关系（关联）查询”没有直接关系。这个误区会导致看外键定义和JOIN语义时脑子容易乱。
第二坑：以为SQL执行顺序和书写顺序一致。这是我早期写复杂SQL时反复头疼的根源。一旦背熟了上文的执行顺序表，哪些别名能用在哪些子句里、WHERE能不能用聚合函数，全都迎刃而解了。
第三坑：把“页头”“记录头”当成一种东西。二者层级完全不同，前者是物理存储单元的头信息，后者是单条记录内部的编码头信息。理解它们的前提是先分清楚“页”和“记录”是两个抽象层级。
5.2 学习过程中的演练方式
我的一个做法是：找一张自己的真实表结构（比如用户订单表），把建表DDL、几条INSERT语句，以及磁盘上大致怎么分布的过程都走一遍。然后分别设定几个场景：插入一条很长的地址字段、删除一条记录、把一个改得很长的备注字段更新进去。设想DBMS会怎么操作页和槽位。这个过程不需要真去读MySQL的源码，但会让你对为何要控制字段长度、为何页空间会碎片化等有直观认识。
另一个实用手段：给每讲做一个“一页纸总结”。Lec1一页纸写上关系模型三组件和主外键约束；Lec2一页纸写SQL执行顺序和JOIN陷阱；Lec3一页纸画slotted page图。复盘时只需要看这三页纸，效率高得多。
5.3 环境与练习资源建议
环境方面，我建议装两个东西：SQLite（零配置，适合快速验证SQL语义）和PostgreSQL（和cmu15445实验更贴近的关系型数据库，也是一线使用率很高的开源数据库）。用SQLite跑一个单独的文件，用PostgreSQL跑更严格的约束校验，对比两者对相同SQL处理上的差异，帮助很大。
另外，课程官网和公开仓库里有配套的PPT、作业说明、往年考试题。前三讲对应的Project 0虽然没正式发布，但相关的C++基础题目值得先热身。每周群里总有人问“如何入门cmu15445”，我的回复永远是：练，练，练。凡是你觉得自己看懂了，就用代码跑一遍；跑不出来，就是没懂。
5.4 前三讲如何为后续学习铺路
lec4会讲缓冲区池（Buffer Pool），它是整门课的第一道分水岭。lec3的页和文件组织是理解buffer pool的前提。lec5-6讲哈希索引和B+树，它们的存储载体还是页结构。lec7-8讲排序和连接算法，连接算子读取左右子树数据的单位就是页。lec9-10讲查询优化，优化的基础就是关系代数等价变换（lec2埋的点）。至于lec11以后的事务和并发控制，又依赖前面对记录布局和锁的语义的理解。
所以大家在学前三讲时，心里要有路线图：你现在看到的一切“为什么存储要这样设计”，都是后面讨论“怎么加速”和“怎么保证正确”的地基。
6. 对初学者的话：怎么把这一遍学扎实
6.1 我在实际学习中的节奏安排
我自己的试错经验是：不要一晚上连看三讲。前三讲信息密度太高，连看之后大概率只是“听过”。更有效的节奏是：第一遍倍速观看，建立整体框架；第二遍正常速度细看，边看边记笔记；第三遍隔一天后不看视频，自己复述每节课的核心逻辑。
我第一次连看三讲之后，第二天发现连slotted page的槽位数组方向都画反了。后来用“复述法”才真正解决问题。学习这种硬核课程，大脑需要“睡眠巩固”，千万不要图快。
6.2 关于Project 0和动手实验的告诫
虽然前三讲看似没有正式Project，但Andy自己会建议你提前掌握C++的一些基本工具链（CMake、Sanitizer、Google Test）。这些基本功会直接影响后面Project 1的完成速度。我见过不少同学卡在环境配置上，根本不是算法不会，而是不会看CMake输出、不会用ASAN排查内存越界。
给自己定一个小目标：在进入lec4前，能用C++写出一个把任意结构体序列化到固定大小缓冲区、再从缓冲区解析出来的小工具。这样等到Project 1要做Disk Manager时，你的思路会顺很多。
7. 后续内容可以这样扩展
7.1 从前三讲延伸到缓冲区管理
一旦你真正理解了页和槽位，再看Buffer Pool时学生会非常自然：DBMS在内存里维护若干frame，每个frame对应磁盘上的一个page；通过page table记录映射关系；使用clock或LRU策略衡量驱逐哪些页。你会发现lec3是在回答“数据长什么样”，lec4是在回答“数据怎么在内存和磁盘间流动”。
建议学完lec3后先自己写一段伪代码：给定一个页ID，先从page table查它是否在内存中，不在就从磁盘读入，然后计算它内部有没有空闲空间能插入一条记录。这段伪代码写出来，你对后面的并发控制为什么会需要闩锁（latch）也会更有体会。因为多个线程同时读写同一个页时，buffer pool的页就是天然的竞争资源。
7.2 从关系代数延伸到查询优化
lec2学的选择、投影、连接、聚合，刚好是查询优化器做等价变换的最小集合。后面讲启发式优化时，会教你如何把选择尽量下推、把投影尽量下推。如果你没有建立“代数表达式树”的心智模型，优化器就是在黑盒变戏法。所以我把关系代数从“SQL前置知识”提升到了“优化器的母语”这个高度来学。
7.3 从页布局延伸到真实存储引擎的差异
学完前三讲，你可以做一个小调研：对比PostgreSQL（8KB页、堆表、MVCC）和MySQL InnoDB（16KB页、聚簇索引、undo log）在页与记录组织上的关键差异。这比单纯背八股文更有用，面试官如果问你“为什么InnoDB用聚簇索引而PostgreSQL用堆表”，你完全可以从页布局和记录定位方式的角度给出结构性的回答。
我也把这个话题定位成“学完lec3之后最好的延伸讨论”，因为逻辑上，PostgreSQL记录通过（页号，槽号）定位，表本身是一个堆，而InnoDB的主键索引叶子节点直接存放整行记录。这些差异其实就是lec3里“堆文件组织”和“索引组织表”两种思路在工业界的实体化。
在课程里Andy会明确说“我们还没有讲到索引”，所以你现在看到堆组织就可以了。但结合真实数据库对比着看，学习体验会立刻变得立体——这也是为什么我一直强调，课程和工程文档要配合食用，不要只看一边。
