《大數(shù)據(jù)架構(gòu)師必讀的NoSQL建模技術(shù)》要點：
本文介紹了大數(shù)據(jù)架構(gòu)師必讀的NoSQL建模技術(shù)，希望對您有用。如果有疑問，可以聯(lián)系我們。

1.前言

為了適應大數(shù)據(jù)應用場景的要求,Hadoop以及NoSQL等與傳統(tǒng)企業(yè)平臺完全不同的新興架構(gòu)迅速地崛起.而下層技術(shù)基礎(chǔ)的革命必將影響上層建筑：數(shù)據(jù)模型和算法.簡單地將傳統(tǒng)基于第四范式結(jié)構(gòu)化關(guān)系型數(shù)據(jù)庫的模型拷貝到新的引擎上,無異于削足適履,不僅增加了大數(shù)據(jù)應用開發(fā)的難度和復雜度,又無法發(fā)釋放新框架的潛能.

該如何構(gòu)建基于NoSQL的數(shù)據(jù)模型?現(xiàn)在能供參考的公開知識積累要么是空虛簡單的一句“去規(guī)范化“或粗暴的寬表化(將query和應用需要拜訪的所有字段“排排坐“,放在一個有很多列的結(jié)構(gòu)化表中),要么是針對具體工具或具體場景的實現(xiàn)細節(jié),(如《HBase權(quán)威指南》中對于如何設(shè)計HBase主鍵的探討).沒有一個像編程的設(shè)計模式一樣的,在模型架構(gòu)層面可以遵循的方法論.

在比較不同的NoSQL數(shù)據(jù)庫時,通常使用功能以外其他各種指標,如可擴展性、性能和一致性.由于這些指標通常是使用NoSQL的初衷,所以無論從理論的角度還是實踐的角度被深入地研究了,而像CAP定理這樣的分布式系統(tǒng)基礎(chǔ)結(jié)論也同樣適用于NoSQL系統(tǒng).另一方面,在NoSQL的數(shù)據(jù)模型領(lǐng)域,卻還沒有很好地研究過,也缺乏關(guān)系數(shù)據(jù)庫中那種系統(tǒng)性的理論.

我在這篇文章中從數(shù)據(jù)建模的角度對NoSQL家族系統(tǒng)做了比較簡單的比較,并簡要介紹幾種常見建模技術(shù).

2.NoSQL數(shù)據(jù)模型視圖

要探索數(shù)據(jù)建模技術(shù),必須先從系統(tǒng)性的NoSQL數(shù)據(jù)模型視圖著手,這多多少少能幫助我們揭示其發(fā)展趨勢以及相互之間的關(guān)系.下圖描繪了主要NoSQL家族系統(tǒng)的虛擬“進化”過程,即鍵值存儲,BigTable類型的數(shù)據(jù)庫,文檔數(shù)據(jù)庫,全文搜索引擎,數(shù)據(jù)庫和圖形數(shù)據(jù)庫：

首先,我們應該注意到,一般意義上講,SQL和關(guān)系型模型都是在很久以前就被設(shè)計出來,目的是為最終用戶交互之用.這種面向用戶的性質(zhì)有極深的影響：

最終用戶往往對匯總報表信息感興趣而不是單獨的數(shù)據(jù)項,因而SQL這方面做了大量的工作.

不能指望作為自然人的用戶能顯式地控制并發(fā)性、完整性、一致性或者數(shù)據(jù)類型有效性.這就是為什么SQL竭力關(guān)注于事務保證、schema和參照完整性.

另一方面,軟件應用程序往往對在數(shù)據(jù)庫內(nèi)部做聚合沒有太大的興趣,而且至少在許多情況下,程序能夠自己控制完整性和有效性.除此之外,剔除這些功能對于性能和可擴展性存儲的影響極其重要.

新數(shù)據(jù)模型的演變開始了：

鍵-值存儲是一個非常簡單,但非常強大的模型.下面所描述的許多技術(shù)都完全適用于這個模型.

鍵值模型最致命的缺點之一就是不適合按范圍處理主鍵的場景.有序的鍵-值模型突破了這一限制,并顯著提高了聚合能力.

有序的鍵-值模型非常強大,但它不提供任何針對值(value)的建模框架.在一般情況下,值的建模可以由應用程序完成,但BigTable風格的數(shù)據(jù)庫想得更加周到,它可以將值依照映射的映射的映射(map-of-maps-of-maps)進行建模,說得明確點,分別是列簇(column family)、列(column)和時間戳化的版本.

文檔數(shù)據(jù)庫對BigTable模式提出兩個明顯的改善.第一,值可以被聲明為任意復雜的schema,而不僅僅是一個映射的映射(map-of-maps).第二,至少有一些產(chǎn)品實現(xiàn)了被數(shù)據(jù)庫管理的索引.就這個意義上來講,全文搜索引擎也可以同樣被認為提供了靈活的schema和自動化的索引.他們之間主要區(qū)別在于,文檔數(shù)據(jù)庫是根據(jù)字段名對索引進行編組,而搜索引擎是使用字段值對索引編組.值得注意的是像Oracle Coherence這樣的鍵-值存儲系統(tǒng)增加了索引和內(nèi)嵌入口處理器的功能,正逐步向文件數(shù)據(jù)庫演進.

最后,圖形數(shù)據(jù)模型可以被視為有序的鍵-值模型朝另外一個方向的進化.圖形數(shù)據(jù)庫允許對業(yè)務實體進行非常透明的建模(這個東西取決于那個東西),而分層建模技術(shù)在這方面用的是另外的數(shù)據(jù)模型,但也可與之媲美.圖形數(shù)據(jù)庫和文件數(shù)據(jù)庫息息相關(guān),因為許多實現(xiàn)允許建模的值是映射或者文檔.

3.NoSQL數(shù)據(jù)建模的一般注意事項

與關(guān)系型建模不同,NoSQL數(shù)據(jù)建模往往是從特定查詢的應用開始：

關(guān)系型建模是典型地被手上可用數(shù)據(jù)的結(jié)構(gòu)所驅(qū)動.設(shè)計主要圍繞著的是“我有什么樣的答案?”

NoSQL數(shù)據(jù)建模通常由特定應用的拜訪模式所驅(qū)動,比如需要支持的查詢類型.設(shè)計主要圍繞著的是“我有什么問題?”

NoSQL數(shù)據(jù)建模往往比關(guān)系數(shù)據(jù)庫建模需要更加深入地了解數(shù)據(jù)結(jié)構(gòu)和算法.在這篇文章中,我介紹了幾個著名的數(shù)據(jù)結(jié)構(gòu),他們雖然非NoSQL所特有,但對于實際的NoSQL建模非常有用.

數(shù)據(jù)復制和去規(guī)范化是一等公民.

關(guān)系數(shù)據(jù)庫在對分層或圖形數(shù)據(jù)進行建模和處理時不是很方便.圖形數(shù)據(jù)庫顯然是這個領(lǐng)域的完美辦理方案,但實際上大多數(shù)的NoSQL也都非常善于辦理這樣的問題.這就是為什么這篇文章為分層數(shù)據(jù)建模單獨寫了一個章節(jié).

雖然數(shù)據(jù)建模技術(shù)基本上和具體實現(xiàn)無關(guān),但我還是列出了在寫這篇文章時我能想到的產(chǎn)品：

鍵值存儲：Oracle Coherence,Redis,Kyoto Cabinet

BigTable風格的數(shù)據(jù)庫： Apache HBase,Apache Cassandra

文檔數(shù)據(jù)庫： MongoDB,CouchDB

全文搜索引擎： Apache Lucene,Apache Solr

圖形數(shù)據(jù)庫：Neo4j,FlockDB

4.概念技術(shù)

本節(jié)專門介紹NoSQL數(shù)據(jù)建模的基本原則.

1、 去規(guī)范化(Denormalization)

可以將去規(guī)范化定義為把相同的數(shù)據(jù)復制到多個文檔或數(shù)據(jù)表中,這樣可以簡化/優(yōu)化查詢處理,或者讓用戶數(shù)據(jù)能匹配一個特定的數(shù)據(jù)模型.在本文的大多數(shù)技術(shù)用到了這樣或那樣的去規(guī)范化.

一般來說,去規(guī)范化用于以下的折衷：

查詢的數(shù)據(jù)量或每次查詢IO**與總數(shù)據(jù)量的折衷.去規(guī)范化可以將一個查詢所需的所有數(shù)據(jù)組合起來存放到同一個地方.這通常意味著對相同數(shù)據(jù)的不同的查詢會拜訪不同的數(shù)據(jù)組合.因此,數(shù)據(jù)需要被復制多份,也就意味著增加了總數(shù)據(jù)量.

處理復雜性與總數(shù)據(jù)量的折衷.建模時的規(guī)范化和相應查詢的連接(join)明顯增加了查詢處理器的復雜度,在分布式系統(tǒng)中尤為明顯.去規(guī)范化允許將數(shù)據(jù)依照查詢友好的方式存儲,從而簡化查詢的處理.

適用性：鍵值存儲,文檔數(shù)據(jù)庫, BigTable風格的數(shù)據(jù)庫

2、 聚合(Aggregates)

所有主流NoSQL都提供了這樣或那樣的松散schema(soft schema)支持：

鍵值存儲和圖形數(shù)據(jù)庫通常不對值進行約束,所以值可能是任意格式.另外,也可以通過使用組合鍵將一個業(yè)務實體表示為多條記錄.例如,可以將一個用戶帳戶建模為UserID_name,UserID_email,UserID_messages等組合鍵表示的一個實體集合.如果用戶沒有電子郵件或消息,然后相應的實體不會被記錄.

BigTable模式也支持松散schema,因為一個列簇是可變的列集合,一個單元格又能存儲不定數(shù)目的數(shù)據(jù)版本.

文檔數(shù)據(jù)庫天生就沒schema,雖然某些文檔數(shù)據(jù)庫允許在數(shù)據(jù)輸入時使用用戶定義的schema進行驗證.

松散schema允許使用復雜的內(nèi)部結(jié)構(gòu)(嵌套實體)構(gòu)造實體的類,也允許改變特定實體的結(jié)構(gòu).這個更能帶來了兩個重要的便利：

通過嵌套的實體,最小化了一對多的關(guān)系,也因此減少了連接(join).

異構(gòu)業(yè)務實體的模型可以使用一個文檔集合或者一個數(shù)據(jù)表.松散schema掩藏了這種建模和業(yè)務實體之間“技術(shù)”上的差異.

我們用下面的圖來說明這些便利.該圖描繪了對電子商務領(lǐng)域中一個產(chǎn)品實體進行的建模.首先我們可以認為所有的產(chǎn)品都有一個ID、價格(Price)和描述(Description).進一步來看,我們發(fā)現(xiàn)不同類型的產(chǎn)品有不同的屬性,如圖書包含作者信息,而牛仔褲有長度屬性.這些屬性中間的某些屬性天生就有一對多或這多對多的特性,比如音樂唱片中的曲目.

更進一步來看,可能有些實體不可能使用固定的類型進行建模.例如,不同品牌的牛仔褲的屬性是不固定的,而每個制造商出產(chǎn)的牛仔褲的屬性也是不一致的.在規(guī)范化的關(guān)系型數(shù)據(jù)模型中雖然這些問題都可以解決,但辦法很猥瑣.松散schema軟架構(gòu)允許只使用一個聚合(Aggregation)(產(chǎn)品)就能對所有類型的產(chǎn)品及其屬性進行建模：

內(nèi)嵌的去規(guī)范化會在性能和一致性上對更新操作造成很大的影響,所以要特別注意更新過程.

適用性：鍵值存儲,文檔數(shù)據(jù)庫, BigTable的風格數(shù)據(jù)庫

3、 應用端連接(Application Side Joins)

很少有NoSQL辦理方案支持連接.NoSQL“問題導向”性質(zhì)的后果就是,通常在設(shè)計時處理join,而關(guān)系型模型是在執(zhí)行查詢時處理join.查詢時處理join幾乎肯定會帶來性能上的損失,但在許多情況下,可使用去規(guī)范化和聚合,即嵌入嵌套實體來避免join.當然,join在許多情況下是不可避免的,而且應該由應用程序處理.主要的用例：

多對多關(guān)系往往是通過鏈接(link)建模的,這需要join.

聚合操作往往不適合內(nèi)部實體會被頻繁修改的場景.通常更好的方法是將發(fā)生的事情作為一條新的記錄保留,并在查詢的時候?qū)⑺杏涗涀鰆oin,而不是去更改值.例如,對于一個信息系統(tǒng)而言,可以用嵌套包含了Message實體的User實體來建模.但是,如果會經(jīng)常地添加消息,更好的方法可能是把Message提取出來作為獨立實體,并在查詢時再將其與User進行連接：

適用性：鍵值存儲,文檔數(shù)據(jù)庫, BigTable風格數(shù)據(jù)庫,圖形數(shù)據(jù)庫

5.一般建模技術(shù)

在本節(jié)中,我們將討論適用于各種NoSQL實現(xiàn)的一般建模技術(shù).

1、 原子聚合(Atomic Aggregates)

許多NoSQL辦理方案提供了有限的事務支持,雖然有些NoSQL不支持.在某些情況下,人們還可以使用分布式鎖或應用程序管理的MVCC機制實現(xiàn)事務行為,但常見的是使用聚合技術(shù)來對數(shù)據(jù)建模,以保證一些ACID特性.

強大的事務處理機制對于關(guān)系型數(shù)據(jù)庫而言是不可或缺的,其中原因之一就是規(guī)范化的數(shù)據(jù)通常需要在多個地方進行更新.另一方面,聚合允許一個單個業(yè)務實體存儲為一個文件,行或鍵值對,從而可以對其進行原子性的更新：

當然,做為一種數(shù)據(jù)建模技術(shù),原子聚合并不是一個完善的事務型辦理方案,但如果存儲能提供原子性、鎖或者TAS(test-and-set,測試并設(shè)置)指令上的一些擔保,那原子聚合就是可行的.

(譯者注：即將需要事務性操作的業(yè)務數(shù)據(jù)聚合放在一起,存儲在一個NoQSQL提供或者應用能提供原子性操作的數(shù)據(jù)結(jié)構(gòu)中.使用HBase時,將某個用戶某個業(yè)務的所有數(shù)據(jù),如上圖,用一行存儲就是這種模式的應用.)

適用性：鍵值存儲,文檔數(shù)據(jù)庫, BigTable風格數(shù)據(jù)庫

2、 可枚舉主鍵(Enumerable Keys)

也許無序鍵-值數(shù)據(jù)模型最大的好處就是可以通過將主鍵哈希的方法把實體數(shù)據(jù)分別存儲在多個服務器上.排序使事情變得更加復雜,但是即使存儲不提供這樣的功能,有時應用程序也能利用到有序主鍵的優(yōu)勢.讓我們將對電子郵件建模作為一個例子：

某些NoSQL存儲提供原子計數(shù)器,能生成一個順序化的ID.在這種情況下,可以使用userID_messageID作為一個復合鍵來存儲消息.如果最新的消息ID是已知的,那就可以遍歷以前的消息.另外,對于任何一個給定的消息ID,也可以向前或向后進行遍歷.

也可以將消息分桶(bucket),例如,每天的數(shù)據(jù)放到一個桶里.這樣就允許從任何指定日期或當前日期開始,向前或向后遍歷一個郵箱.

適用性：鍵值存儲

(譯者注：能利用主鍵的一些自然或業(yè)務維度的特征,將隨機讀寫轉(zhuǎn)換為順序讀寫能提高遍歷性能,同時能方便應用邏輯編寫.但需要注意對分布式部署時并發(fā)寫的影響以及對于業(yè)務的過度耦合.對于無序主鍵和有序主鍵的討論可以參見《HBase權(quán)威指南》中Schema設(shè)計章節(jié).)

3、 降維(Dimensionality Reduction)

降維這種技術(shù)允許將一個多維數(shù)據(jù)模型映射到一個鍵-值模型或其他非多維模型.

傳統(tǒng)的地理信息系統(tǒng)使用四叉樹(Quadtree)或R樹(R-tree)的某種變形來做索引.這些結(jié)構(gòu)需要就地完成更新操作,因此在數(shù)據(jù)量很大時,維護開銷相當?shù)拇?另一種辦法是對這個二維結(jié)構(gòu)進行遍歷,并將其扁平化為一個普通的條目列表.使用這種技術(shù)的一個眾所周知的例子是Geohash. Geohash使用類似Z形狀的路線來掃描整個二維空間,每次移動根據(jù)行進方向被編碼為0或1.交錯位的經(jīng)度和緯度上的變更移動以及移動.編碼過程在下圖中進行了說明,其中黑色和紅色位分別代表經(jīng)度和緯度：

如圖所示,Geohash的一個重要特性是能夠通過這種逐位編碼的近似程度來估計區(qū)域之間的距離.Geohash編碼允許使用簡單普通的數(shù)據(jù)模型來存儲地理信息,比如用有序鍵值保存空間上的聯(lián)系.[6.1]講述了BigTable中的降維技術(shù).更多有關(guān)Geohash及其相關(guān)技術(shù)的信息可以在[6.2]和[6.3]中找到.

適用性：鍵值存儲,文檔數(shù)據(jù)庫, BigTable風格的數(shù)據(jù)庫

(譯者注：通過交織編碼方式來能將原本需要多維度標示的數(shù)據(jù),如cube,存儲到一維的鍵值存儲系統(tǒng)中,這是一種非常重要的建模模式：提供了不同縮放等級下在多維空間中鄰接的數(shù)據(jù)仍然順序存儲,遍歷高效;同時不同主鍵從前向后的相似度和空間距離的遠近相一致,能通過鍵值的簡單順序比較判斷其位置“相似度”.

它的應用遠遠不只地理信息的表示,有多個維度屬性不同粒度的數(shù)據(jù)表示都能用到這個技術(shù),比如線下銷售交易數(shù)據(jù)通常都有時間和分支結(jié)構(gòu)信息,用戶查詢銷售數(shù)據(jù)時通常先查詢一個大的區(qū)域,而且使用的時間段跨度也比較大,需要查詢更具體的信息時同時縮小地區(qū)和時間來逐步定位細節(jié),這時分支機構(gòu)和時間就好比是經(jīng)度維度的兩個軸,通過交織時間和分支結(jié)構(gòu)編碼的方式建立主鍵,能很好的滿足這種場景.而單純的使用時間或分支機構(gòu)做主鍵或索引卻都不能適應上述場景.)

4、 索引表(Index Table)

索引表是一個非常簡單的技術(shù),它在內(nèi)部不支持索引的存儲上提供索引的支持.這類存儲中最重要的一類就是BigTable風格的數(shù)據(jù)庫.索引表的想法是依照訪問模式所需要的鍵來創(chuàng)建和維護一個特殊的表.例如,有一個主表,存儲了可以通過用戶ID直接訪問的用戶帳戶.查詢指定城市的所有用戶可以通過一個額外的用城市做主鍵的表來支持：

索引表可以在每一個主表記錄更新時更新或者使用批模式更新.無論哪種方式,它會導致額外的性能損失,并帶來數(shù)據(jù)一致性上的問題.

可以認為索引表是一種對關(guān)系數(shù)據(jù)庫實例化視圖的模擬.

適用性： BigTable風格的數(shù)據(jù)庫

5、 組合主鍵索引(Composite Key Index)

復合主鍵是一個非常通用的技術(shù),但尤其在主鍵有序存儲時極其有用.復合主鍵結(jié)合二次排序就能建立起一種多維索引,這和前面所述的降維技術(shù)在原理上是類似的.例如,假設(shè)我們有一組記錄,每個記錄是一個用戶統(tǒng)計數(shù)據(jù).如果我們要按用戶來自的地區(qū)來聚合這些統(tǒng)計資料,我們可以使用這樣的主鍵格式(State:City:UserId).如果主鍵的存儲支持通過部分匹配來選取范圍(如BigTable風格的數(shù)據(jù)庫),那就可以在特定的州(State)或者城市(City)的記錄上做遍歷：

適用性： BigTable風格的數(shù)據(jù)庫

(譯者注：在使用HBase這類BigTable風格的數(shù)據(jù)庫時,如果主鍵只使用一個字段/域的信息簡直是暴殄天物.使用多字段組合主鍵不僅能辦理主鍵值不能重復的問題,還能提高對于數(shù)據(jù)子集二次查找時的性能.)

6、 組合主鍵的聚合

復合主鍵不僅可用于作索引,還可以為不同類型分組.讓我們來看一個例子.有一個巨大的日志數(shù)組,記錄了互聯(lián)網(wǎng)用戶和他們拜訪不同的網(wǎng)站(點擊流)的信息.我們的目標是對于每個唯一用戶計算出每個站點的點擊數(shù)量.這類似于下面的SQL查詢：

我們可以使用將用戶名當前綴的組合主鍵來對這種情況進行建模：

我們的想法是將一個用戶的所有記錄放置在一起,這樣就可能將其全部加載到內(nèi)存中(一個用戶不會產(chǎn)生太多的事件),并使用哈希表或其他辦法消除掉重復的網(wǎng)站.另一種技術(shù)是將用戶做為主鍵,每次事件到達時將網(wǎng)站添加到這條數(shù)據(jù)的后部.然而,在大多數(shù)實現(xiàn)中,修改數(shù)據(jù)一般比插入數(shù)據(jù)的效率低.

適用性：有序鍵值存儲,BigTable風格的數(shù)據(jù)庫

7、 倒排搜索-直接聚合

這種技術(shù)更像是數(shù)據(jù)處理模式,而不是數(shù)據(jù)建模.然而,數(shù)據(jù)模型也受這種模式使用的影響.這種技術(shù)的主要思想是使用索引來找到滿足條件的數(shù)據(jù),但聚合操作還是使用原來的方式或者全表掃描.讓我們來考慮一個例子.有一堆的日志數(shù)據(jù)記錄了互聯(lián)網(wǎng)用戶和他們拜訪不同的網(wǎng)站(點擊流,click stream)的信息.假設(shè)每條記錄都包括用戶ID、用戶所屬類別(男性、女性、博主(Blogger)等)、用戶來自的城市以及拜訪的網(wǎng)址.我們的目標是找出滿足條件(網(wǎng)址、城市等)的觀眾,并將這堆觀眾(如符合標準的用戶集合)中出現(xiàn)的不同用戶按類別歸類.

很明顯,滿足條件的用戶可以通過像{類別->[用戶ID]}或{網(wǎng)站->[用戶ID]}這樣的倒排索引表非常高效地查找到.使用這樣的倒排索引,可以得到所要的用戶ID的交集或者并集(如果用戶ID被存儲為排有序的列表或位圖,這就可以非常高效地實現(xiàn)),從而獲得目標用戶.但如果目標用戶是使用類似這樣的聚集查詢描述的：

那如果類別的數(shù)量很大,就不能用倒排索引做有效的處理.要辦理這個問題,可以用{用戶名->[分類集合]}的形式創(chuàng)建直接索引(Direct Index),然后遍歷它來建立最終報表.此架構(gòu)示意如下圖：

最后需要提示的是,我們需要知道如果隨機地拜訪目標用戶中每一個用戶ID所對應記錄,這樣做的效率可能很低.可以通過利用批量查詢處理解決這個問題.這意味著,一些數(shù)量的用戶集可以被預先計算(針對不同的報表條件),然后可以通過對直接索引表或倒排索引表進行一次全表掃描從而計算出這批目標用戶的所有報告.

適用性：鍵值存儲,BigTable風格的數(shù)據(jù)庫,文檔數(shù)據(jù)庫

分層建模技術(shù)(Hierarchy Modeling Techniques)

(譯者注：如果需要通過屬性或者類別來快速查找對應的實體,這樣的索引比不可少.現(xiàn)在很火的用大數(shù)據(jù)分析用戶畫像不就需要像{用戶標簽->用戶群}這樣的結(jié)構(gòu)么.)

8、 樹聚合(Tree Aggregation)

可以將一條單獨的記錄或者文件的模型建成樹,甚至是任意的圖(通過去規(guī)范化).

在樹會被一次性拜訪的場景中(例如,博客的整個評論樹會被讀取,并顯示在一篇文章的頁面中),這個技術(shù)很高效.

搜索和拜訪任意條目可能有問題.

在大多數(shù)NoSQL的實現(xiàn)中,更新操作的效率低下(同相互獨立的節(jié)點相比).

適用性：鍵值存儲,文檔數(shù)據(jù)庫

(譯者注：這是文檔型NoSQL的天下,對于無需跨樹join的場景,不僅讀寫效率高,而且能很好的支持局部性的事務應用.)

9、 鄰接列表(Adjacency Lists)

鄰接列表是一個簡單的圖型建模辦法——每個節(jié)點作為一個單獨記錄建模,其中有包含直接祖先的數(shù)組或包含后代的數(shù)組.它允許通過其父母或子女的標識符來搜索一個節(jié)點,當然也可以通過查詢一次前進一步的方式來遍歷一個圖.無論對于深度優(yōu)先或廣度優(yōu)先遍歷而言,要在整個子樹中找到一個給定的節(jié)點,這種辦法的效率通常不高.

適用性：鍵值存儲,文檔數(shù)據(jù)庫

10、 物化路徑

物化路徑是一種有助于避免在樹型結(jié)構(gòu)上做遞歸遍歷的技術(shù).也可以認為這是一種去規(guī)范化的技術(shù).其設(shè)計思想是用一個節(jié)點所有的父節(jié)點或者子女節(jié)點來標識該節(jié)點,這樣就有可以不用遍歷而得到一個節(jié)點的所有祖先節(jié)點或者衍生節(jié)點：

因為這個技術(shù)可以將層次結(jié)構(gòu)轉(zhuǎn)換成扁平化的文檔,所以它對于全文搜索引擎特別地有用.從上圖中可以看出,在男鞋(Men’s Shoes)類別下所有的產(chǎn)品或者子類別可以簡單的通過查詢一個類別名稱而得到.這個查詢很短.

物化路徑的存儲方式可以是一個ID的集合,或者一個是包含級聯(lián)ID的字符串.后一種方式允許使用正則表達式,來查找那些指定部分的路徑符合某種條件的節(jié)點.此種辦法如在下圖(路徑也包括了節(jié)點自身)所示：

適用性：鍵值存儲,文檔數(shù)據(jù)庫,搜索引擎

11、 嵌套集合(Nested Sets)

在對類似樹型結(jié)構(gòu)進行建模時,嵌套集合是個標準的做法.它在關(guān)系數(shù)據(jù)庫中廣泛被使用,然而它也完全適用于鍵值存儲和文檔數(shù)據(jù)庫.其設(shè)計思想是在用數(shù)組來存儲樹的葉子節(jié)點(譯者：每個葉子節(jié)點對應數(shù)組中的一個位置下標),并將每個非葉結(jié)點映射為一個葉子節(jié)點的范圍,這個范圍就是開始葉子節(jié)點和結(jié)束葉子節(jié)點在數(shù)組中的位置下標.如下圖所示：

這個結(jié)構(gòu)對于不變數(shù)據(jù)來講非常有效,因為它占用的內(nèi)存小,并且可以在不遍歷樹的情況下得到一個給定節(jié)點的所有葉子節(jié)點.然而,因為增加一個葉子節(jié)點會帶來位置下標的大量更新,所以插入和更新的操作代價是相當?shù)母?

適用性：鍵值存儲,文檔數(shù)據(jù)庫

(譯者注：適用于字典表、按日期排序的歷史日志數(shù)據(jù)表等.)

12、 扁平化嵌套文件：字段名稱編號

搜索引擎通常工作在扁平化的文檔之上,即每個文檔由兩個扁平列表組成,這兩個列表分別記錄了字段的名稱和它對應的值.數(shù)據(jù)建模的目標是將業(yè)務實體映射為簡單無結(jié)構(gòu)的文檔,但如果實體內(nèi)部的結(jié)構(gòu)很復雜,這就難辦了.一個典型的困難就是層次結(jié)構(gòu)模型,比如要將內(nèi)部嵌套了文檔的文檔映射為簡單無結(jié)構(gòu)的文檔.讓我們來考慮下面的例子：

每一個業(yè)務實體是一份某種形式的簡歷,其中包含了這個人的名字,和枚舉了他或她所具有的技能以及相應技能水平的列表.為這樣的實體建模的一個很顯然的方式就是是建立的簡單無結(jié)構(gòu)文檔,里面包含Skill和Level字段的列表.這種模式允許通過技能或水平來搜索某個人,但將這兩個字段聯(lián)合起來搜索卻容易導致虛假匹配,正如上圖所述.(譯者：簡單的AND操作不能感知技能以及其水平的對應關(guān)系.)

在[4.6]中提出了一種解決這個問題的辦法.這項技術(shù)的主要思想是將每一項技能以及相應的水平聯(lián)合起來組成一個配對(pair),并使用下標標識成為Skill_i和Level_i.在搜索時需要同時查詢所有這些對值(查詢中OR條件語句的個數(shù)是和一個人所能具有的技能的最大值相同)：

這種辦法實際上沒有可擴展性,因為隨著嵌套結(jié)構(gòu)的數(shù)目的增長會迅速增加查詢的復雜度.

適用性：搜索引擎

(譯者注：如果你對于使用索引來加速查詢無計可施,尤其對用戶將來如何查詢數(shù)據(jù)一無所知,無法在設(shè)計模型時進行優(yōu)化時,這就是最后的稻草：使用全文搜索工具.它至少能在可接受的時間內(nèi)能查出點東西來^o^.)

13、 扁平化嵌套文件：近似查詢

在[4.6]中還描述了另一種可以辦理嵌套文件問題的技術(shù).它的想法是使用近似的查詢,將文檔中單詞之間的距離限制在可以接受的距離范圍以內(nèi).在下面的圖中,所有的技能和水平都被索引到了一個叫SkillAndLevel的域.使用“Excellent”和“Poetry”進行查詢表示的話,就會查找到這兩個單詞鄰接的條目：

[4.3]講述了在Solr之上使用這種技術(shù)的一個成功案例.

適用性：搜索引擎

(譯者注：同上,但查詢召回率高,會出現(xiàn)假匹配,有臟數(shù)據(jù).)

14、 批量圖處理

在瀏覽一個指定節(jié)點的相鄰節(jié)點或瀏覽兩個或幾個節(jié)點之間的關(guān)系時,像Neo4j這樣的圖形數(shù)據(jù)庫的性能出奇的好.然而,通用圖形數(shù)據(jù)庫對大圖做全局性處理不是很高效,因為擴展性不好.分布式圖形處理可以使用MapReduce或者消息傳遞(Message Passing)模式來實現(xiàn).我以前的一篇文章就介紹了一種這樣的模式.這種辦法使用了鍵值存儲、文檔數(shù)據(jù)庫和BigTable風格的數(shù)據(jù)庫,能處理大型的圖形.

適用性：鍵值存儲,文檔數(shù)據(jù)庫,BigTable風格的數(shù)據(jù)庫

作者介紹：陳飚,Cloudera售前技術(shù)經(jīng)理、行業(yè)領(lǐng)域顧問、資深方案架構(gòu)師,原Intel Hadoop發(fā)行版核心開發(fā)人員.2006年加入Intel編譯器部門從事服務器中間件軟件開發(fā),擅長服務器軟件調(diào)試與優(yōu)化,曾帶領(lǐng)團隊開發(fā)出世界上性能領(lǐng)先的 XSLT 語言處理器.2010 年后開始Hadoop 產(chǎn)品開發(fā)及方案顧問,先后負責Hadoop 產(chǎn)品化、HBase 性能調(diào)優(yōu),以及行業(yè)辦理方案顧問,已在交通、通信等行業(yè)成功實施并支持多個上百節(jié)點Hadoop 集群.

歡迎參與《大數(shù)據(jù)架構(gòu)師必讀的NoSQL建模技術(shù)》討論，分享您的想法，維易PHP學院為您提供專業(yè)教程。

轉(zhuǎn)載請注明本頁網(wǎng)址：
http://www.snjht.com/jiaocheng/9334.html