一种基于树形结构的Sql结果集向Json数据的转换算法

方耀耀（北方工业大学，北京，100041）



一种基于树形结构的Sql结果集向Json数据的转换算法

方耀耀
（北方工业大学，北京，100041）

摘要：tree是web开发中比较常用的展示控件，用来显示信息的分级视图，具有层次分明，表意清晰的特点。因此许多web插件中都包含tree，例如ExtJS、JQuery UI和easy UI，它们有一个共同的特点就是数据格式都是json，并且由于树分层的特性使得json数据还会嵌套多层。而在关系型数据库中取出的sql结果集却往往不能友好地支持这种分层的json格式。本文根据具有树形结构的数据在数据库中存储的方式以及其与json数据之间的复杂映射关系，提出一种sql结果集到json数据的转换算法。

关键词：树；Sql；Json；映射

0　引言

树是一种十分重要的数据结构，在实际的生活中也有着广泛的应用，比如人事管理，组织机构等等。许多web插件中也都包含了树结构的web控件，如easyui中的tree和treegrid，jQuery中的JsTree。用树结构的方式来显示信息，使信息更加清晰明了，有效提高信息的显示效果。Web应用中，对树结构的引用一般采用json格式，这种格式在形式上保留了树节点一对多的关系特点。而在关系型数据库中，sql结果集中的每一行记录形式上独立，行记录之间呈线性排列，无法体现行记录之间的层次关系。在web应用程序开发时，首先获取到的便是从数据库中选出的sql结果集，我们要构建一棵树，必须要把这种线性的结果集转化为具有层次性的json格式数据，这是一个复杂的过程。

介于sql结果集数据格式与web tree控件所需要的json数据格式不一致的矛盾，本文提出了一种数据格式转换算法，从而有效解决了这个问题。本文主体部分共分为四个部分，第一部分介绍了关系数据库中树结构存储的两种表示方法以及我们需要转换的目标json数据的格式。第二部分详细阐述了转换的中间步骤和算法， 第三部分给出了相应的实验结果，最后对全文作出总结， 提出算法的意义。

1　树的存储

在关系型数据库中针对具有树结构的数据有两种存储表示方法：

1.1路径表示法

路径表示法设有一个path字段记录了从树的根节点到当前节点的完整路径。路径表示法的优点在于能够快速查找节点，缺点在于一旦某个节点的位置发生变化时，就要维护该节点及其子节点的路径，对于操作频繁的树这是非常繁琐的。图1是一颗标准的数据结构树的示意图：

表1：路径表示法

图1.数据结构树

我们根据图1的示意以及路径表示法的规则，将其存入关系型数据库中，得到表1，其中path字段的值就为该节点的完整路径，父子节点之间用“-”隔开。

表2：双亲表示法

1.2双亲表示法

双亲表示法用一个字段parentid记录了当前节点的父节点。与路径表示法相反，它易于维护，某个节点层次关系发生变化时，只需修改它的父节点即可，即parentid，但查找起来较费劲，需要层层迭代查找，树的深度越大查找难度也就越大。同样，根据图1和双亲表示法规则，得到表2，其中parentId字段的值表示该节点的父节点id，如果parentId为null，则表示该节点为根节点。

1.3Json Tree

图2　树节点的实体定义

图3　树的json数据串

Json是一种轻量级的数据交换格式，在web开发中相比于XML有着一定的应用优势。图2是对单个树节点的实体定义，它共包含五个属性，children表示该节点的子节点集合，反映了父节点与子节点一对多的关系。目标json数据格式，如图3所示。

图4　构造树的流程图

2　格式转换算法

2.1初始化sql结果集

程序获取到sql结果集如果呈现双亲表示法，我们对结果集不做变化。如果呈现路径表示法，需要对结果集进行一个预处理，将其先装换为双亲表示法。

从表1中，随机选取一行记录，比如id＝6，取其path字段值”2-5-6”， 根据路径表示法path字段的取值规则，可以知道这棵树存在id＝2的根节点。存在id＝5的父节点。在选取id＝2的记录时，发现其path字段值就是它的id，这表示它本身就是一个根节点，它的父节点就为空，即null。以此类推，可以将表1的每个记录的path字段变成表2中的parentid字段，即把路径表示法转换成了双亲表示法。

2.2树的构建与解析

图3是根据json tree要求的数据格式手动拼成的。在实际程序处理过程中，不能直接按图2的节点定义来构造树，那样效率会很低且实现起来比较困难。要先对图2中children属性重新定义，将其类型改为String类型，使其仅仅表示该节点下直隶子节点id的集合。

图5.解析树的流程图

图4为是构建树的流程图。以表2中的结果集为例说明构建过程。首先定义一个字符串变量root，用于记录所有根节点id的集合。同时引入一个键值对数组kv（String id，object node），实际上kv相当于一个小型的数据库。其中，id即节点编号，node表示该节点的直隶子节点集合。然后遍历表2中的行记录，例如id＝8，首先试图在键值对数组kv中获取id＝8的元素，如果存在先替换该元素中除id和chilren之外的其他属性，缓存parentId（＝7）；如果不存在，将这个元素按照图2的格式封装并存入kv中，即插入“（8”，node），插入之前，同样缓存parentId。若parentId为空，将parentId添加到root，若不为空，在kv中找出id为parentId的元素，如找不到，添加一个id 为parentId（＝7）的空节点。然后再将当前节点的id添加赋值到其父节点的children属性里。对表2结果集的每行记录做出这样的处理后，一棵树即被构建起来。

图5是解析树的流程图。在树构建好以后，从字符串root中的id集合开始，根据存有所有树节点础数据的kv，对每一个树节点进行迭代赋值，最终生成出如图3所示的目标格式json数据串。

3　实验结果

表2中的结果集作为实验的输入数据，经过本文所提供的算法处理后得到如图6所示的json格式的数据，图7是这组数据在easyui下treegrid的效果展示：

如果使用全国省市县乡的数据来构建树，原始数据有44129条，在装有win7系统，内存为4G的机子上，java环境下运行，构建该树的四级结构需要不到1秒的时间。实验结果表明，这种算法是有效的，为web UI设计者创建Tree相关的控件带来很大的方便。

4　结论

本文以mysql为数据库创建基础数据，利用键值对的缓存机制记录每条数据之间的映射关系，详细论述了从sql结果集到

json tree的转换过程，并在java环境中进行了实现和验证，并达到了预期的效果。通过使用文中所述转换算法，有效地解决了sql结果集到json格式数据的过渡问题。对web UI开发者高效地创建tree相关的web控件提供了解决方案，具有一定的参考价值。

参考文献

[1]张昕，袁晓如. 树图可视化[J]. 计算机辅助设计与图形学学报，2012，09：1113-1124.

[2]汪建，方洪鹰.树形结构在关系数据库中的压缩存储研究.重庆交通学院学报，2006. 25（6）：155-157.

[3]严蔚敏，吴伟民.数据结构[M]. 北京：清华大学出版社，2002..

[4]胡千里. 比较XML与JSON在Web中的应用[J]. 中小企业管理与科技（下旬刊）. 2011（07） .

[5]孙劲光，吴素红. 基于分类遍历的碰撞检测优化算法[J]. 计算机应用，2015，01：194-197.

[6]苏翔宇. Key-Value数据库及其应用研究[J]. 电脑知识与技术，2012，05：1009-1011.

[7]魏纪东，王昭顺，戴桂兰，戴军. 树形结构数据帧解析和处理[J]. 小型微型计算机系统，2010，12：2352-2354.

[8]汤晓燕. 基于EasyUI框架的Web异步树实现[J]. 电脑编程技巧与维护，2012，12：92-93.

[9]朱少楠，张雪英，李明，王宇. 基于行政隶属关系树状图的地名消歧方法[J]. 地理与地理信息科学，2013，03：39-42.

[10]韩小祥. 数据绑定技术在TreeView控件中的应用[J]. 现代计算机（专业版），2013，01：42-44.

An algorithm of Converting Sql result set to Json Data based on the Tree structure

Fang Yaoyao
（North China University of Technology，Beijing，100041）

Abstract：Tree is a commonly used display control in web development，Used to display information in a hierarchical view，Distinct levels and clear expression are its characteristics.Consequently，a treeview is included in Many web UI plugins， such as ExtJS、JQuery UI and easy UI，a common feature of these plugins is the JSON data format，And also the hierarchical characteristic of tree makes the JSON data be nested. however，The SQL result set taken out in the relational database is often not in a friendly way to support the JSON format.In this paper，According to the databse storage mode of the tree data and the Complex mapping relationship with JSON data，An algorithm of Converting Sql result set to Json Data is proposed.

Keywords：Tree；Sql；Json；Map