保持余额更新的数字总和的数据结构

Question

我有一个表，其中包含单个帐户的数百万笔交易。每笔交易包含：

• moment—事务发生时的时间戳
• sequence-对发生在完全相同的moment上的事务进行排序的数字
• description、merchant等——整体信息
• amount-交易的货币价值，可以是正的，也可以是负的
• balance-交易后的账户余额（当前和以前所有amount的总和）。这是由系统计算的

假设用户可以插入、删除或修改非常旧的事务的amount，那么为了快速显示或更新所有事务的正确balance，对什么数据结构进行了优化？

我目前的选择是在顺序为M的B树中组织事务，然后在每个节点上存储amount的总和。然后，如果更新了一些非常旧的事务，我只更新相应的节点和它的所有父节点，这是非常快的。它还允许我通过对根节点的一次读取来显示总的balance。然而，为了显示未来记录的正确balance值，我最终需要读取M节点，假设每个节点都在云存储上，这有点慢。

有更好的解决方案吗？

Answer 1

使用B-树的解决方案可能会得到进一步增强。您可以将增量修改的列表存储在RAM中。此列表（也可能是一个二进制树）只包含更新，并按时间戳排序。

例如，这个列表在某个时刻可能看起来如下：

（t₁，+5），（t₁₀、-6），（t₁₅和+80）

这意味着当您需要用时间戳显示交易余额时

• 小于t₁-不执行任何操作
• 介于[t₁，t₁₀之间）-您添加5
• 介于[t₁₀，t₁₅之间）-递减6
• [t₁₅，inf）-加80

现在假设我们需要进行修改（t₂，-3）。我们

1. 将此节点插入列表中的适当位置
2. 使用delta（-3）更新右侧的所有节点
3. 使用来自其左邻居的值更新此节点的值（+5-3=+2）

列表变为：

（t₁，+5），（t₂+2），（t₁₀-9），（特₁₅、+77）

最终，当delta列表变大时，您需要将其应用于B树。