实验二要求实现一个数据结构 ：B+树。

实验难点在于理清B+树存储结构、插入分裂、删除合并以及并发控制。

强烈建议阅读教材给出的B+树执行流程的伪代码。

本节课首先介绍B+树索引，然后介绍B+树的设计，最后介绍B+树的优化措施。

实验零要求实现一个数据结构：前缀树。适合复习CPP以及适应实验代码环境。

实验一要求实现一个缓冲池实例，包括动态扩张的哈希表、基于LRU-K的替换器。

动态哈希表的难点在于理清数据结构，数据插入与扩容过程，不要求缩容。

LRU-K的实现比较坑，如果没有理解替换器与缓冲池整体的关系，也就很难理解各个函数的实现。

建议看教材：Database System Concepts 里面讲得比较清晰。

哈希表具有无法比拟的常数查询性能，是数据库的常用查询数据结构。

本节课探讨了静态哈希与动态扩容的哈希。动态扩容包括链式哈希、extendible hash以及线性哈希。

哈希表能较好应对多次点查询，但无法较好应对范围查询。

存储-2

How the DBMS manages its memory and move data back-and-forth from disk.

DBMS是怎么管理其内存的，怎么与硬盘交互的（包括加载和写数据）。

本节课主要介绍缓存池的加载策略、替换策略。

存储-1

How the DBMS represents the database in files on disk.

DBMS是怎么在底层表示数据的？

本节融合了三节课内容，主要是数据库底层存储的表现，讨论了页中tuple的存储模型，包括两种类型基于tuple和基于log。讨论了具体的数据表示，系统元数据。最后介绍OLTP和OLAP，对应的行存储和列存储优缺点。简单介绍了数据压缩方法。

本节课主要介绍数据库系统的一些概念以及SQL语句。

前缀和与差分都是数组的重要技巧。

论文材料： https://pdos.csail.mit.edu/6.824/papers/spanner.pdf

Spanner是谷歌公司研发的、可扩展的、多版本、全球分布式、同步复制数据库。它是第一个吧数据分布在全球范围内的系统，并且支持外部一致性的分布式事务。Spanner实现了一个强大的时间API，用于实现非阻塞的读、不采用锁机制的只读事务和原子模式变更。

Spanner论文比较复杂，这里我结合课程，只重点讲述如何利用时间API完成分布式事务，包括读写事务和只读事务。

1
2

http://loopjump.com/google_spanner/
十问Spanner https://zhuanlan.zhihu.com/p/47870235