摘 要：隨著信息技術(shù)的全面發(fā)展，二叉樹算法在各個領域的應用越來越廣泛，需要運用二叉樹算法技術(shù)對數(shù)據(jù)進行數(shù)據(jù)庫模型構(gòu)建，提升數(shù)據(jù)信息的存取能力，通過對二叉樹算法技術(shù)的應用研究，可以提升金融行業(yè)數(shù)據(jù)控制層能力。具體實施過程中采取開源框架無疑是一條捷徑。但是，借鑒和使用開源框架需要結(jié)合各自的實際需求，通過分析Dataline節(jié)點的特點。把數(shù)據(jù)控制模型作為Dataline節(jié)點的研究基礎，把數(shù)據(jù)控制模型的部分特點運用到實際項目中，建立數(shù)據(jù)控制模型完全支持的關(guān)系數(shù)據(jù)模型，提升數(shù)據(jù)信息挖掘能力。

關(guān)鍵詞：二叉樹算法；數(shù)據(jù)控制層；數(shù)據(jù)庫模型構(gòu)建

中圖分類號：TP301.6

Dataline節(jié)點提供的是一個比較簡單的數(shù)據(jù)庫HBase，該數(shù)據(jù)庫是以數(shù)據(jù)控制模型作為基礎的HBase[1]，其無論在設計思想方面還是選取的數(shù)據(jù)模型在很大程度上與Google開發(fā)的數(shù)據(jù)庫BigTable非常的類似。然而HBase對完全的關(guān)系數(shù)據(jù)模型并不支持，僅僅給用戶提供了比較簡單的數(shù)據(jù)模型，讓他們動態(tài)控制數(shù)據(jù)的分布和格式。HBase是稀疏能夠存在硬盤上，具有多維度和排序的映射表[2]。該表將行關(guān)鍵字和列關(guān)鍵字以及時間戳作為索引。任何一個值都是不解釋的一個字符數(shù)組，用戶需要對數(shù)據(jù)庫模型構(gòu)建的字串的類型與內(nèi)涵進行解釋。從這個角度來看，該模型的靈活性是非常強的，依靠數(shù)據(jù)表示的仔細選擇，用戶能夠有效的對數(shù)據(jù)局部化進行控制。當然任何事情都具有兩面性，該模型具有靈活性，但是同時也就不支持完全的關(guān)系數(shù)據(jù)模型，這就使得傳統(tǒng)的數(shù)據(jù)數(shù)據(jù)庫模型構(gòu)建格式和HBase不能有效的協(xié)調(diào)起來。Google的GFS具有自身的特殊性，其是專門為網(wǎng)頁搜索而構(gòu)建的，BigTable的簡單數(shù)據(jù)模型能夠把符串形式靈活數(shù)據(jù)庫模型構(gòu)建網(wǎng)頁的URL，時間戳等信息[3]。為了提高有效性，在設計數(shù)據(jù)控制模型的時候，充分考慮和吸取了GFS的思想，所以當前版本的數(shù)據(jù)控制模型能夠很好的去支持網(wǎng)頁搜索。然而數(shù)據(jù)控制模型使用的是傳統(tǒng)的關(guān)系數(shù)據(jù)模型，支持網(wǎng)頁搜索的這個優(yōu)點并沒有發(fā)揮太大的優(yōu)勢，其沒有提供傳統(tǒng)的關(guān)系數(shù)據(jù)庫的相關(guān)功能。

1 分布式數(shù)據(jù)（NODE 控制）的整體架構(gòu)設計

在對數(shù)據(jù)控制層應用需求進行分析，還有充分考慮到當前流行的解決方案存在不足的基礎之上，在這里專門設計了嶄新的一個架構(gòu)Distributed Data Farm（NODE控制）。NODE控制有一個非常大的優(yōu)勢，那就是與實際需要進行掛鉤，同時還參考和借鑒了MapReduce以及數(shù)據(jù)控制模型上面的一些優(yōu)勢還有設計思想。

1.1 NODE 控制的總體架構(gòu)

NODE 控制系統(tǒng)提供的是一個分布式和可伸縮的數(shù)據(jù)功能。但是NODE 控制和分布式數(shù)據(jù)庫有著非常大的不同，NODE 控制在系統(tǒng)底層使用的是關(guān)系數(shù)據(jù)庫保存數(shù)據(jù)。NODE控制系統(tǒng)有很多個數(shù)據(jù)窗口，同時也包括了很多個冗余服務器。在這里冗余服務器和數(shù)據(jù)窗口能夠保持數(shù)據(jù)同步，這樣就可以實現(xiàn)fail-over的功能。典型的數(shù)據(jù)窗口是由一個調(diào)度節(jié)點池還有多個數(shù)據(jù)節(jié)點池構(gòu)成的。

數(shù)據(jù)窗口（Farm）來源于網(wǎng)頁搜索領域，泛指一個搜索的范圍。NODE 控制中引入了這個概念，但是它的概念和網(wǎng)頁搜索中的數(shù)據(jù)窗口不盡相同[4]。

數(shù)據(jù)窗口（Farm）是構(gòu)成NODE控制系統(tǒng)最為基本的單位。一般來說，NODE控制系統(tǒng)可以由一個或幾個數(shù)據(jù)窗口構(gòu)成。這些數(shù)據(jù)窗口是互相獨立的，數(shù)據(jù)窗口之間能夠相互進行通信。數(shù)據(jù)窗口（Farm）在一般情況下只是對其自身范圍內(nèi)的數(shù)據(jù)操作進行負責。數(shù)據(jù)窗口往往是通過其自然屬性來進行劃分的，例如可以根據(jù)國家和地區(qū)還有客戶的組織等劃分。數(shù)據(jù)窗口（Farm）包括了多個由調(diào)度節(jié)點構(gòu)成的節(jié)點池，調(diào)度節(jié)點負責節(jié)點池，同時還構(gòu)建數(shù)據(jù)數(shù)據(jù)庫模型。在對調(diào)度節(jié)點池進行設計的時候充分考慮了負載均衡（Load Balance），一個數(shù)據(jù)窗口一般包括了一個調(diào)度節(jié)點還有多個數(shù)據(jù)節(jié)點池[5]。

1.2 NODE控制的數(shù)據(jù)結(jié)構(gòu)

在描述了NODE控制的總體架構(gòu)之后，我們有必要介紹一下NODE控制的數(shù)據(jù)結(jié)構(gòu)。這一數(shù)據(jù)結(jié)構(gòu)的定義是從某公司新產(chǎn)品的實際需要出發(fā)而制定的，采用了傳統(tǒng)的面向?qū)ο笏枷?，將一個數(shù)據(jù)實體視為一個對象（object）。這個數(shù)據(jù)實體具備基本的結(jié)構(gòu)和屬性，可以視作整個系統(tǒng)中的所有對象的基類，從而可以在它的基礎上派生出各種不同用途的對象。這個數(shù)據(jù)實體應具有如下特點：

*Object本身具有類似XML格式的樹形結(jié)構(gòu)。與XML不同的是，Object本身并沒有強制的序列順序要求。

*每個Object都有一個26位的全局標識（UID）。這個26位的全局標識是這個Object整個生命周期中的全局唯一標識符。

*Object是可分解的。出于安全和訪問目的的考慮，只允許大多數(shù)用戶使用Object的一個子結(jié)構(gòu)，而不是整個對象。

如前所述，某公司新產(chǎn)品所面對的數(shù)據(jù)具有海量，異構(gòu)的特點，具體說來，包括以下幾種對象：

*用戶對象。這類數(shù)據(jù)是最常見的也可能是數(shù)量最多的。如前所述，新產(chǎn)品定位是一個平臺（platform），這個平臺允許用戶定制應用，因此就必須允許用戶創(chuàng)建并保存對象。NODE控制要求用戶對象必須具有完整的XML格式，但是對用戶對象的復雜度和數(shù)量沒有限制。

*聊天條目。按照最初的設想，這些條目用于保存聊天主題之類的數(shù)據(jù)。具體實現(xiàn)有待將來完成。

*標簽和標記對象的引用計數(shù)。這部分可以歸于公用數(shù)據(jù)的一部分。

*反向索引（Inverted Index）。所有的Object都是有索引的，這樣使得所有的Object都是可查詢的。

*對象數(shù)據(jù)（Object Data）。這部分數(shù)據(jù)泛指所有的Object，包括平臺本身預先提供的和用戶定義的Object。

*查詢數(shù)據(jù)（Search Data）。這部分數(shù)據(jù)特指和查詢相關(guān)的數(shù)據(jù)，可分為兩部分：即反向索引（Inverted Index）和其他數(shù)據(jù)（Others）。反向索引主要用于優(yōu)化查詢的速度；其他數(shù)據(jù)主要用于查詢輔助，包括被標記為全文索引的對象，標簽等。

2 NODE 控制的數(shù)據(jù)劃分策略

由于當前存在非常多的異構(gòu)的用戶數(shù)據(jù)，因此對數(shù)據(jù)進行劃分是非常有必要的，這樣才能得到更好的查詢性能。

數(shù)據(jù)劃分策略包括了垂直數(shù)據(jù)劃分（Horizontal partition）還有水平數(shù)據(jù)劃分（Vertical partition）（Tim Chapman，2006）。NODE控制對這兩種劃分策略都應用到了。其中垂直數(shù)據(jù)劃分主要依據(jù)的是功能：

*首先應該將對象、查詢還有其他數(shù)據(jù)歸類到不同的數(shù)據(jù)表里面。

*在這里由于對象數(shù)據(jù)根據(jù)對象類型（object type）來進行訪問的，因此可以根據(jù)對象類型進一步進行垂直劃分，將類型不同的對象數(shù)據(jù)歸結(jié)到相對應的數(shù)據(jù)表里面。

*查詢數(shù)據(jù)也根據(jù)對象類型對其進行垂直劃分，數(shù)據(jù)庫模型構(gòu)建到相應的數(shù)據(jù)表中。

采用對象的全局標識（UID）的哈希值（hash）是水平劃分的，這樣就把對象數(shù)據(jù)劃分到不同的數(shù)據(jù)節(jié)點（Data Node），但是這需要考慮到數(shù)據(jù)遷移的問題。

3 結(jié)束語

二叉樹算法機需要和信息控制結(jié)合在一起，一個特定的數(shù)據(jù)節(jié)點只含有整個系統(tǒng)的一部分數(shù)據(jù)，但是它會有多個數(shù)據(jù)劃分。一般的，數(shù)據(jù)節(jié)點基本是不用去過多的考慮數(shù)據(jù)劃分問題的，調(diào)度節(jié)點不會把其他數(shù)據(jù)節(jié)點包含的數(shù)據(jù)劃分的數(shù)據(jù)操作指向這個數(shù)據(jù)節(jié)點。這就意味著數(shù)據(jù)節(jié)點對數(shù)據(jù)位置問題的問題是不關(guān)心的，關(guān)心數(shù)據(jù)位置的是調(diào)度節(jié)點。數(shù)據(jù)對象的全局標識符已經(jīng)決定其處于什么位置。對查詢來說，默認的情況就是在當前數(shù)據(jù)窗口（Farm）中進行查詢，同時調(diào)度節(jié)點必須要能夠完成對其他數(shù)據(jù)窗口進行的查詢，原理上與當前數(shù)據(jù)窗口進行的查詢基本是相同的。

參考文獻：

[1]劉文.二叉樹算法商業(yè)模式有待成熟[J].硅谷，2011（13）.

[2]許翠蘋.IDC：二叉樹算法將在中國走向主流[J].通訊世界，2011（06）.

[3]范慶彬，王為.二叉樹算法在電信運營商中的應用[J].信息通信，2011（03）.

[4]陳飛.二叉樹算法下的數(shù)字資源共建共享[J].河北科技圖苑，2011（02）.

[5]周紅偉，李琦.基于二叉樹算法的空間信息服務系統(tǒng)研究[J].計算機應用研究，2011（07）.

作者單位：四川大學計算機學院2011級計算機科學與技術(shù)系，成都 610207