无限分类是我们开发中非常常见的应用,像论坛的的版块,CMS的类别,应用的地方特别多。
我们最常见最简单的方法就是在MySql里ID ,parentID,name:
优点是简单,结构简单。
缺点是效率不高,因为每一次递归都要查询数据库,几百条数据库时就不是很快了!
存储树是一种常见的问题,多种解决方案。主要有两种方法:邻接表的模型,并修改树前序遍历算法。
我们将探讨这两种方法的节能等级的数据。我会使用树从一个虚构的网上食品商店作为一个例子。这食品商店组织其食品类,通过颜色和类型。这棵树看起来像这样:
下面我们将用另外一种方法,这就是预排序遍历树算法(modifiedpreordertreetraversalalgorithm)
这种方法大家可能接触的比较少,初次使用也不像上面的方法容易理解,但是由于这种方法不使用递归查询算法,有更高的查询效率。
我们首先将多级数据按照下面的方式画在纸上,在根节点Food的左侧写上1然后沿着这个树继续向下在Fruit的左侧写上2然后继续前进,沿着整个树的边缘给每一个节点都标上左侧和右侧的数字。最后一个数字是标在Food右侧的18。在下面的这张图中你可以看到整个标好了数字的多级结构。(没有看懂?用你的手指指着数字从1数到18就明白怎么回事了。还不明白,再数一遍,注意移动你的手指)。
这些数字标明了各个节点之间的关系,"Red"的号是3和6,它是"Food"1-18的子孙节点。同样,我们可以看到所有左值大于2和右值小于11的节点都是"Fruit"2-11的子孙节点
如图所示:
这样整个树状结构可以通过左右值来存储到数据库中。继续之前,我们看一看下面整理过的数据表。
注意:由于"left"和"right"在SQL中有特殊的意义,所以我们需要用"lft"和"rgt"来表示左右字段。另外这种结构中不再需要"parent"字段来表示树状结构。也就是说下面这样的表结构就足够了。
SELECT * FROM tree WHERE lft BETWEEN 2 AND 11;
看到了吧,只要一个查询就可以得到所有这些节点。为了能够像上面的递归函数那样显示整个树状结构,我们还需要对这样的查询进行排序。用节点的左值进行排序:
SELECT * FROM tree WHERE lft BETWEEN 2 AND 11 ORDER BY lft ASC;
那么某个节点到底有多少子孙节点呢?很简单,子孙总数=(右值-左值-1)/2
descendants=(right–left-1)/2,如果不是很清楚这个公式,那就去翻下书,我们在上数据结构写的很清楚!
添加同一层次的节点的方法如下:
LOCKTABLEnested_categoryWRITE;
SELECT@myRight:=rgtFROMnested_category
WHEREname='Cherry';
UPDATEnested_categorySETrgt=rgt+2WHERErgt>@myRight;
UPDATEnested_categorySETlft=lft+2WHERElft>@myRight;
INSERTINTOnested_category(name,lft,rgt)VALUES('Strawberry',@myRight+1,@myRight+2);
UNLOCKTABLES;
添加树的子节点的方法如下:
LOCKTABLEnested_categoryWRITE;
SELECT@myLeft:=lftFROMnested_category
WHEREname='Beef';
UPDATEnested_categorySETrgt=rgt+2WHERErgt>@myLeft;
UPDATEnested_categorySETlft=lft+2WHERElft>@myLeft;
INSERTINTOnested_category(name,lft,rgt)VALUES('charqui',@myLeft+1,@myLeft+2);
UNLOCKTABLES;
每次插入节点之后都可以用以下SQL进行查看验证:
SELECTCONCAT(REPEAT('',(COUNT(parent.name)-1)),node.name)ASname
FROMnested_categoryASnode,
nested_categoryASparent
WHEREnode.lftBETWEENparent.lftANDparent.rgt
GROUPBYnode.name
ORDERBYnode.lft;
删除节点的方法,稍微有点麻烦是有个中间变量,如下:
LOCKTABLEnested_categoryWRITE;
SELECT@myLeft:=lft,@myRight:=rgt,@myWidth:=rgt-lft+1
FROMnested_category
WHEREname='Cherry';
DELETEFROMnested_categoryWHERElftBETWEEN@myLeftAND@myRight;
UPDATEnested_categorySETrgt=rgt-@myWidthWHERErgt>@myRight;
UPDATEnested_categorySETlft=lft-@myWidthWHERElft>@myRight;
UNLOCKTABLES;
这种方式就是有点难的理解,但是适合数据量很大规模使用,查看所有的结构只需要两条SQL语句就可以了,在添加节点和删除节点的时候略显麻烦,不过相对于效率来说还是值得的,这次发现让我发现了数据库结构真的很有用,但是我在学校学的树基本上都忘记了,这次遇到这个问题才应用到项目中!
参考文章:
http://dev.mysql.com/tech-resources/articles/hierarchical-data.html
http://www.sitepoint.com/article/hierarchical-data-database/3/
分享到:
相关推荐
MySql无限分类结构与数据组树型菜单MySql无限分类结构与数据组树型菜单
分析:通过这种数据库设计出的无限级,可以说读取的时候相当费劲,所以大部分的程序最多3-4级分类,这就足以满足需求,从而一次性读出所有的数据,再对得到数组或者对象进行递归。本身负荷还是没太大问题。但是如果...
我们经常需要在关系型数据库中保存一些树状结构数据,比如分类、菜单、论坛帖子树状回复等。常用的方法有两种: 1. 领接表的方式; 2. 预排序遍历树方式; 假设树状结构如下图: 领接表方式 主要依赖于一个 parent ...
这是一个php无限分类代码,比较完整理包括了数据库是mysql的,有增加、删除、编辑、移动的功能,同时还提供数据库sql表结构。需要的朋友可以参考下,方便大家学习php。
PHP递归写入MySQL无限级分类数据,表结构: CREATE TABLE `kepler_goods_category` ( `id` int unsigned NOT NULL PRIMARY KEY AUTO_INCREMENT, `parentid` int unsigned NOT NULL default 0 comment '父级分类ID...
2014最全的全国省市区mysql数据库,与国家统计局数据同步,46462条,包含简称,地理位置经纬度,无限分类结构,包含港澳台。地区含有经纬度
由于数据的结构简单,所以要将分类的关系由树状显示,我只能想到用递归的方式给于实现,下面是分类数据表结构和自己写的一个树状显示函数,有什么不妥的地方希望大家能指出。 表结构:id字段为分类标识,name字段为...
2014最全的全国省市区mysql数据库,与国家统计局数据同步,邮编,无限分类结构
2014最全的全国省市区mysql数据库,与国家统计局数据同步,46462条,包含简称,地理位置经纬度,无限分类结构,包含港澳台。地区含有经纬度
在本解决方案中,我们将探讨 Java 中的无限层级递归树前后端操作解决方案,解决方案涵盖前端 Vue 无限层级树实现技术大纲、Java 无限递归层级树方案、前端数据结构、MySQL 数据库设计、后端树状接口业务领域模型 DTO...
这款php无限分类代码比较完整理包括了数据库是mysql的,有增加、删除、编辑、移动的功能,同时还提供数据库sql表结构.代码如下: 复制代码 代码如下://连接数据库 $link = mysql_connect(‘localhost’,’root’,”) ...
这篇文章给大家介绍Django中使用 Closure Table 储存无限分级数据,具体内容如下所述: 起步 对于数据量大的情况(比如用户之间有邀请链,有点三级分销的意思),就要用到 closure table 的结构来进行存储。那么在 ...
2017最全的全国省市区mysql数据库,与国家统计局数据同步,包含简称,地理位置经纬度,无限分类结构,包含港澳台。地区含有经纬度
2014最全的全国省市区mysql数据库,与国家统计局数据同步,46593条,包含简称,地理位置经纬度,无限分类结构
最新2018行政区划数据,根据预排序树无限级分类录入,mysql
采集于淘宝手机版,含邮编,无限分类结构。
在该文件中完整的展示了如何利用tp的模型从mysql取得数据,并进行无限分类,最终转换成layui树形组件所需正确格式,当然也添加了一些layui所需的自定义属性(例如:title、spread等),几乎每一行都有注释,也表明了...
3、第三种不是太了解, 好像要使用到算法和数据结构进行排列。 今天我主要分享下第二种方式,一开始也是找了很多资料,确实比较难理解。不过最终还是给搞明白了,因此记下随笔,希望通过这篇文章能够帮助到大家。 ...
大数据时,不再依靠帝国备份王等程序,后台轻松实现海量MySQL数据的备份与恢复。2、实现了多地区城市支持!很多朋友都期待的功能。3、实现了与162100网址导航程序、162100Wap导航(手机版导航)的用户对接,登录后...
全国省市区mysql数据库,与国家统计局数据同步,46462条,包含简称,地理位置经纬度,无限分类结构,包含港澳台。地区含有经纬度