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

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简单多了。

Answer 2

你找到的这篇文章即是yegle提到的Modified Preorder Tree。
我在2006年实践过，它的优点是查询非常高效，缺点是理解起来不那么直观，写操作麻烦。

当年，我在小白板上跟@joyqi等人举例讲这个结构，讲左右值的时候讲不下去了，后来joyqi发明了他的星际算法，即为每个元素定义(x,y)值，x表示往右的偏移，y表示往下的偏移，整个树的根结点是(0,0)。这种树结构最大的优点是理解非常直观（想象一下windows资源管理器左侧的目录树），非常适合网页前端的树形展示（类目树，评论嵌套）。缺点也是明显的，那就是在SQL的层面，无法像Modified Preorder Tree一样一条语句搞定所有子节点查询和族谱查询，需要有专门的API来操纵它，我们在kiwiphp里专门写了一个DbTableTree Class来实现树结构的维护，后来由于实用性的缘故慢慢放弃了，使用最老套的parent_node/root node的方式了。

ps:当年joyqi没毕业，还是实习生，就有这样独特的思路并运用到商业产品中，思考能力和工程能力可见一斑。

所以，我的结论是：

1. 最常用，写操作最简单的就是node_id, parent_node_id这种结构，如果业务限定了树结构的变化频度，可适当加一些root_node_id, parent_path之类的冗余字段提升性能，降低查询编码复杂度
2. Modified Preorder Tree是优秀的树结构设计了，它有效地消除了上面这种算法在查询所有子节点和族谱路径时的递归，只是写操作会麻烦很多很多。这似乎是不可调和的，凡是消除了递归的，好像写操作都会很麻烦。
3. 不明白binary tree怎么让你郁闷了。实在不喜欢binary tree，可以自己根据Modified Preorder Tree的精要设计一个“每个节点可以拥有大于2个子节点”的树结构，就像B-Tree,四叉最小堆

Answer 3

建议参考树的 左孩子右兄弟 的表示方法，可以为每个节点保存一个孩子一个兄弟

Answer 4

感谢 @yegle @qinjianxiang

最后采用了把 general tree 转为 binary tree，然后在用左右值这个方法
表结构为

node_id node_name node_parent_id left right

这样应该比原有单纯的通过父节点 id 递归查询效率高多了，权衡插入更新操作不会很多，主要是查询，所以这样应该没问题了。

Answer 5

CREATE TABLE `sns_tags_tree_tbl` (
  `id` int(10) unsigned NOT NULL DEFAULT '0',
  `pid` int(10) unsigned DEFAULT '0',
  `tree_root` int(10) unsigned DEFAULT '0',
  `tree_level` tinyint(3) unsigned DEFAULT '0',
  PRIMARY KEY (`id`),
  KEY `pid` (`pid`,`tree_root`,`tree_level`)
) ENGINE=MyISAM DEFAULT CHARSET=utf8;

Answer 6

可以考虑加3个字段。

arr_parent_id varchar(255) NOT NULL COMMENT '所有父id',
has_child tinyint(1) NOT NULL COMMENT '是否存在子栏目，1，存在',
arr_child_id varchar(255) NOT NULL COMMENT '所有子栏目id',

配合上你的node_id node_name parent_id 就成了

node_id node_name parent_id arr_parent_id has_child arr_child_id

arr_parent_id 中用符号分割他所有父分类id 例如 1-6-14-35
arr_child_id 同理

这样子， 你在业务逻辑里面就不需要弄那么复杂的查询了。

只是在添加，修改这个表的时候， 用递归 维护好这个字段就ok了。

Answer 7

MPT 算法好用。

Answer 8

进来看的朋友可以看看这篇文章

Ajax技术与路径存储法在树形结构中的整合研究

Answer 9

介绍一下我发现的一种另类的树形结构存储方法，利用很多数据库列存一个占位符(有限深度树):

改进版是只用一个列存深度等级(无限深度树)，建议用后者:

详见 http://drinkjava2.iteye.com/b... ,优点是所见即所得，SQL查/插/删/操作方便，缺点是节点移动麻烦