分享
 
 
 

项目开发中层次结构存储的两种设计方法

王朝other·作者佚名  2008-06-03
窄屏简体版  字體: |||超大  

在实际的项目开发中,我们经常会碰到存储多级数据结构(树状)的问题。下面,我们来介绍一下层次结构存储的两种设计方法:

1:邻接表模式(adjacency list model)

2:先根遍历树算法(modified preorder tree traversal algorithm)

参考数据结构:

中国

|

|---陕西

| |

| |---渭南

| |

| |--- 西安

| |

| |--钟楼

| | |

| | |--大雁塔

|

|---云南

| |

| |---丽江

1:邻接目录模式:

一般情况下,我们在数据库中增加一个parent字段表示这个节点的父节点,从而将整个树状描述出来

如:

parent name

中国

中国 陕西

中国 云南

陕西 渭南

陕西 西安

云南 丽江

西安 钟楼

西安 大雁塔

等这样我们就能够通过数据库保存整个树状结构啦。

通过这种方法需要得到一个多级结构时候需要进行一个递归, 通过递归的方法我们可以得到任意节点的路径。

这种方法的优点是简单,容易理解。缺点是运行速度很慢。尤其是数据量很大的时候需要进行很多查询时候才能完成一个树, 效率很低。

2:先根遍历树算法

将多级数据按照下面的格式划出来

1 中国 16

|

+------------------------+

2 陕西 11 12 云南 15

| |

+-------------+ 13 丽江 14

3 渭南 4 5 西安 10

|

+-----------+

6 钟楼 7 8 大雁塔 9

我们给根节点“中国”左侧标上1, 然后沿着这个树向下在“陕西”左侧标上2, 然后继续前进, 向下在“渭南”左侧标上3, 渭南没有子节点,所以在“渭南”右侧标上4, 然后继续“渭南”的右侧节点。。。沿着整个树的给每个节点的左侧和右侧标上数字。最后一个数组标在“中国”右侧为16。 你只要用手指从1指到16就知道怎么回事啦。

这些数字表明了各个节点之间的关系。我们可以看到, 所有左侧大于2, 右侧小于11的节点,都是“陕西”的子节点。

这样我们可以在数据库中用left, right表示左右数字。如:

我们给根节点“中国”左侧标上1, 然后沿着这个树向下在“陕西”左侧标上2, 然后继续前进, 向下在“渭南”左侧标上3, 渭南没有子节点,所以在“渭南”右侧标上4, 然后继续“渭南”的右侧节点。。。沿着整个树的给每个节点的左侧和右侧标上数字。最后一个数组标在“中国”右侧为16。 你只要用手指从1指到16就知道怎么回事啦。

这些数字表明了各个节点之间的关系。我们可以看到, 所有左侧大于2, 右侧小于11的节点,都是“陕西”的子节点。

这样我们可以在数据库中用left, right表示左右数字。如:

name left right

中国 1 16

陕西 2 11

云南 12 15

渭南 3 4

西安 5 10

钟楼 6 7

大雁塔 8 9

丽江 13 14

这样我们如果想得到 "陕西"下的所有节点。只需要执行:

select * from table where left between 2 and 11;

要想知道“西安”的路径只需要执行:

select * from table where left < 5 and right > 10;

计算某个节点有多少子孙节点: 子孙节点数=(右值-左值-1)/2;

要算出所有节点的左右值, 数据库中需要parent字段,然后编写一个计算左右值递归函数执行。(这里略去不谈)。

主要考虑如何进行一个子节点的增加,删除。

◆方法1: 在数据库中保留parent字段, 增加节点后,调用计算左右值递归函数重新计算左右值。 该方法不推荐用

◆方法2: 改变所有位于新节点右侧的左右值。

比如:想添加“华清池”作为“西安”的最后一个节点,我们给它挪出一个空间,“西安”的右值改为12, “陕西”的右值改为13, “云南”及其子节点的左右值从“12-15”改为 “14-17”, “中国”的右值改为18。即给左右值大于9的所有节点加2 (9为西安最后一个子节点的右值)

update table set right=right+2 where right > 9;

update table set left=left+2 where left > 9;

这样就给新节点腾出空间,它的左右值分别为 9+1, 9+2;

insert into table set left=10, right=11, name='华清池';

当然,删除一个节点时候给左右值大于该节点右值的所有节点减2。

注释:以上两种方法的采用根据我们可以针对具体情况来酌情考虑,假如查询量小但频繁添加,删除则建议采用第一种。假如查询量偏大,我们可以考虑使用第二种方法。

 
 
 
免责声明:本文为网络用户发布,其观点仅代表作者个人观点,与本站无关,本站仅提供信息存储服务。文中陈述内容未经本站证实,其真实性、完整性、及时性本站不作任何保证或承诺,请读者仅作参考,并请自行核实相关内容。
2023年上半年GDP全球前十五强
 百态   2023-10-24
美众议院议长启动对拜登的弹劾调查
 百态   2023-09-13
上海、济南、武汉等多地出现不明坠落物
 探索   2023-09-06
印度或要将国名改为“巴拉特”
 百态   2023-09-06
男子为女友送行,买票不登机被捕
 百态   2023-08-20
手机地震预警功能怎么开?
 干货   2023-08-06
女子4年卖2套房花700多万做美容:不但没变美脸,面部还出现变形
 百态   2023-08-04
住户一楼被水淹 还冲来8头猪
 百态   2023-07-31
女子体内爬出大量瓜子状活虫
 百态   2023-07-25
地球连续35年收到神秘规律性信号,网友:不要回答!
 探索   2023-07-21
全球镓价格本周大涨27%
 探索   2023-07-09
钱都流向了那些不缺钱的人,苦都留给了能吃苦的人
 探索   2023-07-02
倩女手游刀客魅者强控制(强混乱强眩晕强睡眠)和对应控制抗性的关系
 百态   2020-08-20
美国5月9日最新疫情:美国确诊人数突破131万
 百态   2020-05-09
荷兰政府宣布将集体辞职
 干货   2020-04-30
倩女幽魂手游师徒任务情义春秋猜成语答案逍遥观:鹏程万里
 干货   2019-11-12
倩女幽魂手游师徒任务情义春秋猜成语答案神机营:射石饮羽
 干货   2019-11-12
倩女幽魂手游师徒任务情义春秋猜成语答案昆仑山:拔刀相助
 干货   2019-11-12
倩女幽魂手游师徒任务情义春秋猜成语答案天工阁:鬼斧神工
 干货   2019-11-12
倩女幽魂手游师徒任务情义春秋猜成语答案丝路古道:单枪匹马
 干货   2019-11-12
倩女幽魂手游师徒任务情义春秋猜成语答案镇郊荒野:与虎谋皮
 干货   2019-11-12
倩女幽魂手游师徒任务情义春秋猜成语答案镇郊荒野:李代桃僵
 干货   2019-11-12
倩女幽魂手游师徒任务情义春秋猜成语答案镇郊荒野:指鹿为马
 干货   2019-11-12
倩女幽魂手游师徒任务情义春秋猜成语答案金陵:小鸟依人
 干货   2019-11-12
倩女幽魂手游师徒任务情义春秋猜成语答案金陵:千金买邻
 干货   2019-11-12
 
推荐阅读
 
 
 
>>返回首頁<<
 
靜靜地坐在廢墟上,四周的荒凉一望無際,忽然覺得,淒涼也很美
© 2005- 王朝網路 版權所有