一种基于数据库的动态Web权限树快速生成方法

景 民， 万其明， 韩志军， 杨艳萍

（1.61001部队，北京 100093；2.国防大学 信息作战与指挥训练教研部，北京 100091；3.中山职业技术学院，广东 中山 528404；4.海军装备研究院，北京 100036）

树形显示（TreeView）很适合表现具有分支和层次联系的数据，如操作系统中的目录树，信息系统的行政区划导航树，安全控制系统中的访问权限树等，因此在系统开发中，经常使用树形结构来显示和存储层次数据。树形结构的算法和实现也是计算机工程的一个研究热点：文献［1］比较了在内存中生成目录树的2种算法的效率，结论是深度优先算法（Depth－First Algorithm，简称DFA）比 直 接 插 入 算 法 （Insert－into－Tree Algorithm，简称ITA）在给定试验中效率高2～3倍；文献［2］提出了一种生成目录树的快速算法，该算法以先根遍历（preorder traversal）顺序预先将目录数据存入数据库中，然后支持对数据库一次访问快速生成目录树；文献［3］提出一种在 Web中生成动态目录树的方法，实现了在Web中树形显示，利用链表预先将数据库中的目录数据读入内存，并采用ITA算法完成目录树的生成；文献［4］介绍了一种窗体编程工具提供的TreeView控件，并演示了利用该控件读取数据库中的目录树结构；文献［5］介绍了ASP.NET中提供的TreeView控件，采取先根顺序预先将目录数据存在数据库，并采用DFA算法实现了动态目录树的生成。

本文以某大型通用档案文献系统（DAG）的开发为背景，重点研究了基于数据库的动态Web角色权限树的设计和实现，如图1所示。DAG系统管理档案全宗有上百种，但测试用户11111111仅能看到其中3个全宗的文书档案信息和部分科技档案和专门档案。该用户拥有的档案树结点达到100个左右，而对于管理员级别的超级用户，拥有的档案树结点规模可以达到105左右。当前在Web上快速显示具有大量结点的动态树是比较困难的，如何高效管理这些层次数据也是一项困难的任务。本文的研究目的旨在解决以上问题，涉及的关键技术主要包括：① 实现基于Web的树形显示组件；② 实现用户权限树与数据表结构的动态对应；③ 基于数据库快速生成权限树的算法［6］。

图1 DAG的Web展现系统某授权用户的档案树视图

1 Web树形显示组件的实现

目前很多应用开发工具，如Visual Studio、Delphi、PB等，都提供了TreeView控件，在窗体应用程序中使用TreeView控件的应用已相当成熟，然而开发Web程序时实现树形显示还比较困难［5］。虽然已有厂商提供了基于 Web的Tree－View控件，如 Microsoft提供了 ASP.NET［5］技术，文献［7］在Delphi的较高版本中提供了IntraWeb技术，但使用它们的代价是必须部署庞大的.NET Framework类库，或者需要开发专门的服务支持进程，这些都对服务器的性能和配置提出了更高要求，而且影响到Web应用的跨平台部署和访问，这些限制增加了开发基于Web的树形显示的困难。在DAG系统的开发中，由于硬件保密设备的兼容要求，也限定了只能选择先前比较成熟的Web开发技术，因此没有现成的Tree－View控件可用，需要手工编写用于Web的树形显示控件。

JavaScript是Web上的一种功能强大的基于对象的脚本编程语言，它既可以直接应用于客户端的HTML文档以获得交互动态效果，还可以嵌入ASP、JSP或PHP中运行于Web服务器端，因而JavaScript具有广泛的适用性和跨平台性，获得绝大多数浏览器的支持［8］。文献［3］即采用了JavaScript实现了用于Web的树形显示，但由于其采用了JavaScript和HTML混合编程方式，并没有实现JavaScript的行为代码与HTML的格式代码的分离，而且实现的树形显示功能也较简单。DAG的Web展现系统利用JavaScript实现一个功能完善且应用简单的树形显示组件WebTreeView，其主要特点如下：

（1）利用基于对象的事件驱动模型实现了树形显示组件的类封装。组件实现代码统一保存在脚本文件web－tree－view.js中，使JavaScript的事件逻辑代码与HTML的格式代码分开，增强了程序可理解性和代码复用性。

（2）WebTreeView组件提供了丰富的属性和方法。组件主要包括2个对象：Web－Tree－View和Web－Tree－Node，前者用于显示一棵完整的Web树，后者实现了一个完整的树结点功能。

（3）WebTreeView组件应用非常方便。由于实现了类封装，可以方便地在HTML中对树对象进行调用和操作，其应用示例代码和显示效果，如图2所示。

图2 WebTreeView组件在HTML中的调用代码及相应的Web显示效果

2 权限树与数据表结构的动态对应

本节解决对众多用户的动态访问权限的分配和管理问题。设计权限树结构比目录树复杂，因为DAG系统每个用户将对应一棵具有相当规模结点的目录树（授权档案树），假设每个用户的档案树平均包含500个结点，系统支持10 000个用户，将所有用户的结点信息都存储在一个表中将达到500×104的记录规模。DAG系统设计了用户表User－Table、角色表Role－Table和档案树权限表Tree－Table，数据表设计如图3所示。DAG系统引入角色概念，用来连接用户和档案树，既有效降低了数据规模，又简化了授权过程。Tree－Table的主要属性包括 Node－ID、Node－Text、Parent－ID、Node－Level等，利用这些属性可以重构一棵树。图3所示只是构建角色权限树的一些关键字段，其他一些附加信息并未在图中显示。

利用这3个表就可以实现用户与角色，角色和权限树之间的动态对应，由于权限树不像一般的静态目录树，权限树需要经常进行授权调整，所以该表要经常进行插入、删除和更新操作，使得表中的记录不可能保持一种固定的顺序，因此文献［2，5］采取的预先按先根顺序在数据库中存储数据的做法在此无法适用。本文采取这种表设计结构既支持Web中树形显示随数据表内容动态生成，也支持数据表记录的动态改变，是一种支持完全动态的设计结构。

图3 DAG系统中动态权限树的数据表设计结构

3 权限树快速生成算法

3.1 算法A1与分析

通常在数据库中读取记录生成树结构的算法A1如下：

／／算法所涉及记录都是属于某一固定的角色，即Role－ID为一固定值。

（1）取出该Role－ID下所有记录中Node－Level的最大值M。

（2）n：＝0，从表中取出Node－Level＝0的结点，作为根生成树T。

（3）n：＝n＋1，对于T中Level＝n－1的每个结点，从表中读取其子结点，按Node－ID升序依次添加到T中的相应位置。

（4）重复步骤（3），直到n＝M－1，树T生成完毕。

算法A1采取了一种层次优先法（Breadth First Search，简称BFS），BFS是最简单的树遍历算法之一［9］。算法A1是一种“父结点找子结点”的算法，预先生成父节点，然后根据父结点再到数据库中找出该结点的子结点。下面分析算法A1的效率，由于这段算法涉及多次数据库中查询去读取记录，一般读取本地的数据库需要进行磁盘的I／O操作，时间比内存操作费时，读取网络数据库还涉及建立网络连接等时间开销，更加费时，一般一次磁盘I／O操作是一次内存操作时间的105倍左右，所以分析既包括内存操作又包括磁盘操作算法效率时，内存操作的时间基本可以忽略不计，因此可以把磁盘I／O次数作为衡量算法时间效率的指标。

假设树T是一个m层的完全n叉数，则共需要的I／O次数N为：

所以，算法A1是一个时间开销随着n和m成指数增长的算法，当n和m比较小时，比如m、n都为3时，N为5次；m、n都等于4时，N为22次；m、n都等于5时，N已经超过100次；m、n都为6时，N已超过1 000次；而当m、n各等于10时，N便超过了109次。假设一次数据库访问时间为1s，当树的层数和叉数各为5时，所需时间就超过了100s，因此当生成的树超过一定规模，高昂的时间开销就令算法A1失去了实用价值。

在实际的系统实现中，可以针对算法A1时间开销大的弊端进行改进和优化，如系统初次运行时只生成部分树结点，比如只生成树的一级结点，待用户需要点击展开某个结点的时候，再去访问一次数据库将该结点下面的结点生成出来，通常一次数据库访问的时间是秒级，对于几秒的等待时间用户并不会觉得慢，这也是很多系统采用的一种实际做法。然后这种一次仅生成部分树的折中做法，虽然解决了用户等待时间过长的问题，却满足不了展开全部结点的需求，比如有时某些查询和统计功能需要一次生成整棵树。

针对上述2种做法的不足，有些系统会采取一次将涉及的全部结点读取到内存中的线性表，然后再对线性表操作进行树的重构，比如文献［3］，这样虽然可以加快树的生成，但却耗费额外的内存空间，降低了算法的空间效率。

算法A1之所以频繁访问数据库，是因为在树生成的过程中，当生成了一个结点后，然后就为该结点到数据库中找到它所有的子结点，这种父结点找子结点的做法决定了算法A1必须多次访问数据库，因为子结点还在数据库的表中。如果将这个过程逆过来，在树生成的时候，让子结点主动找父结点，由于父结点已早于子结点在内存中生成，子结点可以快速地在内存中找到父结点，然后加入到内存的树中。子结点找父结点是在内存中进行，而父结点找子结点却需要读库，这是两者存在巨大时间差别的关键所在。

3.2 本文算法与分析

本文依据前面设计的动态数据表结构，提出一种新算法A2，算法A2在不增加额外内存空间的情况下，实现了对数据库一次访问快速生成全部树结构。

将算法A1的过程逆向，即“父结点找子结点”的过程改为“子结点找父结点”，就得到了算法A2，算法A2的实现也很简单，共分为2步：

（1）在数据库中按先根顺序访问Tree－Table中Role－ID为某一固定值的所有结点，在访问每一个记录时进行步骤（2）。

（2）根据该记录生成一个树结点，按深度优先算法（DFA）插入到树T中。

第2步完全在内存中进行，而且采用了效率较高的 DFA 算法［1］，DFA 算法可参阅文献［1，9］，在此不再赘述。

第1步是实现算法A2的关键，实现了对表Tree－Table的一次访问，取出所需要的全部记录，下面对该步实现过程进行详细说明。按先根顺序返回结点记录，第1条记录代表根结点。要想在数据库中得到这样的记录顺序，最理想的情况是表中的记录预先按这种顺序保存，如文献［2，5］就采用了这样的做法。按序预先存储记录对于静态的目录树结构是可以的，但是对于动态的权限树，由于经常需要对权限进行重新分配，造成Tree－Table的频繁操作，使其不能保持一种固定的顺序。一个很自然的想法是每次访问前对表重新排序，然而对表重新排序是一个很耗时的过程，而且表Tree－Table存储的不是一棵树的记录，而是所有权限树森林的记录，对森林排序代价更高。

一个可行的办法是按先根顺序建立一个该角色下的所有结点的临时视图V－t，当完成第1步对V－t的访问后，再删去该临时视图，由此在不增加额外空间的条件下，完成了第1步实现。其实还存在可以优化的余地，如果对SQL语言非常熟悉的话，就会发现某些数据库可以支持按树序访问层次数据：

Select＊ FromTree－Table Where Role－ID＝0Connect By Prior Node－ID＝Parent－IDStart With Node－ID＝RootID，

其中，加黑的是SQL语言的关键字；RootID是根节点的序号，该查询将按先根顺序返回数据记录，这条Select语句是符合SQL92标准的一条语句，可被Oracle支持。

图4显示了采用本文方法，生成n层n叉树时（达到测试结点个数即停止生成）结点个数与所用时间的关系。

图4 生成权限树t与lg M的拟合曲线

从图4中可以看出时间t与树结点规模的对数lg M基本成一种曲线增长关系，是一种在一定范围内的缓慢增长曲线。

4 结束语

开发高效的系统经常需要综合优化技术，本文利用JavaScript语言将树形的生成和显示交由客户端浏览器完成，将按先根顺序查询的工作交给后台数据库系统完成，将数据记录读出并转化为生成树结构的脚本交由Web服务器完成，合理划分了三者之间的负载，将交互通信和互相等待的开销减至最低；同时在每一个计算单元内部，也努力改进数据结构和算法设计，提高了系统运行效率。本文提出的基于数据库的动态Web权限树生成方法是一种兼顾时间和空间效率的高效方法，在DAG的Web展现系统中取得了满意的应用效果，几秒时间内便可生成上千结点规模动态权限树。

系统性能的综合优化，需要对系统进行全面的把握，需要良好的数据结构设计和充分挖掘后台数据库的查询优化潜力，更需要在Web服务层采用高效的算法，并为客户端分配合理的负载，这些措施都体现了计算机科学中的权衡（trade－off）思想，因此系统研发既需要进行理论研究，也需要积累工程经验。

［1］韩 卫，宋立明.快速构建目录树的算法研究［J］.科学技术与工程，2009，9（20）：6208－6210.

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

［3］张玉芳，胡向前，熊忠阳.在JSP中使用递归算法生成目录树［J］.计算机工程与设计，2005，26（1）：44－46.

［4］周滇苏，曹 维.动态目录树生成方法探讨［J］.装甲兵装备技术研究，2004（3）：37－41.

［5］周炎涛，陈贤谋.ASP.NET中TreeView控件与数据库结合创建动态目录树［J］.航空计算技术，2004，34（2）：25－27.

［6］胡学钢，王东波，吴共庆.一种基于层次树的高效密度聚类算法［J］.合肥工业大学学报：自然科学版，2008，31（2）：187－190，195.

［7］董立达，权重民，问鸿滨.Delphi7Web开发与应用［M］.北京：机械工业出版社，2003：1－50.

［8］阮文江.Java Script程序设计基础教程［M］.北京：人民邮电出版社，2004：50－100.

［9］Cormen T H.算法导论［M］.潘金贵，译.北京：机械工业出版社，2011：531.