Mr Dk.

线程级别并行写入 WAL 日志： 原先 WAL buffer 是全局的，因此写入 WAL 日志时线程间需要做同步。本文提出： 1. 对 WAL buffer 根据 page ID 分多个区，那么线程向不同分区写入时是并行的 2. 维护每个分区中的 LSN 边界 3. 并行的 log writer 异步写入存储 Log writer 在写入日志时，会将每一个 WAL...

Prefetch：当第一个满足条件的 B-Tree 页面被定位时，其后续的兄弟页面有较大可能被需要，因此提前预取可以抹去云存储较高的 I/O 开销。

锁粒度细化：由于云存储的访问延时高，因此持有锁的时间会变长，线程间同步开销更大。因此需要尽量让持有锁的粒度更细，最好能不加锁，这样所有线程可以最大程度并发。 - Shadow page：将索引页面写入存储时，原先是在 I/O 过程中全程持有锁；优化后的思路是先对页面加锁，然后在内存中快速拷贝出一个 shadow page，然后立刻把锁释放掉；后续 I/O 线程把 shadow page 刷回存储就可以了，原先的页面在锁释放后可以继续被其它线程操作 - 索引 SMO 时，parent 节点会加锁阻塞，另外索引上不允许并发的 SMO；优化后的思路是节点分裂过程中不对 parent 节点上排他锁，只对正在分裂的节点和新节点上排他锁；后续释放掉两个新节点的锁，然后重新从根节点开始锁到 parent 节点并使 parent 节点引用分裂出的新节点

数据打散：在分布式存储中，分配 chunk 时放置在相同或不同的节点上有着不同的优势。放在相同节点上，则更省机器；放在不同的节点上，则利用了更多硬件资源，因此组合带宽更高。WAL 日志写入经过分片拆分后可以写入到多个节点上，从而最大化带宽利用。

绕开为单机而设计的缓存：随着 RO 的数量越来越多，维护缓存一致性的代价也越来越高。索性绕开缓存，使用其它手段提升性能，从而使 RO 数量增大时数据库的性能能够 scale。

基于优先级的 I/O 调度。数据库的四种主要的 I/O 类型： - 写日志：第一优先级，因为涉及到事务提交 - 读数据：重要，影响查询性能 - 写数据：可以 delay，慢慢刷脏 - 读日志：只有 recovery 和 replication 的时候才会用到 由于存储层不识别 I/O 的类型，非重要的 I/O 可能会 delay 重要的 I/O。在数据库内需要根据不同类型的 I/O 有不同优先级的队列。 另外由于云存储的单次 block...

几种面向磁盘的存储结构的约定和特点： * B-Tree：以 disk page 为单元的自平衡多叉查找树，多个 search key 的 search value 可以保存在同一个 page 上，按 search key 顺序排列，从而避免节点过多，树过高，在搜索时发生多次 I/O 操作 * B+-Tree：在 B-Tree 的基础上，非叶子节点上只保存 key，只有叶子节点可以保存 value，这样可以让中间层的节点上存放尽可能多的 key，进一步减少节点的数量，避免树过高；对所有 key 的查找都要到达叶子节点，查找代价稳定；另外叶子节点之间用左右指针相连，方便范围查询

索引的搜索和插入可能发生的并发问题： * 进程 1 在父节点上查找到需要搜索的下一层节点 * 进程 2 在下一层节点上进行了插入操作，导致下层节点分裂，索引结构发生了变化 * 进程 1 进入了错误的下一层节点 B-Tree 索引的并发设计经历了锁粒度从粗到细的发展。 锁整个子树？ Lock-coupling: 沿索引的访问节点路径依次加锁，先锁住 parent node，确认要访问的 child node 后，再锁住 child node，访问到 child node 后释放 parent node...

本文提出 B-link-Tree，允许更高的并发性。 引入的修改： 1. 每个节点加入一个 high key 字段，用于表示这个节点子树里的最大 key 值 2. 引入了一个 link pointer，指向右侧隔壁节点；由 B-Tree 的性质可知，右侧隔壁节点的最小 key 值肯定大于 high key 在之前的并发问题中，出现的问题是，由于并发插入引发了 SMO，导致另一个进程查询错子树了，实际上要查询的数据已经在右兄弟子树中。有没有什么办法能够识别出访问错子树了，并且能够修正到正确的子树上去？ 1. high key 可以识别访问错误，如果要查找的 key 已经大于当前节点的 high key...

还需要看下 PostgreSQL 中的 B-Link-Tree 工程实现。