admin 管理员组文章数量: 1184232
2024年4月22日发(作者：asp网站源码是多少)
维普资讯
第２７卷
计算机应用
Ｖｏ１．２７
２００７年６月
Ｃｏｍｐｕｔｅｒ Ａｐｐｌｉｃａｔｉｏｎｓ
Ｊｕｎｅ ２００７
文章编号：１００１—９０８１（２００７）Ｓ１一Ｏ０１２—０２
非线性结构在ＲＤＭＳ系统中的压缩存储研究
汪建 ，赵海洋 ，叶发忠
（１．重庆邮电大学计算机科学与技术学院，重庆４０００６５；
２．西南大学计算机与信息科学学院，重庆４００７１５；
３．绵阳师范学院计算机科学与工程系，四川绵阳６２１０００；
４．中国科学院成都计算机应用研究所，四川成都６１００４１）
（ｗａｎｇｊｉａｎ＠ｅｑｕｐｔ．ｅｄｕ．ｅｎ）
摘要：关系数据库管理系统（ＲＤＭＳ）是以线形二维数据表作为存储模型，而在科学研究领域
中，许多数据模型并非处于线性状态。讨论的中心问题是如何在ＲＤＭＳ中存放非线性数据结构，使
其在维护海量数据的同时，降低数据冗余，并讨论数据一致性的保证和对比分析存储、检索算法的时
空复杂度。
关键词：数据压缩；非线性数据结构；存储；检索；前缀码
中图分类号：ＴＦ３１１．１３ 文献标识码：Ａ
０ 引言
表１路径表示法关系表
＃ＮＯ ＰａｔｈＮａｍｅ
在计算机科学领域中，数据结构分为线性结构和非线性
１
Ｒｏｏｔ：、
结构两类。线性结构的存储和处理技术比较熟，而非线性结
２
Ｒｏｏｔ：｜Ｄｉｒｌ｜
构因其复杂性和多样性导致其处理困难。
Ｒｏｏｔ：、Ｆｉｌｅｌ
树形数据结构（简称：树结构）是一种常见且非常重要的
Ｒｏｏｔ：、Ｆｉｌｅ２
非线性结构，其应用非常广泛，是层次模型的典型代表。但是
Ｒｏｏｔ：｜Ｄｉｒｌ｜Ｆｉｌｅ３
针对一般树的存储及运算没有通用的算法，通常是将其转换
Ｒｏｏｔ：、Ｄｉｒｌ、Ｆｉｌｅ４
为二叉树进行处理。
Ｒｏｏｔ：｜Ｄｉｒｌ｜Ｆｉｌｅ５
关系数据库是目前海量数据组织处理中最有效的方法，
表２双亲表示法关系表
并且它提供了高效的查询服务。但是在关系数据库应用开发
中，大部分是处理以二维表为基础的线性结构数据。对于非
线性的树形结构，绝大多数关系数据库没作介绍，特别是对树
高和度未知的一般树更是没有统一的解决方案和算法。下面
将分析树结构在关系数据库存储的一般算法，然后提出一种
以前缀码为基础的新型树结构压缩存储算法，最后比较两类
算法的时间复杂度和空间复杂度。
１ 传统的树结构存储算法
表中＃ＮＯ字段是关键字，代表每一个数据项的编号；
１．１路径表示法
ＮｏｄｅＮａｍｅ字段记录了每一个目录或文件的名称；ＦａｔｈｅｒＮｏｄｅ
一
般树的存储通常是采用
字段标明该节点的父节点在数据库中的编号。
记录路径的方式存放层次结
构。以文件分配表为例，各级
２树结构压缩存储法
目录名和文件名构成了ＦＡＴ
２
双亲表示法巧妙的删除了树结构中的无关数据，节省了
结构，如图１所示，它是一个典
存储空间。但是由于每个节点与其在关系表中的位置紧密相
型的树形数据结构。
Ｆｉｌｅ３ Ｆｉｌｅ４ Ｆｉｌｅｓ
关，无论是在表中插入、删除数据或对数据进行排序都会改变
将其转化为关系数据库结
图１ ＦＡＴ结构
数据项的位置，从而导致为了维护树结构的正确性付出高昂
构，如表１所示。其中＃ＮＯ字段是数据库自动编号，且是关键
的开销去调整ＦａｔｈｅｒＮｏｄｅ字段的内容。
字；ＰａｔｈＮａｍｅ字段记录了每一个目录和文件的完整路径。
因此怎样解决双亲表示法弊端的问题就变成了怎样使
１．２双亲表示法
ＮｏｄｅＮａｍｅ字段与物理位置无关的问题。以下是使用前缀码
顾名思义，以回溯的方式组织和记录树结构。该方法以
替代简单的父节点位置的方法：
二维表作为存储基础，适合关系数据库的组织模式。根据上
首先，为了使用前缀编码，必须将一般树结构转化为等价
例可构成双亲表示法的关系表，如表２所示。
的二叉树，具体方法是：建立同层兄弟节点间的联系；保留父
收稿日期：２００６—１２—１４
作者简介：汪建（１９７８～），男，重庆人，讲师，硕士研究生，主要研究方向：智能信息处理、数据挖掘；赵海阳（１９７６一），四川绵阳人，讲师，
主要研究方向：网络安全；叶发忠（１９７６一），男，四川广汉人，工程师，硕士，主要研究方向：软件工程．
维普资讯
６月 汪建等：非线性结构在ＲＤＭＳ系统中的压缩存储研究 １３
节点与第一子节点的联系，删除父节点与其他子节点间的联
系，转换算法如图２所示。
然后，采用前缀码编码方式
对转换得到的二叉树进行编码：
每个节点的左分支编码为０，右
２
分支编码为１，如图３所示。
编码后得到树结构压缩存
Ｆｉｌｅ３ Ｆｉｌｅ４ Ｆｉｌｅ５
储法关系表，如表３所示。
Ｊ口ｌ
Ｆ
表３树结构压缩存储法关系表
Ｒｏｏｔ
醪
Ｆ
由于每一个节点的
ＰｒｅｆｉｘＣｏｄｅ字段只跟父节点的
ＰｒｅｆｉｘＣｏｄｅ字段相关，与记录项
的物理存储位置无关，不会因为
数据的插入删除和排序操作引
发树结构层次混乱，有效地保证
的数据的一致性。
图２一般树转化为二叉树
３ 算法比较
Ｒｏｏｔ
３．１空间复杂度
３．１．１路径表示法
假设系统中目录结构是一
棵满ｎ叉树、树深为ｋ且每个节
点宽度为ｍ，则按照常规的矩阵
存储方式：第一层只有１个根节
点，占用的绝对存储空间是ｍ，
第二层含有ｎ个节点，占用的绝
图３前缀码编码表
对存储空间是ｍｎ，以此类推第ｋ
层含有ｎ 个节点，占用的绝对存储空间是ｎ ’ｍ。所以整棵
树理论上所占用的绝对存储空间是：∑ｎｉ－Ｉ ｍ。
事实上以关系模型作为数据组织模式并使用二维表作为
存储载体的数据库中要实现变长字段是不可能的，众多的商
业数据库系统也没有提供相应的解决方案。因此为了能进行
数据存放，必须考虑最“恶劣”的情况。所以路径表示法模型
所使用的存储空间是：ｋｍ・∑ｎ ’。
３．１．２树结构压缩存储法
针对同一种情况，如果使用改进后的树结构压缩存储法
模型，存放ＮｏｄｅＮａｍｅ字段数据消耗的存储空间为：
ｍ・（∑ｎ ’一１）
存储前缀编码消耗的空间为：
（ｋ＋ｍ一２）・（∑ｎ王了 ’一１）
所以实际消耗的存储空间是：
（Ｊ｝＋２ｍ一２）・（∑ｎ ’一１）。
所以，采用树结构压缩存储法存储同样的一棵树比路径
表示法节约空间：
ｍ一１）・（Ｊ｝一２）・（∑ｎ ’一１）十ｋ・ｍ
即是：
（ｍ一１）・（ｋ一２）・（ 一１）＋ｋ・ｍ
３．２ 时间复杂度
３．２．１ 路径表示法
假设字符串的长度为￡，子串的长度为Ｚ，则在字符串中
搜索子串的匹配算法的平均时间复杂度为：Ｌ十一｝ ．ｚ。根据
上例可知路径表示法的记录项长度为： ．ｍ（Ｊ｝为树的深
度）。所以在路径表示法中进行字串匹配的平均时间复杂度
为： 掣
３．２．２ 树结构压缩存储法
同样，假设字符串的长度为￡，子串的长度为Ｚ，则在字符
串中搜索子串的匹配算法的平均时间内复杂度为：Ｌ十一｝ ．
Ｚ。因为压缩树结构存储法记录项长度为：ｍ。所以在树结构压
缩存储法中进行字串匹配的平均时间复杂度为：Ｌ ．
１。
所以，采用树结构压缩存储法存储同样的一棵树比路径
表示法节约时间： ．二＝一生
。
４ 结语
通过上述的分析不难看出，改进之后的树结构压缩存储
法克服了路径表示法使用冗余存储方式浪费空间过多的缺
点，同时克服了双亲表示法中数据操作困难的缺点。无论是
时间复杂度还是空间复杂度都具有相当的优势。该算法可以
应用到各种需要在关系数据库中存放树形结构数据的场合，
并已在重庆邮电大学的“基于网络的自主学习系统”项目中
得到充分的验证。
参考文献：
【１］ＳＨＡＦＦＥＲ ＣＡ．Ａ Ｐｒａｃｔｉｃａｌ Ｉｎｔｒｏｄｕｃｔｉｏｎ ｔｏ Ｄａｔａ Ｓｔｒｕｃｔｕｒｅｓ ａｎｄ Ａ１一
ｇｏｒｉｔｈｍ Ａｎａｌｙｓｉｓ［Ｍ］．Ｓｅｃｏｎｄ Ｅｄｉｔｉｏｎ．Ｐｕｂｌｉｓｈｉｎｇ Ｈｏｕｓｅ ｏｆ Ｅｌｅｃ—
ｔｒｏｎｉｅ Ｉｎｄｕｓｔｒｙ．２００４．
【２］ＨＤＤＥＬＬ Ｍ，ＭＯＦＦＡＴ Ａ．Ｈｙｂｒｉｄ ｐｒｅｆｉｘ ｃｏｄｅｓ ｆｏｒ ｐｒａｃｔｉｃａｌ ｕｓｅ
【ＡＪ．Ｄａｔａ Ｃｏｍｐｍｓｓｉｏｎ Ｃｏｎｆｅｒｅｎｃｅ［Ｃ］．２００３，１２：７７—７９．
【３］ＢＡＳＳＩＮＯ Ｆ，ＣＬＥＭＥＮＴＪ，ＳＥＲＯＵＳＳＩ Ｇ，ｅｔ ａ１．Ｏｐｔｉｍａｌ ｐｒｅｆｉｘ
ｃｏｄｅｓ ｆｏｒ ｓｏｍｅ ｆａｍｉｌｉｅｓ ｏｆ ｔｗｏ－ｄｉｍｅｎｓｉｏｎａｌ ｇｅｏｍｅｔｒｉｃ ｄｉｓｔｒｉｂｕｔｉｏｎｓ
【Ａ］．Ｄａｔａ Ｃｏｍｐｍｓｓｉｏｎ Ｃｏｎｆｅｒｅｎｃｅ［Ｃ］．２００６，３：１１３—１２２．
【４］ ＭＩＬＩＤＩＵ ＲＬ，ＭＥＬＬＯ ＣＧ．Ｃｒｙｐｔｏ—ｃｏｍｐｒｅｓｓｉｏｎ ｐｒｅｆｉｘ ｃｏｄｉｎｇ［Ａ］．
Ｄａｔａ Ｃｏｍｐｒｅｓｓｉｏｎ Ｃｏｎｆｅｒｅｎｃｅ［Ｃ］．２００６，３：１—５．
【５］ 严蔚敏，吴伟民．数据结构【ＭＪ．北京：清华大学出版社，２００２．
【６］郑相周．ＤＢＭＳ中的树形结构关系数据库【Ｊ］．微型电脑应用，
１９９５，１１（２）：７６－７８、
【７］ 李威，万新光．树形数据顺序存储映象和链式存储映象转换的方
法【Ｊ】．哈尔滨电工学院学报，１９９５，１８（Ｉ）：１００一１０４．
Ｒ
Ｏ
版权声明：本文标题：非线性结构在RDMS系统中的压缩存储研究 内容由网友自发贡献，该文观点仅代表作者本人， 转载请联系作者并注明出处：http://www.roclinux.cn/b/1713748143a649724.html， 本站仅提供信息存储空间服务，不拥有所有权，不承担相关法律责任。如发现本站有涉嫌抄袭侵权/违法违规的内容，一经查实，本站将立刻删除。
发表评论