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

Question

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

• moment - 交易发生时的时间戳。
• sequence - 一个数字，用于对发生在完全相同的时刻的交易进行排序。
• description、merchant 等 - 整体信息。
• amount - 交易的货币值(value)，可以是正数也可以是负数。
• balance - 交易后的账户余额(当前和之前所有金额的总和)。这是由系统计算的。

假设用户可以插入、删除或修改非常旧的交易的金额，哪种数据结构经过优化可以快速显示或更新所有交易的正确余额？

我目前的选择是在 B-tree 中组织交易M 的顺序，然后在每个节点上存储 amount 的总和。然后如果更新了一些非常旧的事务，我只更新相应的节点 sum 及其所有父节点到根，这是非常快的。它还允许我通过一次读取根节点来显示总的 balance。然而，为了显示 future 记录的正确 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), (t ₁₅, +77)

最终，当增量列表变大时，您将需要将它应用到您的 B 树。