nosql数据库中的树结构

Question

我正在为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

如何设置一个结构既可以提高写入性能,又最重要的是用于阅读？

Answer 1

有许多众所周知的方法可以在数据库中表示树木; 他们每个人都有自己的优点和缺点.这是最常见的:

• 邻接列表,其中每个节点存储其父节点的ID.
• 物化路径,这是Keyur描述的策略.这也是App Engine中的实体组(例如,父实体)使用的方法.它或多或少都是您在更新中描述的内容.
• 嵌套集,其中每个节点具有"左"和"右"ID,以便所有子节点都包含在该范围内.
• 使用根ID进行合并的邻接列表.

每种方法都有其优点和缺点.邻接列表很简单,更新便宜,但需要多个查询来检索子树(每个父节点一个).增强的邻接列表使得可以通过在每个记录中存储根节点的ID来检索整个树.

物化路径易于实现且更新便宜,并且允许查询任意子树,但对深树施加了增加的开销.

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

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