方耀耀（北方工業(yè)大學(xué)，北京，100041）

?

一種基于樹(shù)形結(jié)構(gòu)的Sql結(jié)果集向Json數(shù)據(jù)的轉(zhuǎn)換算法

方耀耀
（北方工業(yè)大學(xué)，北京，100041）

摘要：tree是web開(kāi)發(fā)中比較常用的展示控件，用來(lái)顯示信息的分級(jí)視圖，具有層次分明，表意清晰的特點(diǎn)。因此許多web插件中都包含tree，例如ExtJS、JQuery UI和easy UI，它們有一個(gè)共同的特點(diǎn)就是數(shù)據(jù)格式都是json，并且由于樹(shù)分層的特性使得json數(shù)據(jù)還會(huì)嵌套多層。而在關(guān)系型數(shù)據(jù)庫(kù)中取出的sql結(jié)果集卻往往不能友好地支持這種分層的json格式。本文根據(jù)具有樹(shù)形結(jié)構(gòu)的數(shù)據(jù)在數(shù)據(jù)庫(kù)中存儲(chǔ)的方式以及其與json數(shù)據(jù)之間的復(fù)雜映射關(guān)系，提出一種sql結(jié)果集到j(luò)son數(shù)據(jù)的轉(zhuǎn)換算法。

關(guān)鍵詞：樹(shù)；Sql；Json；映射

0　引言

樹(shù)是一種十分重要的數(shù)據(jù)結(jié)構(gòu)，在實(shí)際的生活中也有著廣泛的應(yīng)用，比如人事管理，組織機(jī)構(gòu)等等。許多web插件中也都包含了樹(shù)結(jié)構(gòu)的web控件，如easyui中的tree和treegrid，jQuery中的JsTree。用樹(shù)結(jié)構(gòu)的方式來(lái)顯示信息，使信息更加清晰明了，有效提高信息的顯示效果。Web應(yīng)用中，對(duì)樹(shù)結(jié)構(gòu)的引用一般采用json格式，這種格式在形式上保留了樹(shù)節(jié)點(diǎn)一對(duì)多的關(guān)系特點(diǎn)。而在關(guān)系型數(shù)據(jù)庫(kù)中，sql結(jié)果集中的每一行記錄形式上獨(dú)立，行記錄之間呈線性排列，無(wú)法體現(xiàn)行記錄之間的層次關(guān)系。在web應(yīng)用程序開(kāi)發(fā)時(shí)，首先獲取到的便是從數(shù)據(jù)庫(kù)中選出的sql結(jié)果集，我們要構(gòu)建一棵樹(shù)，必須要把這種線性的結(jié)果集轉(zhuǎn)化為具有層次性的json格式數(shù)據(jù)，這是一個(gè)復(fù)雜的過(guò)程。

介于sql結(jié)果集數(shù)據(jù)格式與web tree控件所需要的json數(shù)據(jù)格式不一致的矛盾，本文提出了一種數(shù)據(jù)格式轉(zhuǎn)換算法，從而有效解決了這個(gè)問(wèn)題。本文主體部分共分為四個(gè)部分，第一部分介紹了關(guān)系數(shù)據(jù)庫(kù)中樹(shù)結(jié)構(gòu)存儲(chǔ)的兩種表示方法以及我們需要轉(zhuǎn)換的目標(biāo)json數(shù)據(jù)的格式。第二部分詳細(xì)闡述了轉(zhuǎn)換的中間步驟和算法， 第三部分給出了相應(yīng)的實(shí)驗(yàn)結(jié)果，最后對(duì)全文作出總結(jié)， 提出算法的意義。

1　樹(shù)的存儲(chǔ)

在關(guān)系型數(shù)據(jù)庫(kù)中針對(duì)具有樹(shù)結(jié)構(gòu)的數(shù)據(jù)有兩種存儲(chǔ)表示方法：

1.1路徑表示法

路徑表示法設(shè)有一個(gè)path字段記錄了從樹(shù)的根節(jié)點(diǎn)到當(dāng)前節(jié)點(diǎn)的完整路徑。路徑表示法的優(yōu)點(diǎn)在于能夠快速查找節(jié)點(diǎn)，缺點(diǎn)在于一旦某個(gè)節(jié)點(diǎn)的位置發(fā)生變化時(shí)，就要維護(hù)該節(jié)點(diǎn)及其子節(jié)點(diǎn)的路徑，對(duì)于操作頻繁的樹(shù)這是非常繁瑣的。圖1是一顆標(biāo)準(zhǔn)的數(shù)據(jù)結(jié)構(gòu)樹(shù)的示意圖：

表1：路徑表示法

圖1.數(shù)據(jù)結(jié)構(gòu)樹(shù)

我們根據(jù)圖1的示意以及路徑表示法的規(guī)則，將其存入關(guān)系型數(shù)據(jù)庫(kù)中，得到表1，其中path字段的值就為該節(jié)點(diǎn)的完整路徑，父子節(jié)點(diǎn)之間用“-”隔開(kāi)。

表2：雙親表示法

1.2雙親表示法

雙親表示法用一個(gè)字段parentid記錄了當(dāng)前節(jié)點(diǎn)的父節(jié)點(diǎn)。與路徑表示法相反，它易于維護(hù)，某個(gè)節(jié)點(diǎn)層次關(guān)系發(fā)生變化時(shí)，只需修改它的父節(jié)點(diǎn)即可，即parentid，但查找起來(lái)較費(fèi)勁，需要層層迭代查找，樹(shù)的深度越大查找難度也就越大。同樣，根據(jù)圖1和雙親表示法規(guī)則，得到表2，其中parentId字段的值表示該節(jié)點(diǎn)的父節(jié)點(diǎn)id，如果parentId為null，則表示該節(jié)點(diǎn)為根節(jié)點(diǎn)。

1.3Json Tree

圖2　樹(shù)節(jié)點(diǎn)的實(shí)體定義

圖3　樹(shù)的json數(shù)據(jù)串

Json是一種輕量級(jí)的數(shù)據(jù)交換格式，在web開(kāi)發(fā)中相比于XML有著一定的應(yīng)用優(yōu)勢(shì)。圖2是對(duì)單個(gè)樹(shù)節(jié)點(diǎn)的實(shí)體定義，它共包含五個(gè)屬性，children表示該節(jié)點(diǎn)的子節(jié)點(diǎn)集合，反映了父節(jié)點(diǎn)與子節(jié)點(diǎn)一對(duì)多的關(guān)系。目標(biāo)json數(shù)據(jù)格式，如圖3所示。

圖4　構(gòu)造樹(shù)的流程圖

2　格式轉(zhuǎn)換算法

2.1初始化sql結(jié)果集

程序獲取到sql結(jié)果集如果呈現(xiàn)雙親表示法，我們對(duì)結(jié)果集不做變化。如果呈現(xiàn)路徑表示法，需要對(duì)結(jié)果集進(jìn)行一個(gè)預(yù)處理，將其先裝換為雙親表示法。

從表1中，隨機(jī)選取一行記錄，比如id＝6，取其path字段值”2-5-6”， 根據(jù)路徑表示法path字段的取值規(guī)則，可以知道這棵樹(shù)存在id＝2的根節(jié)點(diǎn)。存在id＝5的父節(jié)點(diǎn)。在選取id＝2的記錄時(shí)，發(fā)現(xiàn)其path字段值就是它的id，這表示它本身就是一個(gè)根節(jié)點(diǎn)，它的父節(jié)點(diǎn)就為空，即null。以此類推，可以將表1的每個(gè)記錄的path字段變成表2中的parentid字段，即把路徑表示法轉(zhuǎn)換成了雙親表示法。

2.2樹(shù)的構(gòu)建與解析

圖3是根據(jù)json tree要求的數(shù)據(jù)格式手動(dòng)拼成的。在實(shí)際程序處理過(guò)程中，不能直接按圖2的節(jié)點(diǎn)定義來(lái)構(gòu)造樹(shù)，那樣效率會(huì)很低且實(shí)現(xiàn)起來(lái)比較困難。要先對(duì)圖2中children屬性重新定義，將其類型改為String類型，使其僅僅表示該節(jié)點(diǎn)下直隸子節(jié)點(diǎn)id的集合。

圖5.解析樹(shù)的流程圖

圖4為是構(gòu)建樹(shù)的流程圖。以表2中的結(jié)果集為例說(shuō)明構(gòu)建過(guò)程。首先定義一個(gè)字符串變量root，用于記錄所有根節(jié)點(diǎn)id的集合。同時(shí)引入一個(gè)鍵值對(duì)數(shù)組kv（String id，object node），實(shí)際上kv相當(dāng)于一個(gè)小型的數(shù)據(jù)庫(kù)。其中，id即節(jié)點(diǎn)編號(hào)，node表示該節(jié)點(diǎn)的直隸子節(jié)點(diǎn)集合。然后遍歷表2中的行記錄，例如id＝8，首先試圖在鍵值對(duì)數(shù)組kv中獲取id＝8的元素，如果存在先替換該元素中除id和chilren之外的其他屬性，緩存parentId（＝7）；如果不存在，將這個(gè)元素按照?qǐng)D2的格式封裝并存入kv中，即插入“（8”，node），插入之前，同樣緩存parentId。若parentId為空，將parentId添加到root，若不為空，在kv中找出id為parentId的元素，如找不到，添加一個(gè)id 為parentId（＝7）的空節(jié)點(diǎn)。然后再將當(dāng)前節(jié)點(diǎn)的id添加賦值到其父節(jié)點(diǎn)的children屬性里。對(duì)表2結(jié)果集的每行記錄做出這樣的處理后，一棵樹(shù)即被構(gòu)建起來(lái)。

圖5是解析樹(shù)的流程圖。在樹(shù)構(gòu)建好以后，從字符串root中的id集合開(kāi)始，根據(jù)存有所有樹(shù)節(jié)點(diǎn)礎(chǔ)數(shù)據(jù)的kv，對(duì)每一個(gè)樹(shù)節(jié)點(diǎn)進(jìn)行迭代賦值，最終生成出如圖3所示的目標(biāo)格式j(luò)son數(shù)據(jù)串。

3　實(shí)驗(yàn)結(jié)果

表2中的結(jié)果集作為實(shí)驗(yàn)的輸入數(shù)據(jù)，經(jīng)過(guò)本文所提供的算法處理后得到如圖6所示的json格式的數(shù)據(jù)，圖7是這組數(shù)據(jù)在easyui下treegrid的效果展示：

如果使用全國(guó)省市縣鄉(xiāng)的數(shù)據(jù)來(lái)構(gòu)建樹(shù)，原始數(shù)據(jù)有44129條，在裝有win7系統(tǒng)，內(nèi)存為4G的機(jī)子上，java環(huán)境下運(yùn)行，構(gòu)建該樹(shù)的四級(jí)結(jié)構(gòu)需要不到1秒的時(shí)間。實(shí)驗(yàn)結(jié)果表明，這種算法是有效的，為web UI設(shè)計(jì)者創(chuàng)建Tree相關(guān)的控件帶來(lái)很大的方便。

4　結(jié)論

本文以mysql為數(shù)據(jù)庫(kù)創(chuàng)建基礎(chǔ)數(shù)據(jù)，利用鍵值對(duì)的緩存機(jī)制記錄每條數(shù)據(jù)之間的映射關(guān)系，詳細(xì)論述了從sql結(jié)果集到

json tree的轉(zhuǎn)換過(guò)程，并在java環(huán)境中進(jìn)行了實(shí)現(xiàn)和驗(yàn)證，并達(dá)到了預(yù)期的效果。通過(guò)使用文中所述轉(zhuǎn)換算法，有效地解決了sql結(jié)果集到j(luò)son格式數(shù)據(jù)的過(guò)渡問(wèn)題。對(duì)web UI開(kāi)發(fā)者高效地創(chuàng)建tree相關(guān)的web控件提供了解決方案，具有一定的參考價(jià)值。

參考文獻(xiàn)

[1]張昕，袁曉如. 樹(shù)圖可視化[J]. 計(jì)算機(jī)輔助設(shè)計(jì)與圖形學(xué)學(xué)報(bào)，2012，09：1113-1124.

[2]汪建，方洪鷹.樹(shù)形結(jié)構(gòu)在關(guān)系數(shù)據(jù)庫(kù)中的壓縮存儲(chǔ)研究.重慶交通學(xué)院學(xué)報(bào)，2006. 25（6）：155-157.

[3]嚴(yán)蔚敏，吳偉民.數(shù)據(jù)結(jié)構(gòu)[M]. 北京：清華大學(xué)出版社，2002..

[4]胡千里. 比較XML與JSON在Web中的應(yīng)用[J]. 中小企業(yè)管理與科技（下旬刊）. 2011（07） .

[5]孫勁光，吳素紅. 基于分類遍歷的碰撞檢測(cè)優(yōu)化算法[J]. 計(jì)算機(jī)應(yīng)用，2015，01：194-197.

[6]蘇翔宇. Key-Value數(shù)據(jù)庫(kù)及其應(yīng)用研究[J]. 電腦知識(shí)與技術(shù)，2012，05：1009-1011.

[7]魏紀(jì)東，王昭順，戴桂蘭，戴軍. 樹(shù)形結(jié)構(gòu)數(shù)據(jù)幀解析和處理[J]. 小型微型計(jì)算機(jī)系統(tǒng)，2010，12：2352-2354.

[8]湯曉燕. 基于EasyUI框架的Web異步樹(shù)實(shí)現(xiàn)[J]. 電腦編程技巧與維護(hù)，2012，12：92-93.

[9]朱少楠，張雪英，李明，王宇. 基于行政隸屬關(guān)系樹(shù)狀圖的地名消歧方法[J]. 地理與地理信息科學(xué)，2013，03：39-42.

[10]韓小祥. 數(shù)據(jù)綁定技術(shù)在TreeView控件中的應(yīng)用[J]. 現(xiàn)代計(jì)算機(jī)（專業(yè)版），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