这棵树(非二叉树)是这样的:
- 有唯一根节点
- 每个节点只有一个父节点
- 每个节点有多个子节点
现在我的表是这样的:
node_id node_name parent_id
但是这样的设计,在查询是很麻烦,很难快速的查找某个节点下所有子节点,或者查询这个节点的族谱路径,等等。
在网上找到了【树形结构的数据库表Schema设计】这篇文章,讲的很好,主要思想是为每个节点设置左右值。当时还以为是我要的,但是,后来发现这必须是一棵二叉树,最后还是让我郁闷了。
问题就是有没有更好的设计?
这棵树(非二叉树)是这样的:
现在我的表是这样的:
node_id node_name parent_id
但是这样的设计,在查询是很麻烦,很难快速的查找某个节点下所有子节点,或者查询这个节点的族谱路径,等等。
在网上找到了【树形结构的数据库表Schema设计】这篇文章,讲的很好,主要思想是为每个节点设置左右值。当时还以为是我要的,但是,后来发现这必须是一棵二叉树,最后还是让我郁闷了。
问题就是有没有更好的设计?
你找到的这篇文章即是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没毕业,还是实习生,就有这样独特的思路并运用到商业产品中,思考能力和工程能力可见一斑。
所以,我的结论是:
感谢 @yegle @qinjianxiang
最后采用了把 general tree 转为 binary tree,然后在用左右值这个方法
表结构为
node_id node_name node_parent_id left right
这样应该比原有单纯的通过父节点 id 递归查询效率高多了,权衡插入更新操作不会很多,主要是查询,所以这样应该没问题了。
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;
可以考虑加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了。
6 回答1.3k 阅读✓ 已解决
4 回答1.7k 阅读
2 回答2.2k 阅读
2 回答1.3k 阅读
1 回答916 阅读✓ 已解决
1 回答886 阅读✓ 已解决
2 回答1.5k 阅读
使用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个字段来表达这个树:
其中,key字段的值为:从跟节点到父节点的primary key,中间用任意非数字符号分割。
例如以下树状结构
对应的数据库表值为:
于是,在给定一个节点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简单多了。