基于MapReduce范式構造樹與表

摘要:樹和表是兩中代表性的數據結構。文件系統和數據庫，是兩種基本的存儲系統。文件系統的結構可以抽象成樹，數據庫結構可以抽象成表。MapReduc范式是從已有的眾多數據處理流程中抽象出的具有共性的部分，其分而治之的思想核心適用于并行的分布式處理。該文通過兩實例，嘗試了用MapReduce范式來構造表和樹這兩種具有代表性的數據結構，并對其特點進行歸納作為切入點，以便將來進一步對MapReduce范式在更一般范圍的適用性做深入研究。

關鍵詞:樹;表;MapReduce;數據結構

中圖分類號:TP301文獻標識碼:A 文章編號:1009-3044(2010)01-6-01

Construct Tree and Table Based on MapReduce Paradigm

XU Chun-ling

(School of Computer Science Technology， Soochow University， Suzhou 215006， China)

Abstract: Tree and Table is typical data structure. File system and Data Base is primary storage system. The structure of File System can be abstracted to Tree and structure of Data Base can be abstracted to table. MapReduce paradigm is the generality which was abstracted from the data processing， it include the thought of ‘divide and rule’ which is useful to parallel processing. This paper try to construct the typical data structure tree and table base on MapReduce paradigm， and summary the feature as the breakthrough point， so that the applicability in general range of MapReduce paradigm can be deeply studied in future.

Key words: tree; table; MapReduce; data structure

MapReduce范式在 google論文《MapReduce Simplified Data Processing on Large Clusters》中被提及，這正是從已有的眾多數據處理流程中抽象出的具有共性的部分。MapReduce范式又在多大程度上適用于一般的數據處理，本文嘗試用MapReduce構造兩個常見數據結構表、樹的實例子。

1 表的構造

MapReduce作為范式被抽象出來以前已經蘊涵在于各種數結構的生成過程中。例如，一個二維表即可被看作A、B兩個集合之間的一次Map(A，B)，以此類推Map(C，Map(A，B))即可生成一個三維表，Map(D，Map(C，Map(A，B)))生成四維表，這里的map相當于join。一次Reduce相當于對一個維度進行一次order by或group by，前者可看作一個聚類后者是一個聚合，聚合是在聚類基礎上增加聚合算子。

2 樹的構造

兩點被一條線段連接，等同于一對元素的Map。一組相互獨立的線段，可以看作集合之間(或集合內)的一組映射。一次Reduce形成一個深度為1的樹(樹林)，而當map建立在兩個相互獨立沒有交集的集合上時，一次reduce就產生了一個深度為1的樹。

3 總結

以上樹與表的構造實例歸納為以下幾點:

1) 基于兩個無交集的集合;

2) 我們人為的設定，其中一個集合為鍵集合，另一個集合為值集合;

3) 兩個集合中的每個元素都屬于至少一組配對;

4) 鍵集合中元素的個數，小于值集合中元素的個數;

5) map產生的“鍵值對”個數等于值集合元素個數時，reduce無效。

參考文獻:

[1] DEAN J，GHEMAWAT S.MapReduce:Simplified data processing on large clusters[C].6th OSDI，2004:137-150.

[2] Ralf L.Google's MapReduce Programming Model-Revisited[C].SCP，2007.