database - 使用 B+树和快照隔离实现范围查询

Question

我正在开发一个新的 NoSQL 数据库服务器产品。有没有关于如何在使用快照隔离的集群 B+ 树上实现范围查询的论文？

Answer 1

我已经编写了几个 B+tree 实现。对于范围查询，您将光标移动到具有范围下限的键，然后“向右移动”直到到达上限。B+-link 树（在叶节点之间有左/右指针）使这变得非常简单。

但是，我从未实现过快照隔离。我认为这在很大程度上取决于您的隔离算法。如果您使用影子页面（为每个事务创建修改页面的副本），那么您必须在沿叶节点“向右移动”之前检查是否存在影子页面。

Answer 2

您可以为每一行添加一个名为“RowVersion”的隐藏列。每当您更新一行时，您都会插入一个新行，并将 RowVersion 更新为当前事务编号。阅读时，您选择具有> = 比您的事务编号的最低版本的行。您还需要某种清理任务。

您还可以将行版本存储在不同的位置。它不必在同一个 B 树中。您可以将它们保存在 RAM 中或在服务器重新启动时重新创建的临时数据库中。