在数据库中保存树形数据（家谱）

Question

我正在尝试存储家谱。我使用的平台是Zend框架、Mysql和Ajax。我在stackoverflow上搜索到了这篇文章，它在处理对象数据方面非常有帮助。 "家谱" 数据结构 简要说明我的用例。用户可以基于数据库中定义的几个关系创建家庭成员或朋友。我还为关系建立了模型。用户可以创建像离婚配偶、朋友等家庭成员。树的最大深度我们假设是孙子女的最大数量，但宽度也可以扩展。兄弟姐妹及其家庭。

我正在寻找一个高效的数据库设计，以减少查询时间。如果我必须使用上述文章中描述的数据结构，则必须将它们保留为模型。

对于表示，我计划使用http://code.google.com/apis/chart/interactive/docs/gallery/orgchart.html#Example的可视化组织图。

我将总结我所需要的内容。

1. 数据库设计
2. 控制器（ajax）和模型的放置
3. 用户创建的人员将不是其他用户，只是其他数据

就这些！当我完成项目时，我会在这个帖子上发布完整的解决方案，当然需要你们的专业知识帮助。

提前感谢您的帮助。

编辑：我会进一步说明我的情况。

我有一个用户表，一个关系表和一个家庭/家谱表。

家庭表必须具有以下类似结构：

ID        userid              relation id             Name

---

1         34                   3 // for son             ABC
2         34                   4 // for Wife            XYZ
3         34                   3 // for Mom             PQR
4         34                   3 // for DAd             THE
5         34                   3 // for Daughter        GHI
6         34                   3 // for Brother         KLM

这种方法的缺点在于需要生成与其他节点（如儿媳、妻子的兄弟及其家庭）的联系。最理想的做法是为每个用户添加父母、兄弟姐妹和孩子，并从家庭成员关系中派生出额外的关系，例如姐夫应作为姐姐的丈夫或妻子的兄弟得出。目前我能想到的就是这些，我只需要实现指南。希望这可以帮助你们提供更好的解决方案。

- SAM

---

不要忘记考虑到乱伦和时间旅行！ - ceejayoz

@ceejayoz 先生，很抱歉我没听懂您的意思。 - SAM

无论你做什么，请确保你能够处理“你自己成为自己的爷爷”的情况。 - Denis de Bernardy

Answer 1

我猜从数据库的角度来看，最好的实现方式应该是：

id | name | parent_male | parent_female

另一个选项是字符串前缀

id | name | prefix 
1  | Joe  | 0001
2  | Jack | 000100001 //ie. Joes son
3  | Marry| 0001 //ie. Jacks mother
4  | Eve  | 0002 // new family tree
5  | Adam | 00020001 // ie. Eves son
6  | Mark | 000200010001 // ie. Adams son

其他（更有效的）算法，如MPTT，假定数据是一棵树，但在这种情况下不是（它有圆圈）。

为了展示它可以工作-选择Mark的祖父母：

--Mark
SELECT prefix FROM family_tree WHERE id = 6; 
-- create substring - trim N 4-character groups from the end where N is N-th parent generation => 2 for grandparent ==> 0002
--grandparents
SELECT * FROM family_tree WHERE prefix = '0002' 
-- same for other side of family
-- cousins from one side of family
SELECT * FROM family_tree WHERE prefix LIKE '0002%' AND LENGTH(prefix) = 12 

- Tomáš Fejfar

---

我不会超过一代，否则你的前缀很快就会变得臃肿。 - peter

我们已经成功地将其用于电子商务类别的四个级别，其中包含数百个类别。这真的没有问题。 - Tomáš Fejfar

还要看你计划保存多少不同的树（这个前缀在一个子树级别中有9999个项目的限制（即您可以拥有9999个不同的家庭），应该足够了。标准varchar（255）可以保存64代...我认为这已经足够好了。 - Tomáš Fejfar

在这里处理成员删除的最佳方式是什么？ - kiranvj

你需要根据预期结果手动实现它。如果删除某人的母亲，会发生什么？孩子也应该被删除吗？如果是这样，那么对于前缀为00020001的母亲，您可以执行DELETE FROM family_tree WHERE prefix LIKE '00020001％'。这将清除已删除人员的所有子项。否则，您可能需要手动更新前缀以适用于不同的人。 - Tomáš Fejfar

或者你选择父级长度为8且子级长度为4的孩子： WHERE prefix LIKE '00020001%' AND LENGTH(prefix) = 12。然后可能会对它们进行一些操作。要更新父级，您需要更新父级前缀的子字符串。因此，要将Adam分配给Marry而不是Eve，您需要将其更新为0001 +“以[length of original parents prefix]字符开头的子字符串”。 - Tomáš Fejfar