闭卷。不保证回忆准确性

1. 五道选择题

   1. pin-count 的意义
   2. 下列索引的表述中正确的一项
      1. 可扩展散列里面没有溢出块
      2. 写为主的负载 B+ 树的中间节点会接近满
      3. 散列索引可以范围查找但是效率低
      4. B+ 树的指针和键值数量固定
   3. 下列日志的表述中正确的一项
      1. 日志只需要记录 DML
      2. Undo 不允许立即更新
      3. Redo 不允许延迟更新
      4. WAL 先写数据再写日志
   4. 估计 IO（查询代价？）时不需要的一项是
      1. CPU 核心数
      2. ……（忘了）
   5. 不是 SSD 上数据库设计新挑战的是
      1. 因为……？，所以传统块的设计不再合适
      2. 因为读写延迟不均衡，传统 IO 代价估计失效
      3. 因为写入寿命，需要重新安排
      4. 因为可以按照字节读写，所以需要优化……？

2. 密集索引和稀疏索引的磁盘块数量范围

3. 根据 SQL 语句写关系代数表达式，并且估计其最后的大小

4. 根据给出的 4 个事务的调度画优先图和多重图，判断是否冲突可串与视图可串

5. 一个 Redo 的数据库，每天 0 点备份（备份时间忽略），每个整点强制 checkpoint，是否能够恢复到过去时间 t 的一致状态？

6. 两个事务的调度（大致的顺序，T1 读取 a，T2 读取 a，T1 写入 a，T2 写入 a，T2 读取 b，T2 写入 b，T1 读取 b，T2 commit，T1 写入 b，T1 abort）

   1. 这个调度有什么问题？
   2. 如果加锁，S 锁读取完成后可以立刻释放，X 锁最后释放（但是在 commit/abort 之前），是否能够避免 a 中的问题？
   3. 如果 2PL 且所有锁必须在 commit/abort 之后释放，是否能够避免 a 中的问题？

7. 改进版的归并排序，计算最小内存、IO 代价，以及使得新版算法优于原版算法的元组大小（如果可以跨块存储）。

   

   ^ 和这个第三小题几乎一致。