使用B+trees和快照隔离实现范围查询

Question

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

Answer 1

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

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

Answer 2

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

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