基于二叉樹(shù)算法數(shù)據(jù)控制層數(shù)據(jù)庫(kù)模型構(gòu)建

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

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

中圖分類(lèi)號(hào)：TP301.6

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

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

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

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

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

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

數(shù)據(jù)窗口（Farm）是構(gòu)成NODE控制系統(tǒng)最為基本的單位。一般來(lái)說(shuō)，NODE控制系統(tǒng)可以由一個(gè)或幾個(gè)數(shù)據(jù)窗口構(gòu)成。這些數(shù)據(jù)窗口是互相獨(dú)立的，數(shù)據(jù)窗口之間能夠相互進(jìn)行通信。數(shù)據(jù)窗口（Farm）在一般情況下只是對(duì)其自身范圍內(nèi)的數(shù)據(jù)操作進(jìn)行負(fù)責(zé)。數(shù)據(jù)窗口往往是通過(guò)其自然屬性來(lái)進(jìn)行劃分的，例如可以根據(jù)國(guó)家和地區(qū)還有客戶(hù)的組織等劃分。數(shù)據(jù)窗口（Farm）包括了多個(gè)由調(diào)度節(jié)點(diǎn)構(gòu)成的節(jié)點(diǎn)池，調(diào)度節(jié)點(diǎn)負(fù)責(zé)節(jié)點(diǎn)池，同時(shí)還構(gòu)建數(shù)據(jù)數(shù)據(jù)庫(kù)模型。在對(duì)調(diào)度節(jié)點(diǎn)池進(jìn)行設(shè)計(jì)的時(shí)候充分考慮了負(fù)載均衡（Load Balance），一個(gè)數(shù)據(jù)窗口一般包括了一個(gè)調(diào)度節(jié)點(diǎn)還有多個(gè)數(shù)據(jù)節(jié)點(diǎn)池[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)品的實(shí)際需要出發(fā)而制定的，采用了傳統(tǒng)的面向?qū)ο笏枷?，將一個(gè)數(shù)據(jù)實(shí)體視為一個(gè)對(duì)象（object）。這個(gè)數(shù)據(jù)實(shí)體具備基本的結(jié)構(gòu)和屬性，可以視作整個(gè)系統(tǒng)中的所有對(duì)象的基類(lèi)，從而可以在它的基礎(chǔ)上派生出各種不同用途的對(duì)象。這個(gè)數(shù)據(jù)實(shí)體應(yīng)具有如下特點(diǎn)：

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

*每個(gè)Object都有一個(gè)26位的全局標(biāo)識(shí)（UID）。這個(gè)26位的全局標(biāo)識(shí)是這個(gè)Object整個(gè)生命周期中的全局唯一標(biāo)識(shí)符。

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

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

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

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

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

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

*對(duì)象數(shù)據(jù)（Object Data）。這部分?jǐn)?shù)據(jù)泛指所有的Object，包括平臺(tái)本身預(yù)先提供的和用戶(hù)定義的Object。

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

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

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

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

*首先應(yīng)該將對(duì)象、查詢(xún)還有其他數(shù)據(jù)歸類(lèi)到不同的數(shù)據(jù)表里面。

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

*查詢(xún)數(shù)據(jù)也根據(jù)對(duì)象類(lèi)型對(duì)其進(jìn)行垂直劃分，數(shù)據(jù)庫(kù)模型構(gòu)建到相應(yīng)的數(shù)據(jù)表中。

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

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

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

參考文獻(xiàn)：

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

[2]許翠蘋(píng).IDC：二叉樹(shù)算法將在中國(guó)走向主流[J].通訊世界，2011（06）.

[3]范慶彬，王為.二叉樹(shù)算法在電信運(yùn)營(yíng)商中的應(yīng)用[J].信息通信，2011（03）.

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

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

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