陳世敏

中國(guó)科學(xué)院計(jì)算技術(shù)研究所，北京 100190

1 引言

大數(shù)據(jù)產(chǎn)業(yè)是全球高科技競(jìng)爭(zhēng)的前沿領(lǐng)域。大數(shù)據(jù)技術(shù)的推廣應(yīng)用對(duì)國(guó)家經(jīng)濟(jì)、政治、法治、科技、文化、教育、民生、社會(huì)、生態(tài)文明、國(guó)家安全等方面，都會(huì)產(chǎn)生深遠(yuǎn)的影響。傳統(tǒng)的關(guān)系數(shù)據(jù)模型從20世紀(jì)70年代出現(xiàn)至今，在商用數(shù)據(jù)處理方面得到了廣泛的應(yīng)用。但是，關(guān)系模型的簡(jiǎn)單、扁平的二維表結(jié)構(gòu)無(wú)法滿足各行各業(yè)（如社交網(wǎng)絡(luò)、物聯(lián)網(wǎng)、醫(yī)療生物、金融等）日益豐富的大數(shù)據(jù)表達(dá)和處理的需求。于是，實(shí)踐中涌現(xiàn)了多種非傳統(tǒng)的大數(shù)據(jù)類(lèi)型，出現(xiàn)了一批支持非傳統(tǒng)數(shù)據(jù)類(lèi)型的大數(shù)據(jù)系統(tǒng)，被統(tǒng)稱為NoSQL數(shù)據(jù)庫(kù)系統(tǒng)。其中，應(yīng)用最廣泛的是鍵值對(duì)（keyvalue）數(shù)據(jù)類(lèi)型、圖（graph）數(shù)據(jù)類(lèi)型和以JSON（JavaScript object notation）等為代表的樹(shù)狀結(jié)構(gòu)數(shù)據(jù)類(lèi)型（treestructured data type）。

樹(shù)狀結(jié)構(gòu)數(shù)據(jù)類(lèi)型可直觀地表達(dá)高級(jí)程序設(shè)計(jì)語(yǔ)言中類(lèi)（class）、結(jié)構(gòu)（struct）等豐富的結(jié)構(gòu)，能夠簡(jiǎn)潔地支持嵌套、多值和缺值，已被廣泛應(yīng)用于社交網(wǎng)絡(luò)數(shù)據(jù)服務(wù)、Web服務(wù)、數(shù)據(jù)交換格式、分布式系統(tǒng)協(xié)議、物聯(lián)網(wǎng)等，是一種重要的大數(shù)據(jù)類(lèi)型。實(shí)踐中常見(jiàn)的樹(shù)狀結(jié)構(gòu)數(shù)據(jù)類(lèi)型有JSON、Protocol Buffers等。JSON是JavaScript語(yǔ)言標(biāo)準(zhǔn)的一個(gè)子集，常常作為數(shù)據(jù)輸出和數(shù)據(jù)交換的類(lèi)型。Protocol Buffers是Google公司推出的一種數(shù)據(jù)類(lèi)型，是實(shí)現(xiàn)分布式系統(tǒng)內(nèi)部通信協(xié)議的數(shù)據(jù)格式，也是Google公司的Dremel[1]和BigQuery[2]等大數(shù)據(jù)系統(tǒng)的數(shù)據(jù)類(lèi)型。

本文將對(duì)以JSON為代表的樹(shù)狀結(jié)構(gòu)大數(shù)據(jù)類(lèi)型進(jìn)行深入介紹，首先舉例說(shuō)明樹(shù)狀結(jié)構(gòu)大數(shù)據(jù)的含義，然后從多個(gè)角度說(shuō)明樹(shù)狀結(jié)構(gòu)大數(shù)據(jù)的價(jià)值和意義，最后結(jié)合筆者近期的研究工作，說(shuō)明樹(shù)狀結(jié)構(gòu)大數(shù)據(jù)類(lèi)型的處理和支持。

2 樹(shù)狀結(jié)構(gòu)大數(shù)據(jù)類(lèi)型

樹(shù)狀結(jié)構(gòu)大數(shù)據(jù)類(lèi)型包括多種新型數(shù)據(jù)類(lèi)型，例如JSON、Protocol Buffers、Apache Avro等。這些數(shù)據(jù)類(lèi)型的具體表現(xiàn)形式不同，但是它們都可以表達(dá)嵌套、多值、缺值等豐富復(fù)雜的記錄結(jié)構(gòu)，具有相似的結(jié)構(gòu)特點(diǎn)，可以互相轉(zhuǎn)化。它們的記錄結(jié)構(gòu)都可以采用語(yǔ)法樹(shù)來(lái)表達(dá)，因此將它們統(tǒng)稱為樹(shù)狀結(jié)構(gòu)大數(shù)據(jù)類(lèi)型。

以JSON為例，一個(gè)JSON類(lèi)型的數(shù)據(jù)記錄如下：

JSON用花括號(hào)、方括號(hào)、引號(hào)、冒號(hào)、逗號(hào)等標(biāo)點(diǎn)符號(hào)來(lái)表達(dá)記錄的結(jié)構(gòu)。具體而言，花括號(hào)表示一個(gè)對(duì)象，對(duì)象的多個(gè)屬性以逗號(hào)隔開(kāi)。方括號(hào)表示一個(gè)數(shù)組，數(shù)組的多個(gè)元素以逗號(hào)隔開(kāi)。一個(gè)屬性由屬性名和屬性值組成，兩者由冒號(hào)隔開(kāi)，屬性名以引號(hào)標(biāo)注，屬性值可以是原子的字符串、數(shù)值、布爾值等類(lèi)型，也可以是嵌套的對(duì)象或數(shù)組。在這個(gè)例子中，記錄是一個(gè)對(duì)象，由3個(gè)頂層屬性geo、retweet_count和user組成。geo屬性的屬性值是一個(gè)嵌套對(duì)象，內(nèi)部只有一個(gè)coordinates屬性，其屬性值是一個(gè)數(shù)組，數(shù)組的每個(gè)元素是一個(gè)數(shù)值；retweet_count屬性的屬性值是一個(gè)數(shù)值；user屬性的屬性值是一個(gè)嵌套對(duì)象，包括status、favorite、followers和id 4個(gè)屬性，而這4個(gè)屬性的屬性值都是數(shù)值。

將上述記錄的內(nèi)部結(jié)構(gòu)表達(dá)為一棵樹(shù)，如圖1所示。

樹(shù)根代表整個(gè)記錄。樹(shù)中的一個(gè)節(jié)點(diǎn)對(duì)應(yīng)記錄中的一個(gè)屬性，葉子節(jié)點(diǎn)對(duì)應(yīng)屬性值為原子類(lèi)型的屬性，而非葉子節(jié)點(diǎn)則對(duì)應(yīng)屬性值是嵌套值的屬性?；疑墓?jié)點(diǎn)代表多值，即數(shù)組的情況。在這個(gè)例子中，最高層的3個(gè)屬性geo、retweet_count和user對(duì)應(yīng)根的3個(gè)孩子節(jié)點(diǎn)。其中，retweet_count的屬性值是原子的數(shù)值類(lèi)型，因此retweet_count節(jié)點(diǎn)沒(méi)有孩子節(jié)點(diǎn)，是一個(gè)葉子節(jié)點(diǎn)。user的屬性值是一個(gè)嵌套對(duì)象，由status、favorite、followers和id 4個(gè)屬性組成，因此user節(jié)點(diǎn)有4個(gè)孩子節(jié)點(diǎn)。而這4個(gè)屬性的屬性值都是原子類(lèi)型，因此它們都是葉子節(jié)點(diǎn)。geo屬性的屬性值是一個(gè)嵌套對(duì)象，包括一個(gè)coordinates屬性，因此geo節(jié)點(diǎn)有一個(gè)coordinates孩子節(jié)點(diǎn)。coordinates屬性的屬性值是一個(gè)數(shù)組，而數(shù)組的每個(gè)元素是原子類(lèi)型，用灰色的coordinates節(jié)點(diǎn)表達(dá)數(shù)組，該節(jié)點(diǎn)沒(méi)有孩子，是葉子節(jié)點(diǎn)。

JSON、Protocol Buffers、Apache Avro等多種樹(shù)狀結(jié)構(gòu)數(shù)據(jù)類(lèi)型都可以把記錄結(jié)構(gòu)表達(dá)為語(yǔ)法樹(shù)的形式?？梢酝ㄟ^(guò)如下遞歸定義更確切地表達(dá)樹(shù)狀數(shù)據(jù)類(lèi)型Ttree：

由圖6、圖7和表4知，各目標(biāo)函數(shù)隨著算法迭代次數(shù)的增加不斷減小，EMBBO算法較3種MBBO算法、GA的收斂性和搜索效率更好，輸出的解集質(zhì)量更優(yōu)。

圖1 對(duì)應(yīng)于JSON記錄實(shí)例的語(yǔ)法樹(shù)

一個(gè)樹(shù)狀數(shù)據(jù)記錄可以遞歸地表達(dá)為一棵樹(shù)，Ttree是樹(shù)根，樹(shù)根必須是Tobject，每個(gè)Tobject由屬性名key和屬性值value組成。除了Tobject，還定義了數(shù)組Tarray和原子類(lèi)型Tprimitive。而value類(lèi)型則可以遞歸地定義為原子類(lèi)型、對(duì)象類(lèi)型、數(shù)組類(lèi)型。樹(shù)狀結(jié)構(gòu)數(shù)據(jù)類(lèi)型可以表達(dá)多層復(fù)雜的嵌套，每層嵌套表現(xiàn)為樹(shù)的一個(gè)內(nèi)部節(jié)點(diǎn)，而樹(shù)的葉子節(jié)點(diǎn)是原子類(lèi)型。

3 實(shí)用價(jià)值

與關(guān)系數(shù)據(jù)模型相比，樹(shù)狀結(jié)構(gòu)大數(shù)據(jù)類(lèi)型的每個(gè)記錄具有更加靈活豐富的結(jié)構(gòu)，因此在實(shí)踐中得到了廣泛的應(yīng)用。例如，社交網(wǎng)絡(luò)數(shù)據(jù)服務(wù)Twitter等輸出的數(shù)據(jù)類(lèi)型就是JSON，Web 2.0 RESTful架構(gòu)中推薦的數(shù)據(jù)交換格式是JSON，許多提供公共數(shù)據(jù)下載的網(wǎng)站可以使用JSON下載數(shù)據(jù)，Apache Hadoop、HBase等開(kāi)源大數(shù)據(jù)系統(tǒng)中分布式通信協(xié)議采用了Protocol Buffers來(lái)實(shí)現(xiàn)。此外，許多物聯(lián)網(wǎng)單片機(jī)芯片（如Arduino、DragonBoard、BeagleBone等）支持JSON格式的數(shù)據(jù)輸出。大量的原始數(shù)據(jù)是樹(shù)狀結(jié)構(gòu)數(shù)據(jù)類(lèi)型。

樹(shù)狀結(jié)構(gòu)大數(shù)據(jù)類(lèi)型的3個(gè)主要特點(diǎn)使其具有廣泛的實(shí)用價(jià)值，具體如下。

（1）豐富的結(jié)構(gòu)

樹(shù)狀結(jié)構(gòu)大數(shù)據(jù)類(lèi)型支持嵌套、多值、缺值等豐富的結(jié)構(gòu)，可以非常方便地表達(dá)程序設(shè)計(jì)語(yǔ)言中“對(duì)象”等復(fù)雜類(lèi)型的數(shù)據(jù)，例如C語(yǔ)言中的struct、C++/Java等語(yǔ)言中的class、Python語(yǔ)言中的dictionary等類(lèi)型。因此，可以采用樹(shù)狀結(jié)構(gòu)大數(shù)據(jù)類(lèi)型自然地對(duì)應(yīng)用程序的內(nèi)存數(shù)據(jù)結(jié)構(gòu)進(jìn)行序列化，便于寫(xiě)入外存和進(jìn)行網(wǎng)絡(luò)通信，并保持原始內(nèi)存數(shù)據(jù)結(jié)構(gòu)的特征。與之相比，關(guān)系數(shù)據(jù)模型采用簡(jiǎn)單、扁平的記錄結(jié)構(gòu)，記錄的每個(gè)屬性都是原子類(lèi)型，因此對(duì)于應(yīng)用程序數(shù)據(jù)結(jié)構(gòu)中的嵌套、多值等情況來(lái)說(shuō)，必須采用特殊的編碼，將數(shù)據(jù)轉(zhuǎn)換為關(guān)系數(shù)據(jù)模型允許的記錄格式，才可以完成序列化?？梢?jiàn)，樹(shù)狀結(jié)構(gòu)大數(shù)據(jù)類(lèi)型豐富的結(jié)構(gòu)可以更好地支持大數(shù)據(jù)時(shí)代多種多樣的應(yīng)用。

（2）靈活的類(lèi)型

JSON類(lèi)型不需要事先定義記錄的類(lèi)型就可以直接使用。關(guān)系數(shù)據(jù)庫(kù)中先要采用create table建立數(shù)據(jù)表，才可以加載或插入數(shù)據(jù)記錄。而在JSON中，數(shù)據(jù)記錄的結(jié)構(gòu)是在每條記錄中定義的。如第2節(jié)中的例子，JSON采用標(biāo)點(diǎn)符號(hào)定義每條記錄的具體結(jié)構(gòu)。因此，JSON允許靈活地增、刪、改記錄結(jié)構(gòu)，允許將多種結(jié)構(gòu)的記錄放入相同的數(shù)據(jù)集，這可以簡(jiǎn)化很多大數(shù)據(jù)應(yīng)用領(lǐng)域的數(shù)據(jù)存儲(chǔ)和管理。例如，在數(shù)據(jù)采集中，經(jīng)常遇到同種數(shù)據(jù)可能有很多小的類(lèi)別的情況，雖然所有數(shù)據(jù)都有一些公共屬性，但是不同類(lèi)別還包括許多各自特殊的屬性。在這種情況下，如果采用關(guān)系模型，就需要為每個(gè)小類(lèi)別采用create table建立一個(gè)新表，數(shù)據(jù)存儲(chǔ)和后續(xù)的數(shù)據(jù)處理就需要面對(duì)大量的關(guān)系表，使整個(gè)過(guò)程十分繁雜。而采用JSON樹(shù)狀結(jié)構(gòu)數(shù)據(jù)類(lèi)型，就可以把所有小類(lèi)別的數(shù)據(jù)記錄都存儲(chǔ)在一個(gè)數(shù)據(jù)集中，每個(gè)記錄允許不同的屬性（實(shí)際上是允許許多缺值的屬性）在一個(gè)數(shù)據(jù)集中對(duì)所有數(shù)據(jù)進(jìn)行統(tǒng)一的管理，大大簡(jiǎn)化了數(shù)據(jù)管理、編程處理的成本。

（3）低廉的成本

XML也可以表達(dá)豐富的嵌套、多值結(jié)構(gòu)。實(shí)際上，數(shù)據(jù)庫(kù)領(lǐng)域一直希望推動(dòng)XML成為應(yīng)用數(shù)據(jù)存儲(chǔ)和交換的標(biāo)準(zhǔn)。但是，XML的表達(dá)引入了很高的成本，包括DTD類(lèi)型的定義和解析、XML標(biāo)簽占用的空間等。與之相比，JSON等樹(shù)狀結(jié)構(gòu)數(shù)據(jù)類(lèi)型更加簡(jiǎn)潔輕量。以JSON為例，記錄結(jié)構(gòu)采用簡(jiǎn)單的標(biāo)點(diǎn)符號(hào)來(lái)表達(dá)，便于人的理解和程序的解析，而且這種表達(dá)方式引入的空間開(kāi)銷(xiāo)很小。因此，在實(shí)踐中JSON等樹(shù)狀結(jié)構(gòu)數(shù)據(jù)類(lèi)型已經(jīng)逐漸取代了XML，成為事實(shí)上數(shù)據(jù)存儲(chǔ)和交換的標(biāo)準(zhǔn)。

4 理論意義

樹(shù)狀結(jié)構(gòu)大數(shù)據(jù)類(lèi)型不僅具有很強(qiáng)的實(shí)用價(jià)值，而且具有重要的理論意義，主要表現(xiàn)為以下兩個(gè)方面。

（1）關(guān)系數(shù)據(jù)模型的第4次變革

（2）一種通用的大數(shù)據(jù)模型

樹(shù)狀數(shù)據(jù)結(jié)構(gòu)類(lèi)型可以表達(dá)豐富的結(jié)構(gòu)，包括嵌套、多值、缺值等結(jié)構(gòu)。相對(duì)于單個(gè)鍵值對(duì)、單個(gè)圖的頂點(diǎn)、單條圖的邊、單個(gè)圖的屬性、單條關(guān)系型記錄等，單條樹(shù)狀結(jié)構(gòu)的數(shù)據(jù)記錄的結(jié)構(gòu)可以更加豐富復(fù)雜。因此，實(shí)際上很容易把鍵值對(duì)、圖的頂點(diǎn)、邊、屬性和關(guān)系型記錄寫(xiě)成樹(shù)狀數(shù)據(jù)結(jié)構(gòu)類(lèi)型的數(shù)據(jù)，而且可能有多種不同的寫(xiě)法，從而可能以樹(shù)狀結(jié)構(gòu)大數(shù)據(jù)類(lèi)型為基礎(chǔ)，實(shí)現(xiàn)對(duì)其他流行的大數(shù)據(jù)類(lèi)型的支持。因此，樹(shù)狀結(jié)構(gòu)大數(shù)據(jù)類(lèi)型是一種通用的大數(shù)據(jù)模型。

樹(shù)狀結(jié)構(gòu)大數(shù)據(jù)類(lèi)型具有很強(qiáng)的表達(dá)能力，其難點(diǎn)在于如何高效地支持樹(shù)狀大數(shù)據(jù)類(lèi)型的存儲(chǔ)和運(yùn)算，以支持其豐富、靈活的結(jié)構(gòu)。

5 現(xiàn)有的樹(shù)狀結(jié)構(gòu)數(shù)據(jù)處理系統(tǒng)

現(xiàn)有的樹(shù)狀結(jié)構(gòu)數(shù)據(jù)處理系統(tǒng)主要有以下3種。

（1）擴(kuò)展關(guān)系型數(shù)據(jù)庫(kù)系統(tǒng)

主流的關(guān)系數(shù)據(jù)庫(kù)系統(tǒng)Oracle、Microsoft SQL Server、IBM DB2和開(kāi)源數(shù)據(jù)庫(kù)系統(tǒng)PostgreSQL等都擴(kuò)展了對(duì)JSON的支持?；舅悸肥菍⒄麄€(gè)JSON記錄以文本或者二進(jìn)制格式存放在關(guān)系表的單個(gè)屬性中，提供內(nèi)置函數(shù)，支持JSON的解析和訪問(wèn)，從而可以在SQL語(yǔ)句中動(dòng)態(tài)地解析JSON記錄，提取JSON屬性值，并用于SQL查詢[4]，這也是SQL/JSON工作組的基本解決方案。但是，這種解決方案對(duì)數(shù)據(jù)分析的支持較差。數(shù)據(jù)分析操作通常只關(guān)心JSON記錄的少量屬性，存儲(chǔ)和讀取整條JSON記錄會(huì)導(dǎo)致大量不必要的I/O訪問(wèn)。而且，每次執(zhí)行SQL查詢語(yǔ)句，都要?jiǎng)討B(tài)地解析JSON記錄，引入很大的性能開(kāi)銷(xiāo)。

（2）行式樹(shù)狀結(jié)構(gòu)數(shù)據(jù)處理系統(tǒng)

以MongoDB為代表的文檔存儲(chǔ)（document store）系統(tǒng)支持JSON的行式存儲(chǔ)和處理。MongoDB是通過(guò)C/C++實(shí)現(xiàn)的，采用二進(jìn)制的BSON格式存儲(chǔ)JSON記錄。對(duì)于JSON的屬性名，BSON仍然存儲(chǔ)其字符串；而對(duì)于JSON的原子屬性值，BSON采用二進(jìn)制存儲(chǔ)。MongoDB提供一組JavaScript編程界面，可以執(zhí)行與SQL查詢功能相當(dāng)?shù)牟僮鳌：蛿U(kuò)展關(guān)系型數(shù)據(jù)庫(kù)系統(tǒng)相似，由于采用行式存儲(chǔ)，數(shù)據(jù)分析操作會(huì)導(dǎo)致大量的I/O開(kāi)銷(xiāo)。此外，在訪問(wèn)JSON嵌套結(jié)構(gòu)時(shí)，MongoDB需要在每個(gè)嵌套層次進(jìn)行字符串比較，搜索對(duì)應(yīng)的屬性名，性能代價(jià)較大。

（3）列式樹(shù)狀結(jié)構(gòu)數(shù)據(jù)處理系統(tǒng)

Google Dremel提出了Protocol Buffers數(shù)據(jù)的列式存儲(chǔ)編碼方式[1]。Apache Parquet是Dremel的開(kāi)源實(shí)現(xiàn)，支持Parquet格式的文件存取和訪問(wèn)。與Apache Hive結(jié)合，就可以將數(shù)據(jù)存放在Parquet列式文件中，并利用Hive實(shí)現(xiàn)基于MapReduce的SQL查詢，對(duì)大規(guī)模的樹(shù)狀數(shù)據(jù)進(jìn)行分析。由于采用了列式存儲(chǔ)，Parquet可以有效地避免讀取不相關(guān)屬性的I/O操作。但其基于MapReduce和Java的實(shí)現(xiàn)影響了查詢的效率。

上述3種系統(tǒng)都采用完全通用的設(shè)計(jì)，為了支持樹(shù)狀結(jié)構(gòu)數(shù)據(jù)類(lèi)型可能出現(xiàn)的豐富、復(fù)雜的嵌套和多值結(jié)構(gòu)，引入了復(fù)雜的算法。例如，為了把多個(gè)分別存儲(chǔ)的數(shù)據(jù)列組裝還原成原始記錄，Dremel的組裝算法要建立一個(gè)有限狀態(tài)自動(dòng)機(jī)，根據(jù)自動(dòng)機(jī)和列式文件中的特殊編碼完成組裝。除了上述討論每種系統(tǒng)各自的性能問(wèn)題外，這種完全通用的解決方案本身也存在相對(duì)高昂的代價(jià)。

6 樹(shù)狀大數(shù)據(jù)的高效支持：赤兔

筆者設(shè)計(jì)實(shí)現(xiàn)了一個(gè)樹(shù)狀結(jié)構(gòu)數(shù)據(jù)管理系統(tǒng)——赤兔（system for tree structured data, Steed）[5]。Steed是采用C/C++語(yǔ)言實(shí)現(xiàn)的，支持通用的樹(shù)狀結(jié)構(gòu)數(shù)據(jù)存儲(chǔ)和類(lèi)似SQL的查詢處理，包括選擇、投影、連接、分組、聚集、排序等多種運(yùn)算。Steed同時(shí)支持行式和列式的樹(shù)狀結(jié)構(gòu)數(shù)據(jù)存儲(chǔ)，以適應(yīng)不同類(lèi)型應(yīng)用的需要。系統(tǒng)能夠自動(dòng)提取JSON的語(yǔ)法樹(shù)，從而有效地壓縮了對(duì)屬性名的存儲(chǔ)。圖2展示了Steed的系統(tǒng)結(jié)構(gòu)，主要包括數(shù)據(jù)解析模塊、數(shù)據(jù)存儲(chǔ)模塊和查詢執(zhí)行模塊。數(shù)據(jù)解析模塊讀取并解析文本的JSON或Protocol Buffers數(shù)據(jù)，將其轉(zhuǎn)化為行式或者列式的二進(jìn)制格式，存儲(chǔ)在數(shù)據(jù)存儲(chǔ)模塊中。數(shù)據(jù)存儲(chǔ)模塊存儲(chǔ)行式或列式二進(jìn)制數(shù)據(jù)，支持兩種格式數(shù)據(jù)的相互轉(zhuǎn)換。查詢執(zhí)行模塊支持類(lèi)SQL的查詢，支持行式和列式數(shù)據(jù)的查詢處理。整個(gè)查詢執(zhí)行采用傳統(tǒng)關(guān)系型數(shù)據(jù)庫(kù)中查詢樹(shù)的方式實(shí)現(xiàn)。

（1）簡(jiǎn)單路徑及其優(yōu)化

圖2 Steed系統(tǒng)結(jié)構(gòu)

通過(guò)對(duì)現(xiàn)實(shí)的樹(shù)狀結(jié)構(gòu)數(shù)據(jù)進(jìn)行分析，提出了一種頻繁子模式——簡(jiǎn)單路徑（simple path）。在樹(shù)狀結(jié)構(gòu)數(shù)據(jù)的語(yǔ)法樹(shù)中，存在許多從樹(shù)根到葉子的路徑。如果在根到葉子的路徑上存在很多的多值（數(shù)組）節(jié)點(diǎn)，那么其存儲(chǔ)和處理就要考慮很多可能出現(xiàn)的情況，相對(duì)復(fù)雜。相反，當(dāng)路徑中不存在多值節(jié)點(diǎn)或僅存在一個(gè)多值節(jié)點(diǎn)時(shí)，就有可能進(jìn)行簡(jiǎn)化的處理。這種一條包含最多一個(gè)多值節(jié)點(diǎn)的從樹(shù)根到葉子的路徑就是簡(jiǎn)單路徑。筆者分析了現(xiàn)實(shí)的樹(shù)狀結(jié)構(gòu)數(shù)據(jù)的結(jié)構(gòu)，發(fā)現(xiàn)簡(jiǎn)單路徑大量存在。例如，Twitter數(shù)據(jù)的語(yǔ)法樹(shù)中包含203個(gè)葉子節(jié)點(diǎn)，其中195個(gè)葉子節(jié)點(diǎn)對(duì)應(yīng)的路徑是簡(jiǎn)單的，即96%的路徑是簡(jiǎn)單路徑。此外，還分析了Yahoo、IMDB、Sina Weibo等多種表述性狀態(tài)傳遞（representational state transfer，REST）服務(wù)數(shù)據(jù)，發(fā)現(xiàn)超過(guò)99%的路徑是簡(jiǎn)單的。其中，Sina Weibo提供104種不同的調(diào)用服務(wù)，這些服務(wù)數(shù)據(jù)對(duì)應(yīng)的語(yǔ)法樹(shù)中67%的路徑不包含多值節(jié)點(diǎn)，32%的路徑包含一個(gè)多值節(jié)點(diǎn)，只有1%的路徑是包含兩個(gè)到多個(gè)多值節(jié)點(diǎn)的復(fù)雜路徑。筆者分析了Apache Hadoop中所有449種非空的基于Protocol Buffers的通信協(xié)議，發(fā)現(xiàn)97%的路徑是簡(jiǎn)單路徑。在其他多類(lèi)現(xiàn)實(shí)數(shù)據(jù)集中，都觀察到相似的現(xiàn)象：絕大多數(shù)路徑是簡(jiǎn)單路徑。針對(duì)簡(jiǎn)單路徑，Steed優(yōu)化了列式存儲(chǔ)、列式組裝和內(nèi)存行式格式。

（2）MongoDB+Steed

MongoDB是對(duì)JSON文件進(jìn)行存儲(chǔ)和處理的大數(shù)據(jù)系統(tǒng)。MongoDB是采用C/C++語(yǔ)言實(shí)現(xiàn)的，包括Mongod和Mongos兩個(gè)主要部分。其中，Mongod負(fù)責(zé)單機(jī)的數(shù)據(jù)管理和運(yùn)算，而Mongos在Mongod的基礎(chǔ)上實(shí)現(xiàn)了分布式處理，提供了數(shù)據(jù)劃分、備份、分布式執(zhí)行等功能。目前，MongoDB以行式BSON記錄作為數(shù)據(jù)的存儲(chǔ)格式，對(duì)大規(guī)模數(shù)據(jù)分析的運(yùn)算可能引起大量額外的I/O操作。而Steed支持JSON的二進(jìn)制列式存儲(chǔ)，可以很好地支持大規(guī)模的數(shù)據(jù)分析運(yùn)算。因此，將Steed作為MongoDB的存儲(chǔ)引擎，就有可能使MongoDB對(duì)JSON數(shù)據(jù)進(jìn)行列式I/O操作，從而大大提升大數(shù)據(jù)分析的效率。此外，目前Steed的實(shí)現(xiàn)是一個(gè)單機(jī)的數(shù)據(jù)庫(kù)系統(tǒng)，而MongoDB在分布式處理方面有較強(qiáng)的能力，因此將Steed作為MongoDB的存儲(chǔ)引擎，就可以自然地利用MongoDB的分布式處理能力，形成一個(gè)能夠支持多機(jī)分布式存儲(chǔ)和運(yùn)算的樹(shù)狀結(jié)構(gòu)大數(shù)據(jù)系統(tǒng)。MongoDB已經(jīng)在實(shí)踐中得到了廣泛應(yīng)用，在最流行的數(shù)據(jù)庫(kù)引擎排名中名列第5位。若MongoDB+Steed仍然采用MongoDB的前端界面和編程語(yǔ)言，就有可能更容易地被廣大MongoDB用戶接受，因此筆者將MongoDB的后端WiredTiger存儲(chǔ)引擎替換為Steed，使用列式存儲(chǔ)讀取數(shù)據(jù)，并轉(zhuǎn)化為BSON，使用MongoDB現(xiàn)有的內(nèi)存處理。在具體實(shí)現(xiàn)中，需要把上層查詢運(yùn)算的相關(guān)信息發(fā)送到下層的Steed存儲(chǔ)引擎。只有這樣，Steed才可能得知有哪些屬性列參與了當(dāng)前的查詢運(yùn)算，從而可以采用列式的訪問(wèn)讀取這些列的相關(guān)信息，而不是訪問(wèn)全部的列，達(dá)到減少I(mǎi)/O開(kāi)銷(xiāo)、提升效率的目的。

（3）性能比較

圖3 Steed和現(xiàn)有樹(shù)狀結(jié)構(gòu)數(shù)據(jù)處理系統(tǒng)的性能對(duì)比

Steed和現(xiàn)有的樹(shù)狀結(jié)構(gòu)數(shù)據(jù)處理系統(tǒng)PostgresQL、MongoDB、Hive+Parquet的性能對(duì)比如圖3所示。Steed Row和Steed Column分別采用行式和列式數(shù)據(jù)存儲(chǔ)。實(shí)驗(yàn)是在單臺(tái)聯(lián)想ThinkCentre M8500t工作站上運(yùn)行的，工作站配有一個(gè)3.4 GHz 4核的Intel Core i7-4770處理器、16 GB內(nèi)存和一個(gè)7 200 r/min的SATA硬盤(pán)。在Twitter數(shù)據(jù)上運(yùn)行多種查詢操作，圖3中從左到右依次是選擇一個(gè)屬性（select）、使用1～3個(gè)條件過(guò)濾數(shù)據(jù)集（1filter、2filters、3filters）、分組統(tǒng)計(jì)（group）、在分組統(tǒng)計(jì)的結(jié)果上進(jìn)一步過(guò)濾（having）、排序（order）、連接（join）?？傮w而言，Steed Column性能在所有系統(tǒng)中最優(yōu)，比Hive+Parquet提高4.1～17.8倍，比MongoDB提高55.9～105.2倍，比PostgreSQL提高33.8～1 294倍。MongoDB+Steed采用了列式存儲(chǔ)，比采用行式存儲(chǔ)的原始MongoDB性能提升16～51倍。把BSON格式改變?yōu)镾teed的內(nèi)存結(jié)構(gòu)，節(jié)省了對(duì)字符串屬性名的比較，采用了更高效的查詢處理實(shí)現(xiàn)，Steed Column比MongoDB+Steed性能提升1.8～5.5倍。

7 結(jié)束語(yǔ)

傳統(tǒng)的關(guān)系數(shù)據(jù)模型難以滿足大數(shù)據(jù)應(yīng)用日益豐富的大數(shù)據(jù)表達(dá)和處理需求，因此實(shí)踐中涌現(xiàn)了多種非傳統(tǒng)的大數(shù)據(jù)類(lèi)型。其中，以JSON為代表的樹(shù)狀結(jié)構(gòu)大數(shù)據(jù)類(lèi)型是一種重要的大數(shù)據(jù)類(lèi)型。本文從數(shù)據(jù)模型、實(shí)用價(jià)值和理論意義等方面介紹了樹(shù)狀結(jié)構(gòu)大數(shù)據(jù)類(lèi)型，探討了樹(shù)狀結(jié)構(gòu)大數(shù)據(jù)類(lèi)型的高效處理，設(shè)計(jì)實(shí)現(xiàn)了一個(gè)樹(shù)狀結(jié)構(gòu)數(shù)據(jù)管理系統(tǒng)——Steed系統(tǒng)，支持通用的樹(shù)狀結(jié)構(gòu)數(shù)據(jù)存儲(chǔ)和類(lèi)似SQL的查詢處理。通過(guò)分析現(xiàn)實(shí)數(shù)據(jù)，提出一種頻繁子模式——簡(jiǎn)單路徑，簡(jiǎn)單路徑在實(shí)際數(shù)據(jù)中大量存在。針對(duì)簡(jiǎn)單路徑，Steed優(yōu)化了外存存儲(chǔ)、列組裝算法和內(nèi)存行式結(jié)構(gòu)。與現(xiàn)有系統(tǒng)PostgreSQL、MongoDB、Hive+Parquet相比，Steed對(duì)數(shù)據(jù)分析類(lèi)的操作普遍有10～1 000倍的性能提升。