产品分类,多级的树状结构的论坛,邮件列表等许多地方我们都会遇到这样的问题:如何存储多级结构的数据?在PHP的应用中,提供后台数据存储的通常是关系 型数据库,它能够保存大量的数据,提供高效的数据检索和更新服务。然而关系型数据的基本形式是纵横交错的表,是一个平面的结构,如果要将多级树状结构存储 在关系型数据库里就需要进行合理的翻译工作。接下来我会将自己的所见所闻和一些实用的经验和大家探讨一下:
层级结构的数据保存在平面的数据库中基本上有两种常用设计方法:
- 毗邻目录模式(adjacency list model)
- 预排序遍历树算法(modified preorder tree traversal algorithm)
我不是计算机专业的,也没有学过什么数据结构的东西,所以这两个名字都是我自己按照字面的意思翻的,如果说错了还请多多指教。这两个东西听着好像很吓人,其实非常容易理解。
简单需求分析:
1.实现无限级分类。
2.实现无限级链接导航
3.实现逐级分类下各条信息的查询,包括最多浏览量,最多评论量,最新信息。
4.随意转移子分类到任何级别而不用修改分类下的信息表
5.使用最少的参数得到所要的信息,URL参数最好只有一个,比如cID=1或者ID=1
6.不管多少级,只有一个PHP文件实现类列表和各种方式的信息调用。
表为两张,一张分类表,一张信息表。
信息表如下:
`ID` int(10) unsigned NOT NULL auto_increment,
`cID` tinyint(3) unsigned NOT NULL default '0',
`title` varchar(255) NOT NULL default 'No Title',
`content` mediumtext NOT NULL,
最简单的无限级分类数据表,只是设置一个parentID来判断父ID
数据表如下:
`cID` tinyint(3) unsigned NOT NULL auto_increment,
`parentID` tinyint(3) unsigned NOT NULL default '0',
`order` tinyint(3) NOT NULL default '0',
`name` varchar(255) NOT NULL default '',
这样可以根据cID = parentID来判断上一级内容,运用递归至最顶层。
缺点是只能查询最小分类下的信息。这样就不能完成需求3、4点,而第二点也勉强符合
第二种方法是设置parentID为varchar类型,将父类id都集中在这个字段里,用符号隔开,比如:1,3,6
这样可以比较容易得到各上级分类的ID,而且在查询分类下的信息的时候,可以使用如:Select * From information Where cID Like "1,3%"。这样能比较好解决需求3。不过在添加分类和转移分类的时候操作将非常麻烦。
我就说到这里,请大家讨论一下如何能够最简单的方法实现无限级分类——考虑性能,代码的简练性,前后台操作的容易性,扩展性!
2、预排序遍历树算法
- --
- -- 表的结构 `category`
- --
- CREATE TABLE IF NOT EXISTS `category` (
- `id` int(11) NOT NULL AUTO_INCREMENT,
- `type` int(11) NOT NULL COMMENT '1为文章类型2为产品类型3为下载类型',
- `title` varchar(50) NOT NULL,
- `lft` int(11) NOT NULL,
- `rgt` int(11) NOT NULL,
- `lorder` int(11) NOT NULL COMMENT '排序',
- `create_time` int(11) NOT NULL,
- PRIMARY KEY (`id`)
- ) ENGINE=InnoDB DEFAULT CHARSET=utf8 AUTO_INCREMENT=10 ;
- --
- -- 导出表中的数据 `category`
- --
- INSERT INTO `category` (`id`, `type`, `title`, `lft`, `rgt`, `lorder`, `create_time`) VALUES
- (1, 1, '顶级栏目', 1, 18, 1, 1261964806),
- (2, 1, '公司简介', 14, 17, 50, 1264586212),
- (3, 1, '新闻', 12, 13, 50, 1264586226),
- (4, 2, '公司产品', 10, 11, 50, 1264586249),
- (5, 1, '荣誉资质', 8, 9, 50, 1264586270),
- (6, 3, '资料下载', 6, 7, 50, 1264586295),
- (7, 1, '人才招聘', 4, 5, 50, 1264586314),
- (8, 1, '留言板', 2, 3, 50, 1264586884),
- (9, 1, '总裁', 15, 16, 50, 1267771951);
现在让我们看一看另外一种不使用递归计算,更加快速的方法,这就是预排序遍历树算法(modified preorder tree traversal algorithm)
这种方法大家可能接触的比较少,初次使用也不像上面的方法容易理解,但是由于这种方法不使用递归查询算法,有更高的查询效率。
我们首先将多级数据按照下面的方式画在纸上,在根节点Food的左侧写上 1 然后沿着这个树继续向下 在 Fruit 的左侧写上 2 然后继续前进,沿着整个树的边缘给每一个节点都标上左侧和右侧的数字。最后一个数字是标在Food 右侧的 18。 在下面的这张图中你可以看到整个标好了数字的多级结构。(没有看懂?用你的手指指着数字从1数到18就明白怎么回事了。还不明白,再数一遍,注意移动你的 手指)。
这些数字标明了各个节点之间的关系,"Red"的号是3和6,它是 "Food" 1-18 的子孙节点。 同样,我们可以看到 所有左值大于2和右值小于11的节点 都是"Fruit" 2-11 的子孙节点