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