树状结构的数据表如何设计?
这棵树（非二叉树）是这样的：
- 有唯一根节点
- 每个节点只有一个父节点
- 每个节点有多个子节点
现在我的表是这样的：
node_id node_name parent_id
但是这样的设计，在查询是很麻烦，很难快速的查找某个节点下所有子节点，或者查询这个节点的族谱路径，等等。
在网上找到了【 树形结构的数据库表Schema设计 】这篇文章，讲的很好，主要思想是为每个节点设置左右值。当时还以为是我要的，但是，后来发现这 必须 是一棵 二叉树 ，最后还是让我郁闷了。
问题就是有没有更好的设计？
大写的M青年
10 years, 6 months ago
Answers
使用Modified Preorder Tree简直是必须的。网上可以搜一下modified preorder tree travesal找到相关资料。参考 http://www.sitepoint.com/hierarchical...
至于你说的binary tree和general tree的问题，这是个树的基本操作了，互相转换问题不大。参考 http://en.wikipedia.org/wiki/Binary_t...
----------------------
好吧我忘了提一个很dirty的方法。
如果你的树深度是可预期的话，有个超简单的数据结构。你需要3个字段来表达这个树：
- id，本节点的primary key
- parent_id，其值为父节点的primary key
- key，忘了学名叫啥了，你可以称为线索
- level，表示当前节点到根节点的距离
其中，key字段的值为：从跟节点到父节点的primary key，中间用任意非数字符号分割。
例如以下树状结构
├── a │ ├── d │ │ ├── p │ │ ├── q │ │ └── r │ ├── e │ └── f ├── b │ ├── x │ ├── y │ └── z ├── c
对应的数据库表值为：
| id | value | parent_id | key | level | | 1 | a | 0 | "-" | 1 | | 2 | b | 0 | "-" | 1 | | 3 | c | 0 | "-" | 2 | | 4 | d | 1 | "1-" | 2 | | 5 | e | 1 | "1-" | 2 | | 6 | f | 1 | "1-" | 2 | | 7 | x | 2 | "2-" | 2 | | 8 | y | 2 | "2-" | 2 | | 9 | z | 2 | "2-" | 2 | | 10 | p | 4 | "1-4-" | 3 | | 11 | q | 4 | "1-4-" | 3 | | 12 | r | 4 | "1-4-" | 3 |
于是，在给定一个节点d的时候，
-
查找d的所有子孙节点：
select * from table_name where key like "${d.key}-${d.id}-%" -
查找某个节点的所有子节点：
select * from table_name where key like "${d.key}-${d.id}-%" and level=${d.level}+1
这个设计，结构非常简单。key和level是辅助字段，维护这两个字段成本很低，即使全部重建要比MPT简单多了。
yyyyy
answered 10 years, 6 months ago
