基于二进制移位的嵌套区间层次模型算法优化.pdf

2023 年第 9 期11计算机应用信息技术与信息化基于二进制移位的嵌套区间层次模型算法优化汪 鹏1 雷玮剑1 王云福1 侯 斌1 王 理1WANG Peng LEI Weijian WANG Yunfu HOU Bin WANG Li 摘要 嵌套区间是嵌套集合理论在有理数范围的扩展，利用有理分数进行层次结构编码的方式，解决了嵌套集合模型中节点容量受限和节点变形操作性能较差的问题。嵌套区间模型中节点编码会随着层次结构规模增大而呈指数增加，导致节点操作性能下降且存储增加。针对此问题，研究了嵌套区间的数学模型，根据节点编码特点，提出了一套基于二进制移位原理的嵌套区间模型优化算法，可将算法时间复杂度降为O(1)，提高层次结构操作效率。同时设计了一种新的节点存储结构，可以降低磁盘存储。实验结果表明，新算法和存储结构能够显著提高节点操作效率并降低存储。关键词 层次模型；嵌套区间；有理分数；二进制移位；存储结构；节点操作效率 doi：10.3969/j.issn.1672-9528.2023.09.0021.深圳中广核工程设计有限公司 广东深圳 518000 基金项目 本论文由国家重点研发计划复杂产品全生命周期价值链协同平台研发与应用示范（课题编号：2020YFB1711705）资助。0 引言层次结构作为一种基础数据结构在很多领域都有重要的应用，常见的重要层次结构有树型结构1、森林结构、有向图结构等。利用层次结构可以表达文件关联、设备构型、产品分类、部门架构等层级从属和并列关系。在操作系统、数据库和机器学习等领域，也用到了很多优秀的无限分级层次结构，例如 Window/Unix 文件系统、R-Tree、B-Tree、KD-Tree、决策树、随机森林等等。研究如何高效表达、组织和管理这种无限分级的非线性结构数据，对理论扩展和实践应用都具有重要意义。本文以核电设计管理平台中的无限分级树型结构为例进行了层次结构模型的相关研究。树型结构指数据元素之间存在着“一对多”的层级关系的数据结构，是一种特殊的有向无环图（directed acyclic graph，DAG）。其可以表达复杂的数据类型，包括嵌套、重复和缺失值2-3，是一类重要的非线性数据结构。一般有两种树结构模型来处理这种无限分级非线性关系：分层递归模型（hierarchical recursive model）和树型编码模型（tree encoding model）4。最具代表性的分层递归技术为邻接表模型，但是这种数据结构存在信息冗余和传递依赖，不符合域键范式（DKNF 范式）5。在进行自下而上的传递依赖查询和自上而下的偏序查询以及涉及子树的变形操作时，都依靠递归技术来完成，当树规模变大时，将存在严重的性能问题。另外两种常用数据结构为物化路径和闭包表，这两种模型存在大量冗余信息，存储耗费巨大，且数据量增长极快，不适用于大规模应用场景。在现实业务场景中，查询的需求是远大于树结构变形操作需求的，树型编码模型从树节点的全局位置出发，对节点在层次结构里面的全局位置进行有规则的编码，再配合定位算法，可以给树结构模型带来优秀的层次查询性能，在统计业务频繁的场景中表现优异。树型编码模型中最为著名的是Celko6提出的嵌套集合模型（nested sets model，NSM），其在电力文档库建设、组织机构树、树型数据库设计等实际工程中应用广泛7-11。NSM 是一种改进的先序遍历树模型，在 NSM 中仅用一对称为“左右值”的有序正整数来编码一个树节点，祖先后代关系通过整数区间之间的子集关系反映出来，为层次查询提供了非常直观的基础。可以在消除递归的前提下实现无限分级，而且统计条件是基于整型数字比较，效率很高。NSM 在统计方面具有类似的性能，作为基础数据结构被广泛应用，但它有两个明显的缺点12。第一，节点编码是不稳定的，具有易变性。每当插入一个新节点时，大约一半的树节点需要重新编码。第二，从性能角度来看，查询范围操作是不对称的。要查询一个点是否落在某个区间内很容易（即自上而下查询），要为包含给定点的一组区间建立索引却很难（即自下而上查询）。虽然 NSM 存在上述问题，但这种编码方案给树型结构设计开辟了新思路。Tropashko13将 NSM 进行泛化，提出了嵌套区间模型（nested intervals model，NIM）。NIM 利用二元有理分数这种特定编码模式对节点进行左右值编码，是NSM 理论在有理数范围的扩展，这种稠密域的引入有效解决了上述问题。一种基于 NIM 的典型树型结构如图 1 所示。2023 年第 9 期12计算机应用信息技术与信息化11.21.11.31.1.21.1.11.1.31.2.21.2.11.2.31.3.21.3.11.3.36493253251631634141329814121212116516583831698585434310111111图 1 基于嵌套区间模型的树型结构有理数编码具有许多良好的理论性质，本质上是物化路径的数值反映。相比于嵌套集合模型，嵌套区间模型通过稠密域的引入很好地解决了节点容量受限问题，同时由于编码构建过程是规则化的，嵌套区间模型能够以算法的方式在内存中完成祖先路径层次的查询，而无需通过层次递归技术访问数据库中存储的层次关系数据。NIM 也在很多方面得到了改进和应用，Tropashko14-15通过 Conway 数列16和法雷级数17-18对 NIM 进行了改进，带来了很好的效果。Na 等人19将 NIM 应用到 XML 数据的大规模存储和检索中，性能得到很大提升。Volonkin 等人20利用 NIM 来提升 DBMS 的索引性能，Malikov 等人21在残差类系统中用 NIM 描述间隔数，可以避免大数字的存储，并且很容易通过并行编程算法实现。然而，从工程角度来看，NIM 有一个明显的缺陷：二元有理数相当不经济地利用区间值域，且节点编码会随着树结构规模增大而呈指数增加，导致节点操作性能下降且存储量增加。本文致力于对核电设计管理平台中的基础树型结构进行创新表达，以提升树结构查询性能，对嵌套区间模型相关算法和数据结构进行优化，以降低树规模增长带来的影响。本文主要贡献如下：（1）根据嵌套区间节点生成过程，推导出嵌套区间模型的数学模型，并进行了严格证明；（2）基于编码结构特性，结合二进制乘除原理，提出了基于二进制移位原理的嵌套区模型系列优化算法；（3）结合编码结构特性，设计了新的节点存储方案；（4）与原始嵌套区间模型算法和存储对比，新算法和存储结构能够显著提高节点操作效率并降低存储。1 嵌套区间模型算法优化1.1 嵌套区间数学模型在嵌套区间模型中，利用笛卡尔平面中点的 x,y 坐标来表示节点的左右值 rgt,lft，树节点与平面中的点形成严格双射关系，嵌套区间模型中相关关键节点定义如下。定义 1 在笛卡尔坐标系中，点 P 的深度优先聚合点是对角线yx=与过点 P 的垂直线的交点。定义 2 在笛卡尔坐标系中，点 P 的广度优先聚合点是对角线yx=与过点 P 的水平线的交点。定义 3 节点索引定义为其在兄弟节点中从右往左的逻辑位次，最右边第一个子节点的索引定义为 1。定义 4 笛卡尔平面中点的坐标 x,y 定义为树节点的左右值编码 rgt,lft，其中 x 为右编码 rgt，y 为左编码 l ft;左右值编码之和 num/den 的分子与分母组成的二元整数值对定义为节点的嵌套区间编码 num,den。嵌套区间模型设计了一种带有二元有理数的特定编码模式，通过有理数来对节点进行左右值编码。假设区间 0,1 为根节点，整个嵌套区间模型节点的构造规则如下：父节点 P的第一个子节点 C1是由深度优先聚合点 dp 和父节点 P 连线的中点来确定，子节点下一个兄弟节点 Ci由上一个兄弟节点 Ci1和父节点 P 的广度优先聚合点 bp 连线的中点来确定，其构造过程如图 2 所示。在一维和二维坐标系中展示如图 3 和图 4 所示。图 2 嵌套区间模型节点构造过程图 3 嵌 套区间一维图示图 4 嵌套 区间二维图示根据节点构造规则，利用数学归纳法可以得到以下嵌套区间定理。2023 年第 9 期13计算机应用信息技术与信息化引理1假设节点左值为，则右值为（根节点除外），且 为既约分数，其中 b 为奇数，。证明从略。定理 1假设父节点的左右值编码为，则第 i 个子节点 Ci的左右值编码为：(1)式中：i 为子节点索引。定理 2假设根节点为 0,1，父节点的左右值编码为，则第 i 个子节点 Ci的嵌套区间编码为：(2)式中：h 为层级索引，父节点的层级索引定义为 0，i 为节点索引。定理 3假设根节点为 m,n，父节点的左右值编码为，则第 i 个子节点的嵌套区间编码为：(3)式中：h 为层级索引，i 为节点索引。1.2 基于二进制移位的算法优化通过 1.1 节中的数学模型分析，找到了子节点与父节点之间的关系。利用数乘和数除运算的二进制原理，对嵌套区间模型中节点索引计算算法（INDEX）、父节点计算算法(PARENT)、节点寻径算法（PATH）和节点距离计算算法(DISTANCE)进行了优化，提出了基于二进制移位的嵌套区间模型系列优化算法（binary shift calculation algorithm，BSCA）。其中节点索引计算算法和父节点计算算法是嵌套区间模型中其他树型操作算法的基础，这两个算法的性能对整个模型至关重要，本文将进行重点分析。b1b*2i00100左移i位i位左移i位图 5 左值分子与二进制移位节点索引计算算法和父节点计算算法的核心思想是：根据定理 1 中描述的父子节点关系，首先利用二进制左移运算与数乘的对应关系，在近乎 O(1)的时间复杂度内直接求出子节点索引 i，然后利用二进移位运算与数乘和数除的对应关系计算出 a 值和 b 值，即可以计算出父节点的左右值。算法巧妙地利用了二进制移位与乘除运算的关系，在公式(1)中令左值分子，变形得到，即表示将 b 的二进制形式进行左移 i 位得到 c-1。在嵌套区间模型中，由引理 1 可知 b 一定是奇数，其二进制形式中末尾位一定为 1，所以只需要计算整数 c-1 的二进制形式末尾 0 的个数，就能得到i的值，即直接得到了子节点索引，整个过程如图5所示。从计算机体系结构原理分析，使用移位指令有更高的效率，因为移位指令占 2 个机器周期，而乘除法指令占 4 个机器周期。从硬件上看，移位对硬件也更容易实现。BSCA 系列算法如算法 1 4 所示。算法 1节点索引计算算法 INDEX输入：子节点左值分子 num 和子节点左值分母 den。输出：子节点索引。1.temp=num-12.y=313.if temp S2-S3-S4），水平导航时的步数就是子节点的索引，两个算法的时间复杂度均为 O(n)。当给定子节点的索引较大时，求解越耗时；子节点越靠近第一个兄弟节点时，耗时越小。基于二进制移位的节点索引计算算法和父节点计算算法则通过底层二进制移位操作，直接求出子节点的索引，然后根据父子节点之间的计算公式，求出父节点，如图 7 所示（S1），两个算法的时间复杂度均近乎 O(1)。11.11.1.11.1.1.1231.21.31.2.11.3.12.12.1.12.22.2.13.14RootS1S2S3S41.4图 6 原父节点计算算法11.11.1.11.1.1.1231.21.31.2.11.3.12.12.1.12.22.2.13.14Root1.4S1图 7 基于二进制移位的父节点计算算法1.3 存储数据结构优化在嵌套区间模型底层数据结构中，直接对定义 4 中节点的嵌套区间编码进行了存储，即存储了左右值之和的分子和分母。这种结构会随着树规模的增长呈现指数级的增长，受到数据库字段容量的限制，数值溢出问题会限制树的增长规模。由引理 1 和定理 1 3 可知，节点的左右值本身以及左右值之间均遵循指数函数的规律，基于这两点可以对节点嵌套区间编码底层存储结构做如下优化。（1）分母：只存储嵌套区间编码分母的指数部分。（2）分子：只存储节点嵌套区间左值的分子，而不存储左右值和的分子。以图 1 中节点 1.3.3 为例，该节点的左右值之和为 9/64+5/32=19/64，对应的嵌套区间编码为 19,64，原方案中需要存储的二元数值对为 19,64。新方案中只存储节点左值的分子和分母的指数，即只需存储 9,6。当节点层次和索引更大时，存储优势将更为明显。综合而言，新的存储结构可以降低嵌套区间编码所需的存储空间，也在一定程度上缓解了数值溢出问题。2023 年第 9 期15计算机应用信息技术与信息化2 实验与结果分析在本节中，对以下两个问题进行实验验证，来评估提出的嵌套区间模型系列优化算法和存储结构。（1）相比原始嵌套区间系列算法（包括父节点计算算法、节点索引计算算法、节点寻径算法和节点距离计算算法），BSCA 系列算法效果如何?（2）相比原嵌套区间存储方案，新存储方案表现如何?2.1 实验环境和数据集本文的实验环境为 64 位 Windows 系统，Intel(R)Core(TM)i7-10510U CPU，8 GB 内存，底层树结构采用 MySQL 进行存储，利用 SQL、Java 和 Python 语言进行编码。为了充分测试算法性能和统计节点存储量，本文所有实验均在满叉树结构上进行，满叉树节点数可通过公式计算得出：T11hdNodesd=(4)式中：T 表示树结构节点总数，d 表示满叉树的度（d1），h 表示树的高度。表 1 中列举了不同度数的满叉树在高度为710 时树结构的节点总数。表 1 满叉数节点信息层度7891017891021272555111023310933280984129 5244546121 84587 381349 525519 53197 656488 2812 441 406655 987335 9232 015 53912 093 2357137 257960 8006 725 60147 079 2088299 5932 396 74519 173 961153 391 6899597 8715 380 84048 427 561435 848 050101 111 11111 111 111111 111 1111 111 111 1112.2 模型算法优化对比本节在满 N 叉树上进行 BSCA 系列算法与原始嵌套区间系列算法的效果对比实验，包括父节点计算算法、节点索引计算算法、节点寻径算法和节点距离计算算法。测试在不同度数不同层级的树型结构中进行上述操作时，BSCA 系列算法和传统算法的时间耗费。父节点计算算法是整个嵌套区间模型的关键基础算法，其他算法均基于此算法来实现。父节点计算算法与节点的索引深度密切相关，为了方便对比，选用高度较低的树型结构进行测试。固定树高度为 3，度数从 1 到 20 动态变化，同时选取高度最高、节点索引最深的节点（即整棵树中最下层最左的节点）作为测试节点，以此来测试算法性能。例如在满 6 叉数高度为 3 的树中，选择最底层最左的高度为 3、索引为 6 的节点作为测算对象。图 8 和图 9 展示了父节点计算和节点索引计算算法的耗时对比，横轴同时表示树的度数和节点索引，纵轴表示算法时耗。以父节点计算算法为例，从图中可以得到以下几点结论：（1）原始算法随着节点索引增加，时耗呈线性增加；当节点索引较小（index6）时，经过较少的投影点逼近就可以到达父节点，原始算法要优于新PARENT 算法；（2）新 PARENT 算法随着节点索引增加，时耗维持水平不变；当节点索引 index 6 时，新 PARENT算法优于原始算法；（3）从节点索引为 6 开始，原始算法随着索引深度增加，要通过计算更多的投影点，逐步向父节点逼近，时耗也近似线性增加，时间复杂度为 O(n)；新PARENT 算法则可以通过数学公式，结合二进制移位原理，在近乎 O(1)的时间复杂度内完成计算，时耗基本不变。图8 父节点计算算法时耗对比 图 9 节点索引计算算法时耗对比在高度为 3 的满 20 叉树中进行节点寻径和距离计算实验，选取树根节点为源节点，同时选取高度最高、索引从 1到 20 的节点作为目标测试节点，分别计算源和目标节点之间的路径和距离。实验结果如图 10 和图 11 所示。从图中可以看到，BSCA 算法可以对嵌套区间模型相关算法进行整体提升，能将各种操作的时间复杂度降低到常数量级，时耗基本不会随着节点索引的增加而加大。究其本质，是因为对节点关系进行了数学建模，通过公式和二进制数乘数除原理直接对关系进行表达，而无需通过循环迭代这种耗时操作来实现。图 10 节点寻径算法时耗对比 图 11 节点距离计算算法时耗对比2.3 模型存储优化对比实验中使用公式(5)对树存储空间 D（disk storage space）进行量化，N 表示树节点总数，ni表示存储结构的分子字段，di表示存储结构分母字段：(5)2023 年第 9 期16计算机应用信息技术与信息化进行了两组实验，第一组实验中固定树度数为 3，高度从 3 8 变化；第二组实验中固定树高度为 3，度数从 3 8变化。图 12 展示了实验 1 中两种方案的 D 对比，横轴表示树高度，纵轴表示树的 D。图 13 展示了实验 2 中两种方案的D对比，横轴表示树度数，纵轴表示树的D。两组实验都表明，当树的规模较小时，两种方案的 D 相差无几，但是当树的规模逐渐增大时，新方案的 D 要明显优于原始方案。图 12 度数固定，高度变化 图 13 高度固定，度数变化3 结语本文研究了基于嵌套区间模型的无限分级层次结构这种重要的基础数据结构，利用数乘和数除与二进制移位原理的关系对相关算法进行了优化，提出了一套基于二进制移位原理的嵌套区间模型优化算法，并设计了一种新的节点存储结构，可以提高层次结构操作效率并降低磁盘存储，并通过实验进行了验证。目前该项研究成果已经在中广核智能核电项目和中广核核电设计管理平台的各个应用系统中进行大量使用，包括核电设计文件树、核电设备构型树、核电仪器测点树、FTA 实例树、知识结构树等，均取得了很好的效果，满足工程应用需求。参考文献：1 毛影.树型结构的应用与 平衡查找树的研究 D.江西:江西师范大学,2010.2 WANG Z,CHEN S.Exploiting common patterns for tree-structured dataC/the 2017 ACM International Confer-ence.Chicago:ACM Press,2017.3 陈世敏.树状结构大数据 类型的高效支持 J.大数据,2018,4(4):35-43.4 ABDELALI E,MOHAMMED C M O,MAZOUZ S.Dif-ferent approaches to modeling the trees data in relational data-baseJ.International journal of computer applications,2012,53(18):38-42.5 ALTAIBEK A A.Database design based on a domain-key normal formJ.Vestn.KazNU,2009(1):111-118.6 CELKO J,CEL KO J.Joe Celkos trees and hierarchies in SQL for smartiesJ.Elsevier Ltd Oxford,2012(1):110.7 褚衍国.编码表示法表征 树形结构及其在设备管理系统中的应用 J.机电信息,2020(36):116-117.8 石岩.采用预排序遍历树算法实现无限分级树形结构的设计及应用 J.内江科技,2011,32(12):93-94.9 林春.基于 SQL 的双编号树结构数据研究 J.现代计算机(专业版),2010(1):59-62.10 严浩,汪宇霆,张焰,等 .基于嵌套集合模型的电力文档管理系统的研究与开发 J.计算机应用与软件,2009,26(5):141-144.11 ABDELALI E,MAZOUZ S.Diff erent approaches to mod-eling the trees data in relational databaseJ.International Journal of Computer Applications,2012,53(18).12 BADDERS B,O LMSTED A.Improve CRUD performance on hierarchical data:nested interval model vs.nested set modelC/2017 12th International Conference for Internet Technology and Secured Transactions(ICITST).Cambridge,United Kingdom:IEEE,2017:370-371.13 TROPASHKO V.Trees in SQL:nested sets and materialized pathJ.URL: TROPASHKO V.Nested intervals tree encoding with con-tinued fractionsJ.arXiv preprint cs/0402051,2004.15 TROPASHKO V.Nested intervals tree encoding in SQLJ.ACM SIGMOD Record,2005,34(2):47-52.16 CONWAY J H.On numbers and gamesM.Florida,US-A:AK Peters/CRC Press,2000.17 BATES B.The stern-brocot continued fractionJ.Integers,2014,14:A39.18 TROPASHKO V.Nested intervals with farey fractionsJ.arXiv preprint cs/0401014,2004.19 NA G J,LEE S W.A relational nested interval encoding scheme for XML storage and retrievalC/Asia Information Retrieval Symposium.Springer,Berlin,Heidelberg,2005.20 VOLONKIN V.DBMS index for hierarchical data using nested intervals and residue classesC/Young Scientists International Workshop on Trends in Information Processing(YSIP).Seoul,Korea:YSIP,2014:67-76.21 MALIK OV A,TURYEV A.Nested intervals tree encoding with system of residual classesJ.International journal of computers and applications(IJCA),2011(1):2-19.【作者简介】汪鹏（1988），男，湖北仙桃人，西安电子科技大学计算机专业硕士研究生，工程师，研究方向：核电设计软件研发、智能核电、深度学习和核电知识图谱研究、项目管理等，email:weapon_。（收稿日期：2023-07-31 修回日期：2023-08-26）