树状结构的数据表如何设计?

Question

这棵树（非二叉树）是这样的：

• 有唯一根节点
• 每个节点只有一个父节点
• 每个节点有多个子节点

现在我的表是这样的：

node_id node_name parent_id

但是这样的设计，在查询是很麻烦，很难快速的查找某个节点下所有子节点，或者查询这个节点的族谱路径，等等。

在网上找到了【树形结构的数据库表Schema设计】这篇文章，讲的很好，主要思想是为每个节点设置左右值。当时还以为是我要的，但是，后来发现这必须是一棵二叉树，最后还是让我郁闷了。

问题就是有没有更好的设计？

Answer 1

使用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个字段来表达这个树：

1. id，本节点的primary key
2. parent_id，其值为父节点的primary key
3. key，忘了学名叫啥了，你可以称为线索
4. 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的时候，

1. 查找d的所有子孙节点：select * from table_name where key like "${d.key}-${d.id}-%"
2. 查找某个节点的所有子节点：select * from table_name where key like "${d.key}-${d.id}-%" and level=${d.level}+1

这个设计，结构非常简单。key和level是辅助字段，维护这两个字段成本很低，即使全部重建要比MPT简单多了。