13

我正在为 Google App Engine 开发一个应用程序，它使用 BigTable 作为其数据存储。

这是一个关于协作编写故事的应用程序。这是一个非常简单的爱好项目，我只是为了好玩而工作。它是开源的，你可以在这里看到它：http: //story.multifarce.com/

这个想法是任何人都可以写一个段落，然后需要另外两个人来验证。一个故事也可以在任何段落中分支，以便故事的另一个版本可以向另一个方向继续。

想象一下下面的树结构：

每个数字都是一个段落。我希望能够选择每个独特故事情节中的所有段落。基本上，那些独特的故事情节是（2、7、2）；(2, 7, 6, 5); (2, 7, 6, 11) 和 (2, 5, 9, 4)。忽略节点“2”出现了两次，我只是从维基百科上拿了一张树状结构图。

我还绘制了一个建议解决方案的图表：https ://docs.google.com/drawings/edit?id=1fdUISIjGVBvIKMSCjtE4xFNZxiE08AoqvJSLQbxN6pc&hl=en

我怎样才能建立一个结构对写作来说是高效的，但最重要的是阅读？

4

2 回答 2

16

有许多众所周知的方法来表示数据库中的树。他们每个人都有自己的优点和缺点。以下是最常见的：

  • 邻接列表，每个节点存储其父节点的 ID。
  • 物化路径，这是 Keyur 描述的策略。这也是 App Engine 中的实体组（例如父实体）使用的方法。这也或多或少是您在更新中描述的内容。
  • 嵌套集，其中每个节点都有“左”和“右”ID，因此所有子节点都包含在该范围内。
  • 与根 ID 关联的邻接列表。

这些中的每一个都有其自身的优点和缺点。邻接表很简单，更新成本低，但需要多次查询来检索子树（每个父节点一个）。增强的邻接表可以通过在每条记录中存储根节点的 ID 来检索整个树。

物化路径易于实现且更新成本低廉，并允许查询任意子树，但会增加深度树的开销。

嵌套集更难实现，并且每次插入时平均需要更新一半的节点。它们允许您查询任意子树，而不会增加具体化路径的密钥长度问题。

但是，在您的特定情况下，您似乎根本不需要树结构：每个故事，尽管可能是原始故事，但都是独立的。我建议有一个“故事”模型，其中包含其段落的键列表（例如，在 Python 中为 db.ListProperty(db.Key)）。要渲染一个故事，您需要获取故事，然后对所有段落进行批量获取。要分支故事，只需复制故事条目 - 保持对段落的引用不变。

于 2010-07-20T09:05:30.230 回答
0

我能想到的一种解决方案是——节点的路径也是该节点的关键。所以节点 11 的键是“2/7/6/11”。您可以通过对路径中所有键的简单键查找来遍历路径 - “2/7/6/11”、“2/7/6”、“2/7”、“2”

于 2010-07-19T18:54:07.127 回答