- 浏览: 803603 次
- 性别:
- 来自: 南京
文章分类
最新评论
-
xieye:
jetty插件有好几个版本,1.6,1.7,1.8
我选的是用 ...
tapestry入门(翻译)3 导入项目到eclipse -
xieye:
还有,
注:第2部分时,需要先安装jetty,我自己在安装过程 ...
tapestry入门(翻译)3 导入项目到eclipse -
xieye:
说明一下:实际使用中,导入时我并没有错误。2、我把eclips ...
tapestry入门(翻译)3 导入项目到eclipse -
xieye:
其实还是有一些先决条件的。1是外部环境,2是进步是阶段性的(意 ...
(转载文章)如何愉悦起来:一位精神治疗师的见解 -
mandy_yanzi:
我都已经饿7天了坚持为了我的衣衣
身体健康的问题
原文:
http://be-evil.org/post-168.html
本文是我学习MySQL官方教程Managing Hierarchical Data in MySQL的笔记
多层数据结构估计所有的web开发者估计都不会陌生,各种软件的分类都是基于多层结构来设计的。
下面是一个典型的多层数据结构示意图:
点击查看原图
相关创建数据语句:
CREATE TABLE category(
category_id INT AUTO_INCREMENT PRIMARY KEY,
name VARCHAR(20) NOT NULL,
parent INT DEFAULT NULL);
INSERT INTO category
VALUES(1,'ELECTRONICS',NULL),(2,'TELEVISIONS',1),(3,'TUBE',2),
(4,'LCD',2),(5,'PLASMA',2),(6,'PORTABLE ELECTRONICS',1),
(7,'MP3 PLAYERS',6),(8,'FLASH',7),
(9,'CD PLAYERS',6),(10,'2 WAY RADIOS',6);
SELECT * FROM category ORDER BY category_id;
在这种数据结构中,各层之间通过字段 parent 来形成邻接表,我们查询某些层级的关系的时候一般都是通过递归的方式,遍历某个层级关系的SQL的查询次数会顺着层级的增加,想想在层级有20的时候,根据某个底层节点取它到顶层节点的查询次数吧。
为了解决这个问题,人们想出了嵌套集模型(The Nested Set Model),请看下图:
点击查看原图
上图依然是表现的与图一相同的层级关系,但是却更换了一种表现形式 下面是新的关系表和数据(关系和数据与之前相同,但是表结构不一样):
CREATE TABLE nested_category (
category_id INT AUTO_INCREMENT PRIMARY KEY,
name VARCHAR(20) NOT NULL,
lft INT NOT NULL,
rgt INT NOT NULL
);
INSERT INTO nested_category
VALUES(1,'ELECTRONICS',1,20),(2,'TELEVISIONS',2,9),(3,'TUBE',3,4),
(4,'LCD',5,6),(5,'PLASMA',7,8),(6,'PORTABLE ELECTRONICS',10,19),
(7,'MP3 PLAYERS',11,14),(8,'FLASH',12,13),
(9,'CD PLAYERS',15,16),(10,'2 WAY RADIOS',17,18);
SELECT * FROM nested_category ORDER BY category_id;
这里将 left,right 修改为 lft,rgt因为这两个词在MYSQL中属于关键字 下面我们将插入的数据标识在图上: 点击查看原图
同样,我们将数据标识在原来的结构上:
点击查看原图
怎么样,是不是很明确了
下面使我自己标定一种形式,方便理解
[1
[2
[3 4]
[5 6]
[7 8]
9]
[10
[11
[12 13]
14]
[15 16]
[17 18]
19]
20]
遍历整个树,查询子集 条件:左边 > 父级L, 右边 < 父级R
SELECT node.name
FROM nested_category AS node,
nested_category AS parent
WHERE node.lft BETWEEN parent.lft AND parent.rgt
AND parent.name = 'ELECTRONICS'
ORDER BY node.lft;
+----------------------+
| name |
+----------------------+
| ELECTRONICS |
| TELEVISIONS |
| TUBE |
| LCD |
| PLASMA |
| PORTABLE ELECTRONICS |
| MP3 PLAYERS |
| FLASH |
| CD PLAYERS |
| 2 WAY RADIOS |
+----------------------+
- 查询所有无分支的节点 条件:右边 = 左边L + 1
SELECT name
FROM nested_category
WHERE rgt = lft + 1;
- 查询某个字节点到根节点的路径
SELECT parent.name
FROM nested_category AS node,
nested_category AS parent
WHERE node.lft BETWEEN parent.lft AND parent.rgt
AND node.name = 'FLASH'
ORDER BY parent.lft;
SELECT node.name, (COUNT(parent.name) - 1) AS depth
FROM nested_category AS node,
nested_category AS parent
WHERE node.lft BETWEEN parent.lft AND parent.rgt
GROUP BY node.name
ORDER BY node.lft;
- 查询子节点的深度
SELECT node.name, (COUNT(parent.name) - (sub_tree.depth + 1)) AS depth
FROM nested_category AS node,
nested_category AS parent,
nested_category AS sub_parent,
(
SELECT node.name, (COUNT(parent.name) - 1) AS depth
FROM nested_category AS node,
nested_category AS parent
WHERE node.lft BETWEEN parent.lft AND parent.rgt
AND node.name = 'PORTABLE ELECTRONICS'
GROUP BY node.name
ORDER BY node.lft
)AS sub_tree
WHERE node.lft BETWEEN parent.lft AND parent.rgt
AND node.lft BETWEEN sub_parent.lft AND sub_parent.rgt
AND sub_parent.name = sub_tree.name
GROUP BY node.name
ORDER BY node.lft;
- 插入新节点
算法详解:
1.所有分类 左边和右边的值 > 插入节点的左边节点记录的右值 的全部 + 2
2.插入节点 左值 = 插入位置左边节点记录的右值 + 1, 右值 = 插入位置左边节点记录的右值 + 2
例子:
在 R = 9(L8, R9)与 L = 10(L10,R11) 节点之间插入一个新节点
那么所有 左值 和 右值 > 9 的节点的左值和右值需要 + 2
例如新节点右边的节点(L10,R11)左值右值都需要 + 2 那么插入后的新值为 L12 R13
新节点的左值为 9 + 1 = 10 右值为 9 + 2 = 11
SQL语句实现
LOCK TABLE nested_category WRITE;
SELECT @myRight := rgt FROM nested_category
WHERE name = 'TELEVISIONS';
UPDATE nested_category SET rgt = rgt + 2 WHERE rgt > @myRight;
UPDATE nested_category SET lft = lft + 2 WHERE lft > @myRight;
INSERT INTO nested_category(name, lft, rgt) VALUES('GAME CONSOLES', @myRight + 1, @myRight + 2);
UNLOCK TABLES;
- 删除新节点
删除节点的算法与添加一个节点的算法相反
删除一个没有子节点的节点
LOCK TABLE nested_category WRITE;
SELECT @myLeft := lft, @myRight := rgt, @myWidth := rgt - lft + 1
FROM nested_category
WHERE name = 'GAME CONSOLES';
DELETE FROM nested_category WHERE lft BETWEEN @myLeft AND @myRight;
UPDATE nested_category SET rgt = rgt - @myWidth WHERE rgt > @myRight;
UPDATE nested_category SET lft = lft - @myWidth WHERE lft > @myRight;
UNLOCK TABLES;
删除一个分支节点和它所有的子节点
LOCK TABLE nested_category WRITE;
SELECT @myLeft := lft, @myRight := rgt, @myWidth := rgt - lft + 1
FROM nested_category
WHERE name = 'MP3 PLAYERS';
DELETE FROM nested_category WHERE lft BETWEEN @myLeft AND @myRight;
UPDATE nested_category SET rgt = rgt - @myWidth WHERE rgt > @myRight;
UPDATE nested_category SET lft = lft - @myWidth WHERE lft > @myRight;
UNLOCK TABLES;
删除一个节点后移动其字节点到
LOCK TABLE nested_category WRITE;
SELECT @myLeft := lft, @myRight := rgt, @myWidth := rgt - lft + 1
FROM nested_category
WHERE name = 'PORTABLE ELECTRONICS';
DELETE FROM nested_category WHERE lft = @myLeft;
UPDATE nested_category SET rgt = rgt - 1, lft = lft - 1 WHERE lft BETWEEN @myLeft AND @myRight;
UPDATE nested_category SET rgt = rgt - 2 WHERE rgt > @myRight;
UPDATE nested_category SET lft = lft - 2 WHERE lft > @myRight;
UNLOCK TABLES;
总结:
预排序遍历树算法的核心就是牺牲了写的性能来换取读取的性能
在你的开发的应用遇到此类问题的时(读压力 > 写压力),尝试下使用预排序遍历树算法来提高你的程序的性能吧。
http://be-evil.org/post-168.html
本文是我学习MySQL官方教程Managing Hierarchical Data in MySQL的笔记
多层数据结构估计所有的web开发者估计都不会陌生,各种软件的分类都是基于多层结构来设计的。
下面是一个典型的多层数据结构示意图:
点击查看原图
相关创建数据语句:
CREATE TABLE category(
category_id INT AUTO_INCREMENT PRIMARY KEY,
name VARCHAR(20) NOT NULL,
parent INT DEFAULT NULL);
INSERT INTO category
VALUES(1,'ELECTRONICS',NULL),(2,'TELEVISIONS',1),(3,'TUBE',2),
(4,'LCD',2),(5,'PLASMA',2),(6,'PORTABLE ELECTRONICS',1),
(7,'MP3 PLAYERS',6),(8,'FLASH',7),
(9,'CD PLAYERS',6),(10,'2 WAY RADIOS',6);
SELECT * FROM category ORDER BY category_id;
在这种数据结构中,各层之间通过字段 parent 来形成邻接表,我们查询某些层级的关系的时候一般都是通过递归的方式,遍历某个层级关系的SQL的查询次数会顺着层级的增加,想想在层级有20的时候,根据某个底层节点取它到顶层节点的查询次数吧。
为了解决这个问题,人们想出了嵌套集模型(The Nested Set Model),请看下图:
点击查看原图
上图依然是表现的与图一相同的层级关系,但是却更换了一种表现形式 下面是新的关系表和数据(关系和数据与之前相同,但是表结构不一样):
CREATE TABLE nested_category (
category_id INT AUTO_INCREMENT PRIMARY KEY,
name VARCHAR(20) NOT NULL,
lft INT NOT NULL,
rgt INT NOT NULL
);
INSERT INTO nested_category
VALUES(1,'ELECTRONICS',1,20),(2,'TELEVISIONS',2,9),(3,'TUBE',3,4),
(4,'LCD',5,6),(5,'PLASMA',7,8),(6,'PORTABLE ELECTRONICS',10,19),
(7,'MP3 PLAYERS',11,14),(8,'FLASH',12,13),
(9,'CD PLAYERS',15,16),(10,'2 WAY RADIOS',17,18);
SELECT * FROM nested_category ORDER BY category_id;
这里将 left,right 修改为 lft,rgt因为这两个词在MYSQL中属于关键字 下面我们将插入的数据标识在图上: 点击查看原图
同样,我们将数据标识在原来的结构上:
点击查看原图
怎么样,是不是很明确了
下面使我自己标定一种形式,方便理解
[1
[2
[3 4]
[5 6]
[7 8]
9]
[10
[11
[12 13]
14]
[15 16]
[17 18]
19]
20]
遍历整个树,查询子集 条件:左边 > 父级L, 右边 < 父级R
SELECT node.name
FROM nested_category AS node,
nested_category AS parent
WHERE node.lft BETWEEN parent.lft AND parent.rgt
AND parent.name = 'ELECTRONICS'
ORDER BY node.lft;
+----------------------+
| name |
+----------------------+
| ELECTRONICS |
| TELEVISIONS |
| TUBE |
| LCD |
| PLASMA |
| PORTABLE ELECTRONICS |
| MP3 PLAYERS |
| FLASH |
| CD PLAYERS |
| 2 WAY RADIOS |
+----------------------+
- 查询所有无分支的节点 条件:右边 = 左边L + 1
SELECT name
FROM nested_category
WHERE rgt = lft + 1;
- 查询某个字节点到根节点的路径
SELECT parent.name
FROM nested_category AS node,
nested_category AS parent
WHERE node.lft BETWEEN parent.lft AND parent.rgt
AND node.name = 'FLASH'
ORDER BY parent.lft;
SELECT node.name, (COUNT(parent.name) - 1) AS depth
FROM nested_category AS node,
nested_category AS parent
WHERE node.lft BETWEEN parent.lft AND parent.rgt
GROUP BY node.name
ORDER BY node.lft;
- 查询子节点的深度
SELECT node.name, (COUNT(parent.name) - (sub_tree.depth + 1)) AS depth
FROM nested_category AS node,
nested_category AS parent,
nested_category AS sub_parent,
(
SELECT node.name, (COUNT(parent.name) - 1) AS depth
FROM nested_category AS node,
nested_category AS parent
WHERE node.lft BETWEEN parent.lft AND parent.rgt
AND node.name = 'PORTABLE ELECTRONICS'
GROUP BY node.name
ORDER BY node.lft
)AS sub_tree
WHERE node.lft BETWEEN parent.lft AND parent.rgt
AND node.lft BETWEEN sub_parent.lft AND sub_parent.rgt
AND sub_parent.name = sub_tree.name
GROUP BY node.name
ORDER BY node.lft;
- 插入新节点
算法详解:
1.所有分类 左边和右边的值 > 插入节点的左边节点记录的右值 的全部 + 2
2.插入节点 左值 = 插入位置左边节点记录的右值 + 1, 右值 = 插入位置左边节点记录的右值 + 2
例子:
在 R = 9(L8, R9)与 L = 10(L10,R11) 节点之间插入一个新节点
那么所有 左值 和 右值 > 9 的节点的左值和右值需要 + 2
例如新节点右边的节点(L10,R11)左值右值都需要 + 2 那么插入后的新值为 L12 R13
新节点的左值为 9 + 1 = 10 右值为 9 + 2 = 11
SQL语句实现
LOCK TABLE nested_category WRITE;
SELECT @myRight := rgt FROM nested_category
WHERE name = 'TELEVISIONS';
UPDATE nested_category SET rgt = rgt + 2 WHERE rgt > @myRight;
UPDATE nested_category SET lft = lft + 2 WHERE lft > @myRight;
INSERT INTO nested_category(name, lft, rgt) VALUES('GAME CONSOLES', @myRight + 1, @myRight + 2);
UNLOCK TABLES;
- 删除新节点
删除节点的算法与添加一个节点的算法相反
删除一个没有子节点的节点
LOCK TABLE nested_category WRITE;
SELECT @myLeft := lft, @myRight := rgt, @myWidth := rgt - lft + 1
FROM nested_category
WHERE name = 'GAME CONSOLES';
DELETE FROM nested_category WHERE lft BETWEEN @myLeft AND @myRight;
UPDATE nested_category SET rgt = rgt - @myWidth WHERE rgt > @myRight;
UPDATE nested_category SET lft = lft - @myWidth WHERE lft > @myRight;
UNLOCK TABLES;
删除一个分支节点和它所有的子节点
LOCK TABLE nested_category WRITE;
SELECT @myLeft := lft, @myRight := rgt, @myWidth := rgt - lft + 1
FROM nested_category
WHERE name = 'MP3 PLAYERS';
DELETE FROM nested_category WHERE lft BETWEEN @myLeft AND @myRight;
UPDATE nested_category SET rgt = rgt - @myWidth WHERE rgt > @myRight;
UPDATE nested_category SET lft = lft - @myWidth WHERE lft > @myRight;
UNLOCK TABLES;
删除一个节点后移动其字节点到
LOCK TABLE nested_category WRITE;
SELECT @myLeft := lft, @myRight := rgt, @myWidth := rgt - lft + 1
FROM nested_category
WHERE name = 'PORTABLE ELECTRONICS';
DELETE FROM nested_category WHERE lft = @myLeft;
UPDATE nested_category SET rgt = rgt - 1, lft = lft - 1 WHERE lft BETWEEN @myLeft AND @myRight;
UPDATE nested_category SET rgt = rgt - 2 WHERE rgt > @myRight;
UPDATE nested_category SET lft = lft - 2 WHERE lft > @myRight;
UNLOCK TABLES;
总结:
预排序遍历树算法的核心就是牺牲了写的性能来换取读取的性能
在你的开发的应用遇到此类问题的时(读压力 > 写压力),尝试下使用预排序遍历树算法来提高你的程序的性能吧。
发表评论
-
centos安装denyhost
2020-11-21 14:29 347安装denyhost 下面这个不知是否是官网。 https: ... -
rabbitmq的终端管理命令rabbitmqadmin
2020-11-13 17:03 752启动rabbitmq systemctl start rab ... -
centos 安装 RabbitMQ
2020-11-11 14:40 375安装 erlang语言环境。 千万不要直接 yum inst ... -
centos的证书配置
2020-06-09 20:32 832用百度云,发现对其他https 的 网站访问时有时无。 排查 ... -
git常用命令
2020-02-03 15:27 339git常用命令 删除本地分支。 git branch -d ... -
shadowsocks 故障解决
2020-02-01 12:06 4497今天突然发现shadowsocks无法使用。 解决方案:修改服 ... -
putty设置正向代理
2019-08-21 21:17 605利用putty设置正向代理。 假如你的电脑不能访问服务器B, ... -
centos7下vsftp的虚拟用户安装和配置
2019-07-12 20:05 899安装ftp在centos7下, 此类文章很多,这里也只是总结一 ... -
使用systemd为php程序建立守护进程
2019-01-14 16:47 2117前提,是centos7,或ubuntu对应版本。 以前需要 ... -
centos7.4安装php7.2套件
2018-08-24 12:07 2972# 操作系统 centos7.4 # 所谓套件,就是nginx ... -
centos7.4安装php5.6套件
2018-08-15 18:09 2040本文不包括清理系统原有环境里的nginx,php,mysql ... -
mysql数据库导入导出防止乱码,加用户
2017-06-19 10:42 591数据库原本在linux上,项目的编码是gbk。 现在想导入到w ... -
centos7 时间同步
2017-06-15 15:41 868# 安装 yum install chrony # 启 ... -
mysql设用户设密码
2013-12-11 16:45 739都是抄的。 添加最高权限用户 假设root的密码是passw ... -
获得linux文件夹下的所有文件(强化版)
2013-04-26 10:07 906class Sys { /** ... -
使nginx拒绝特定url(实际是目录)下所有文件的请求
2013-03-26 14:56 1404if ($request_uri ~* (.*)(\ ... -
使用php充当shell脚本(转载)
2013-02-02 09:17 1129任务:过滤出2010-08-18的apache访问日志,并放到 ... -
linux常用故障排查
2013-01-28 08:57 809linux 下查找大于100M的文件 find . - ... -
网卡流量监控(转载文章)
2012-12-11 10:45 908http://www.vpseek.com/newbies-g ... -
postgresql安装
2012-12-06 20:12 874# TYPE DATABASE USER ...
相关推荐
大家通常都是使用递归实现无限极分类都知道递归效率很低,下面介绍一种改进的前序遍历树算法,不适用递归实现无限极分类,在大数据量实现树状层级结构的时候效率更高。 sql代码如下: CREATE TABLE IF NOT EXISTS `...
无限级分类----改进前序遍历树 二叉树 c# 无限极分类 前序遍历树
php无限极分类两种方法,递归无限极分类和引用无限极分类!
部门管理的无限极分类 产品分类也是通用 包括一个controller文件 一个model文件 一个view文件夹 和一个sql文件 放在相应位置按需求改动即可使用
php无限极分类函数包,下载即可用,绝对好用,里面有多种无限极分类函数,可以参考,我都试过了
php递归获取子级,父级,无限极分类,带demo,效率超高。下载请评价,谢谢!!!
php无限极分类,手动排序,排序,无限极分类排序,自己填写排序
无限极分类技术,结合thinkphp3.2.3,有数据库表,下载解压即可,适合新手学习的好源码
用递归算法实现无限极添加、删除、修改和移动菜单
jQuery实现递归无限极树状菜单特效源码.zip
主要介绍了php无限极分类递归排序实现方法,通过一个简单的递归函数实现无限递归分类排序,是非常实用的技巧,需要的朋友可以参考下
自己编写的无限极分类代码,参考alixixi
无限极 分类 下拉框 无限极分类 下拉框 无限极分类下拉框
C#无限极分类
此文档使用TreeView控件绑定实现了无限极分类,数据库一个表使用了三个字段
利用递归实现无限极目录展示,可点击展开和收起,基于jquery
递归,无限极评论:无限极评论的原理,用递归实现。由于权限不够,想要视频去访问我的资源里面有