参考资料

PDT 论文1：Positional Update Handling in Column Stores
PDT 论文2：Positional Delta Trees to reconcile updates with
read-optimized data storage

1. 简介

该论文主要是介绍列存系统，如何在线更新数据。论文提出了一个新的数据结构（PDT: Positional Delta Tree）。PDT 的主要目标是在不影响读优化系统的速度（读）优势，支持事务一致性更新。PDT 是存储在内存中的结构。

2. 图例说明

2.1. 名词解释

SID：Stable ID，可以理解为只读存储（read store）的位置ID，但不具备唯一性和升序，只保证不降序。
RID：current Row ID，不唯一，只保证不降序。仅 RID 和 SID 结合起来才是唯一的。
PDT：位置差量树
VALS：值空间
TABLE：等长相关列的集合
tuple：代表一行数据

2.2. 图例

图1是初始状态，TABLE₀持久化存储在磁盘，当前RID 和 SID都是完全相同的。表的主键是 store 和 prod 两列。
图2表示batch₀插入的数据。
图3表示插入操作发生后，PDT 的变化。节点定义如下：

PDT_internal_node {
  sid[F-1],
  delta[F],
  child[F],
  parent
}
PDT_leaf {
  sid[F],
  type[F],
  value[F],
  parent,
  next
}

PDT 是一个类似 B+树的结构，F 是树的度，叶子节点才存放数据（其中，value 字段的 i₀，i₁，i₂，是值空间的地址，见图4）。非叶子节点（这里只有根节点）包含：一个 SID 作为分割键，一个 delta 用于计算 RID <=> SID 的映射（因为插入后，RID 和 SID 不是完全相同，所以需要有个映射关系）。用于分割的 SID 是右子树最小的 SID。插入操作产生的新 SID 都是0（插入数据根据排序规则排在最前面），在PDT 中从左往右的顺序决定了在最后结果中的顺序，见图5 Table₁。delta 的值等于其对应子节点的插入数减去删除数，如果是子节点是非叶子结点，delta 值则等于子节点 delta 值之和。

图4表示值空间的情况。PDT 的叶子节点存了 SID（更新的位置）、更新的类型、指向新 tuple 数据的指针。不同的更新类型（update、insert、delete），有不同的值空间。在之前的插入操作中，仅 insert 的空间有数据。

图6、7、8是在图5 Table₁ 的基础上，执行删除和更新操作。Table₁不是stable 的（没有落盘）。
此处对于 delete 操作就有两种情况。对于删除 Table₀ 中的数据（stable），值空间的 delete 表中有对应的记录，数据其实并没有删除（仅仅置灰，见图9），如(Paris,rug)的删除；对于Table₁（非 stable，数据实际还在值空间 insert 表）的删除，则是直接把值空间中的 insert 表的记录删除掉，如(Berlin,table)的删除。
对于更新操作，每一列在值空间中都有对应的表。如 qty 和 new 分别记录对应列的数据。对于在 PDT 中的数据，则直接修改值空间的值，如(Berlin,cloth,Y,5)。

更准确的说法，对于 PDT 中的记录，删除或者更新都直接操作。