樹狀結(jié)構(gòu)大數(shù)據(jù)類型的高效支持

陳世敏

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

1 引言

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

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

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

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

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

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

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

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

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

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

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

圖1 對應(yīng)于JSON記錄實例的語法樹

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

3 實用價值

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

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

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

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

（2）靈活的類型

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

（3）低廉的成本

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

4 理論意義

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

（2）MongoDB+Steed

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

（3）性能比較

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

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

7 結(jié)束語

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