CaltechCS122 笔记：Assignment 1: NanoDB Set-Up and Storage Layer
Assignment 1: NanoDB Set-Up and Storage Layer
NanoDB 是加州理工大学 Caltech CS122 课程使用的教学数据库系统
buffer pool manager
lab1 的第二部分是实现充分利用空间的 bpm，当前所给出的 bpm 代码 pin/unpin 的调用存在问题，当进行大规模数据的 insert 操作时，会出现空间不够用的问题。
getFirstTuple 方法：在文件中找出第一个 tuple，并构造 HeapFilePageTuple 对象。
需要 unpin 的几个部分
- HeaderPage
- QueryPlan 处理完的 tuple
- 在 SelectNode 中不满足 predicate 的 tuple
修改
- HeapFileManager
- HeaderPage
- DataPage
Insert 性能优化
当前 Insert 的执行流程
- 从 PageNo = 1 的 page 开始寻找能容纳当前 tupleSize 的 datapage
- 在 datapage 中，从 slot0 开始，寻找合适的插入位置。
由上述流程可知，其 insert 操作的时间复杂度为 O(n^2)
storageManager.loadDBPage()
使用这个方法，可以得到给定 PageNode 的 dbPage，因此我们可以在 loadDBPage 方法的外面来设计数据结构，让其能够直接找到拥有空闲空间的 dbPage。
DataPage 在文件中的结构
File and Offset
File.Seek(pageNo)
当我们拥有了 pageNo 后，用过 seek 方法，可以定位到 pageNode 后，通过 seek 方法，可以定位到 pageNo 在文件中的位置。
dataPage address = pageNo * pageSize;
DataStruct
如图所示，我们可以在每个 datapage 的结尾预留 2 个 bytes 的空间来存储当前 dataPage 的 freeSpace 的大小。
- 因此，每个 page 的 getTupleEnd 的值要 -2
- 与此同时，当我们插入 tuple 时，还要更新此 DataPage 的空闲空间记录区域的值。
- 当删除 tuple 时，也要更新空闲空间记录区域的值。
- 当初始化一个 datapage 时，空闲空间记录区域的值也要进行初始化。
所以当初始化一个 DataPage 时，其大小初始化为 8192 - 4，即每个 page 的前后 2 个 byte 都不需要使用。
Find DataPage
现在即使存储了每个 page 的空闲空间的大小，在 insert 的过程中，还是会要遍历每个 page 到内存，所以为了提高 insert 的执行效率，应尽量减少从磁盘读 page 的次数。
为了加速 insert 的速度， side 中给出了 2 种方法 ：1. List of Non-Fill Blocks 2. Free-Space Bitmap
实现 SQL 中的 update语句和 delete 语句
首先进行 update 语句代码的调试
- update 语句
update tablename set column=value
where clause
value 值可以是 NULL，也可以是 int，float 这样的定长数据类型，或者 varchar 这样的变长数据类型。
从单元测试入手，在 TestHeapFileFormat.java 文件的 TestUpdate 方法开始调试。
由代码可以看出，对 value 值，null 和非 null 是分开处理的：
Page 的结构如下图所示：
update value 为 null
- 对 column_idx 所指定的 column 设置 null 值
如果该 column 本身就是 null 值，直接返回，如果本身的 column 不为 null 值。需要进行如下的处理：
- 将 tuple 中的 bitmap 中该列的标识置为空。
- 删除该列的数据（会对数据进行移动）
- 更新 valueOffset 的内容
update value 为非 null
当进行 update 时，如果 set 的值为非 null，需要考虑以下几个方面：
- 原来的列是一个空值，和原来的列是一个变长值
- 原来的列是一个非空值，且是一个定长的数据类型
对于第一种情况，处理流程如下：
- 分配一块空间在 datapage 中
- 调用 writeNonNullValue 方法
- 更新相关的数据结构
对于第二种情况，直接调用 writeNonNullValue 即可。
对于空间的开辟
- 当原值为 NULL 时需要开辟新的空间
- 当原值为 varchar 且空间不够时需要开辟新的空间，当空间多出来的时候，需要回收空间。