第 8 章 · 03 数据的插入与查询

第 8 章 · 03 数据的插入与查询

本节摘要:前两节讲了页式存储与 B+树索引,本节把它们合起来——实现数据库的基础 CRUD:插入(找该去的页、写记录、必要时分裂、维护索引)、按主键查(沿 B+树找叶子)、范围查(沿叶子链表)。这一节让你的数据库「能存能取」,完成最小可用。

内容来源:基于数据库实现整理的导读。

学习目标

1. 实现插入:找叶子页→写记录→满则分裂→维护索引。
2. 实现按主键等值查询:沿 B+树到叶子。
3. 实现范围查询:沿叶子链表遍历。
4. 理解「聚簇索引」下数据与索引的关系。

一、学习价值:CRUD 是数据库的「能跑」标志

前两节是「零件」,本节是「组装」。组装后,数据库具备了「存数据、查数据」的最小能力——虽然还不支持 SQL、没有事务,但能增删查改,就是个能跑的存储引擎了。本节呼应姊妹篇《Linux 命令》第 3 章 awk 的「按列统计」——这里是从存储层支撑这类查询。

二、子系统拆解

插入

1. 按「主键」沿 B+树找到对应叶子页
2. 在该页写入记录(键→数据)
3. 若页满:
   a. 分裂:取半键建新页
   b. 中间键上推到父节点
   c. 父满则递归分裂, 可能到根
4. 更新空闲页管理
​

等值查询(WHERE id = 42)

1. 沿 B+树:从根开始, 按键比较, 找到 42 该去的子节点
2. 到叶子页, 在页内找键 42
3. 找到→返回数据; 没找到→空
​

B+树让等值查询是 O(log n)——几层 IO 就定位,远快于全表扫描。

范围查询(WHERE id BETWEEN 10 AND 50)

1. 沿 B+树找到 id=10 的叶子页
2. 沿叶子链表向后遍历, 收集键在 [10,50] 的记录
3. 直到键 > 50 停止
​

叶子链表是 B+树相对 B-树的关键优势——范围查询顺序扫描,极高效。

删除(简述)

找到记录→从页删除。页可能变稀疏,可能触发页合并(相邻页都很稀疏时合并)——这是 B+树的对称操作,实现复杂度类似页分裂。第一个迷你数据库可简化(只标记删除,定期整理)。

三、上手第一步

1. 实现等值查询(沿树找叶子,页内查找)。
2. 实现插入(找叶子、写记录、暂不处理分裂,先小数据)。
3. 加页分裂(数据量大时)。
4. 实现范围查询(叶子链表)。

本节要点回顾

1. 插入:沿树找叶子页→写记录→满则分裂→上推。
2. 等值查询:沿树到叶子,O(log n);远快于全表扫描。
3. 范围查询:找到起点叶子,沿叶子链表扫描。
4. B+树叶子链表是范围查询高效的根基(相对 B-树的优势)。
5. 删除:找记录删,页稀疏可合并(复杂,迷你库可简化)。

推荐上手顺序

1. 等值查询(先读后写,简单)。
2. 插入(小数据,暂不分裂)。
3. 加页分裂(数据增长后)。
4. 范围查询(叶子链表)。
5. 下一节:WAL 保证持久性。

下一节讲预写日志(WAL)——怎么保证不丢数据。