一种大型动态目录树的构建及管理方法

摘要：动态目录树在信息管理系统中应用广泛，具有很强的通用性，树形组织结构构建的好坏直接影响到树管理的复杂性和查询速度，尤其对于大型动态目录树而言。文章从树的数据库设计入手，利用巧妙编程和设计有效的编码规则，在大型动态目录树的构建和管理方面提出了一套行之有效且具有通用性的管理方法。

关键词：动态目录树；构建；管理；编码规则

中图分类号：TP391 文献标识码：A文章编号：1009-3044（2023）17-0039-02

0 引言

现实世界当中，树目录的组织结构应用非常广泛，例如：一个单位的组织机构、一个国家的行政区划、学科分类、武器装备分类、文件组织结构等，一个信息系统的开发更离不开目录树的构建及管理，尤其是当组织结构非常庞大的时候，如果设计不好，效率会非常影响信息系统的正常使用，主要表现在：第一、构建一棵完整的目录树需要花费相当长的时间；第二、加载和显示目录树的时间也比较长；第三、当该目录树需要修改的节点比较多时，逐一进行维护，效率会比较低；第四、当一棵树的层级和节点数量特别大时，加载的时间会相当长，严重影响用户体验；第五、树节点的查询存在一定的难度[1]。针对上述几点问题，结合作者自身的开发体验，提出了一种大型目录树的构建及管理方法。全文的结构安排如下：第一节为树目录的数据库设计；第二节为树节点的编码规则设计；第三节为大型目录树的快速构建与遍历；第四节为大型目录树的动态管理；第五节为大型目录树的快速加载与显示；最后一节为小结。

1 树的数据库设计

在信息管理系统中，树目录的存储一般是依托SQL数据库进行的，由于本文主要针对传统C/S和B/S 信息管理系统中的树目录开发设计，树的数据库设计同样基于SQL数据库，在此基础上，结合实际开发有所优化。树目录的存储一般通过建立一张二维的关系表来表示，表字段至少包含以下三个：Node_id、Node_name、Parent_id，通过这三个字段的记录内容就可以完整地表示一棵树，但该树没有表示出同一层级下的节点顺序关系，因此，需要增加一个字段Node_no 来表示节点的显示顺序，同时也有利于优化程序开发[2-3]。

为了便于实现程序对整个树形组织结构以及对归属于树节点的实体信息进行动态管理，需建立另外两张表，下面以武器装备分类树为例进行说明。

首先通过表1定义武器装备分类树的根名称和根代码，然后根据表1定义好的根名称和根代码在表2 初始化时生成第一条节点数据，即根节点数据，其父节点代码定义为-1，节点序号定义为0，而后逐次生成其他节点及其子节点数据，表3则是具体的武器装备实体信息，通过类别代码与表2进行关联。这里的关键在于树结构表的构建，算法设计见下文。

2 树节点编码规则

良好的编码规则对树组织结构的管理至关重要，通过编码能够基本反映出各节点之间的层级关系和先后关系[4]，而后通过良好的程序设计进行数据的批量维护，既支持通过系统界面的方式对目录树进行管理，也可批量导出至Excel表方便人工进行校对和管理，修改完成后再导入至信息管理系统中。

下面以组织机构为例进行说明，树节点编码规则如下表所示：

上表中的“Z”为树根节点代码，每多出一个层级，在其后加“-”符号，并以数字1顺序编号，节点编码中有多少个“-”就代表该节点属于多少级的节点，最后一位数字代表该节点在对应层级中的显示位置，例如“Z-1-2-1-1-1”属于第五级的第一个节点。利用XMind思维导图软件可以设计目录树数据，然后导出表4或表5形式的Excel表，再根据上述的编码设计方式，写入数据库表中完成树的构建。

3 目录树的快速构建与遍历

有了目录树的数据库表设计和树节点编码规则作基础，接下来就是如何通过程序算法实现目录树的快速构建与遍历。通常情况下，初始的时候一般通过导入Excel表的方式进行树节点的批量写入，以此来完成整个目录树的构建，这样比较快速高效，避免逐个进行树节点的添加和维护，尤其是当树节点数量比较大时更加实用。

首先给出通过Excel表导入方式快速构建目录树的算法伪代码描述：开始添加根节点读取Excel表数据至DataSet集合中遍历DataSet 首先读取每行第一列数据，获取节点ID 依次读取剩余列数据，获取节点名称If 节点名称不空从节点ID中获得父节点ID和节点序号If 节点ID在treeTable不存在Insert into treeTable（nodeid，nodename，paren⁃tid，nodeno）

结束

接下来是如何对目录树进行快速遍历，主要通过哈希表的方式对树所有节点进行存储和快速查询[5]，算法伪代码描述如下：

开始

按nodeno升序查询treeTable全部数据，返回结果放至DataSet中

分别创建Hashtable和根节点BootNode（rootid，rootname）

HashTable. Add（rootid， BootNode），TreeView1.Nodes.Add（BootNode）

遍历DataSet所有行

依次获取nodeid、parentid和nodename

在Hashtable 中查找与parentid 相同的树节点，记为FNode

If FNode不为空

创建树节点TNode，其节点ID和节点Name 分别为nodeid和nodename

添加TNode作为FNode的子节点

HashTable.Add（nodeid， TNode）

结束

4 目录树的动态管理

目录树的动态管理主要包括添加树节点、删除树节点、通过名称精确或模糊查询树节点、导入全部或部分目录树、导出Excel表等操作。添加和删除树节点操作比较简单，导入全部目录树的操作在上文中已做说明，导入部分目录树的操作与其相同，设计该功能的目的是适应数据量特别大时，多人分别进行子目录树编辑，最后再分别导入完成目录树构建。

这里，主要对模糊查询树节点和导出树目录Ex⁃cel文件分别进行算法说明，首先给出模糊查询树节点算法执行步骤，如下：第1 步：定义用于存放模糊查询结果的DataT⁃able，列信息包括nodeid、nodename 和parentid，记为nodeTable；第2步：定义用于检查重复数据的idList，存放查询结果中的nodeid；第3步：定义按nodename进行模糊查询的SQL语句，将执行结果返回至DataSet；第4步：遍历DataSet，循环执行步骤5、6；第5步：获取每行的节点数据，添加至nodeTable，添加nodeid至idList中；第6步：获取该节点的所有父节点数据，如果no⁃deid 在idList 中不存在，则添加父节点数据至no⁃deTable，添加nodeid至idList中；第7步：对nodeTable按nodeid升序排序；第8步：将nodeTable通过哈希表构建的方式加入目录树显示控件TreeView1。

接下来是导出树目录Excel 文件算法执行步骤描述：第1 步：定义用于存放目录树所有节点的List，记为nodeList；第2步：从TreeView1根节点开始，遍历得到所有子节点，逐个添加至nodeList中；第3步：遍历nodeList，循环执行步骤4、5、6；第4 步：获取nodeList 中的TreeNode，定义栈stack，并将TreeNode的父节点全部压栈；第5步：对stack中的全部节点进行循环出栈操作，每个节点名称用“＼t”分割连接；第6步：按行写入输出的Excel文件中。

5 目录树的快速加载与显示

当目录树节点特别多的时候，加载显示的时间会比较长，尤其是节点在10万以上的大型目录树，严重影响用户体验。这时主要的处理方式就是初始时并不完全加载所有节点，而是在逐层展开时再加载其子节点，每点击一个“+”号，仅加载该节点的下一级所有节点，这样采用需要时再加载的方式，将显示时间分散到了各点击展开事件，能够大大改善用户体验。算法设计的思路很简单，主要是进行巧妙的编程，目录树的加载和展开事件程序设计流程描述如下。

页面或窗体初始化时，执行如下步骤：第1步：树显示控件TreeView1添加根节点；第2步：为了便于点击“+”展开，判断根节点的子节点是否为空，如果不空，添加一个空的TreeNode；第3步：关闭TreeView1的所有节点。

点击“+”进行节点展开事件时，执行如下步骤：第1步：首先获取当前选择节点的nodeid，然后到数据库表中查询该节点的下一级子节点，结果返回至DataTable；第2步：清除之前加载的空节点；第3步：遍历DataTable，循环执行步骤4、5；第4 步：获取每行数据，生成TreeNode，记为cNode，往当前节点上逐个添加cNode；第5步：判断cNode 的子节点是否为空，如果不空，添加一个空的TreeNode。

6 结束语

本文着重从实践角度对动态目录树的构建及管理方法进行阐述，所提出的方法已应用到多个信息管理系统中，通用性较强。目录树的节点数量级在20万以上时，加载和查询的速度均在毫秒级，尤其是目录树的构建可以采用多人按模板编辑Excel构建目录子树，而后再分别导入系统的方式，大大节省了构建时间。

参考文献：

[1] 景民，万其明，韩志军，等.一种基于数据库的动态Web权限树快速生成方法[J].合肥工业大学学报（自然科学版），2012，35（6）：757-761.

[2] 张志强，颜励，李岳峰.基于ASP.NET的动态查询式树型目录的实现[J].科学技术与工程，2011，11（29）：7286-7289.

[3] 李万东，郭福亮.基于用户角色的动态目录树的研究与应用[J].计算机与数字工程，2010，38（7）：189-191.

[4] 陈德军，马英哲，周祖德.一种动态目录树快速生成算法[J].武汉理工大学学报（交通科学与工程版），2008，32（1）：40-42.

[5] 刘暐，赵嵩正，殷茗.一种ASP.NET环境下面向信息统计的动态树型目录的实现[J].微型电脑应用，2010，26（2）：30-32.

【通联编辑：谢媛媛】