NOSQL 數據建模技術

全文譯自牆外文章“NoSQL Data Modeling Techniques”，譯得不好，還請見諒。這篇文章看完之後，你可能會對NoSQL的數據結構會有些感覺。我的感覺是，關係型數據庫想把一致性，完整性，索引，CRUD都幹好，NoSQL只幹某一種事，但是犧牲了很多別的東西。總體來說，我覺得NoSQL更適合做Cache。下面是正文——

NoSQL 數據庫經常被用作很多非功能性的地方，如，擴展性，性能和一致性的地方。這些NoSQL的特性在理論和實踐中都正在被大眾廣泛地研究著，研究的熱點正是那些和性能分佈式相關的非功能性的東西，我們都知道 CAP 理論被很好地應用於了 NoSQL 系統中（陳皓注：CAP即，一致性(Consistency)， 可用性(Availability)， 分區容忍性(Partition tolerance)，在分佈式系統中，這三個要素最多隻能同時實現兩個，而NoSQL一般放棄的是一致性）。但在另一方面，NoSQL的數據建模技術卻因為缺乏像關係型數據庫那樣的基礎理論沒有被世人很好地研究。這篇文章從數據建模方面對NoSQL家族進行了比較，並討論幾個常見的數據建模技術。

要開始討論數據建模技術，我們不得不或多或少地先系統地看一下NoSQL數據模型的成長的趨勢，以此我們可以瞭解一些他們內在的聯繫。下圖是NoSQL家族的進化圖，我們可以看到這樣的進化：Key-Value時代，BigTable時代，Document時代，全文搜索時代，和Graph數據庫時代：（陳皓注：注意圖中SQL說的那句話，NoSQL再這樣發展下去就是SQL了，哈哈。）

NoSQL Data Models

首先，我們需要注意的是SQL和關係型數據模型已存在了很長的時間，這種面向用戶的自然性意味著：

• 最終用戶一般更感興趣於數據的聚合顯示，而不是分離的數據，這主要通過SQL來完成。
• 我們無法通過人手工控制數據的併發性，完整性，一致性，或是數據類型校驗這些東西的。這就是為什麼SQL需要在事務，二維表結構（schema）和外表聯合上做很多事。

另一方面，SQL可以讓軟件應用程序在很多情況下不需要關心數據庫的數據聚合，和數據完整性和有效性進行控制。而如果我們去除了數據一致性，完整性這些東西，會對性能和分佈存儲有著重的幫助。正因為如此，我們才有數據模型的進化：

• Key-Value 鍵值對存儲是非常簡單而強大的。下面的很多技術基本上都是基於這個技術開始發展的。但是，Key-Value有一個非常致命的問題，那就是如果我們需要查找一段範圍內的key。（陳皓注：學過hash-table數據結構的人都應該知道，hash-table是非序列容器，其並不像數組，鏈接，隊列這些有序容器，我們可以控制數據存儲的順序）。於是，有序鍵值 （Ordered Key-Value） 數據模型被設計出來解決這一限制，來從根本上提高數據集的問題。
• Ordered Key-Value 有序鍵值模型也非常強大，但是，其也沒有對Value提供某種數據模型。通常來說，Value的模型可以由應用負責解析和存取。這種很不方便，於是出現了 BigTable類型的數據庫，這個數據模型其實就是map裡有map，map裡再套map，一層一層套下去，也就是層層嵌套的key-value（value裡又是一個key-value），這種數據庫的Value主要通過“列族”（column families），列，和時間戳來控制版本。（陳皓注：關於時間戳來對數據的版本控制主要是解決數據存儲併發問題，也就是所謂的樂觀鎖，詳見《多版本併發控制(MVCC)在分佈式系統中的應用》）
• Document databases 文檔數據庫 改進了 BigTable 模型，並提供了兩個有意義的改善。第一個是允許Value中有主觀的模式（scheme），而不是map套map。第二個是索引。 Full Text Search Engines 全文搜索引擎可以被看作是文檔數據庫的一個變種，他們可以提供靈活的可變的數據模式（scheme）以及自動索引。他們之間的不同點主要是，文檔數據庫用字段名做索引，而全文搜索引擎用字段值做索引。
• Graph data models 圖式數據庫 可以被認為是這個進化過程中從 Ordered Key-Value 數據庫發展過來的一個分支。圖式數據庫允許構建議圖結構的數據模型。它和文檔數據庫有關係的原因是，它的很多實現允許value可以是一個map或是一個document。

NoSQL 數據模型摘要

本文剩下的章節將向你介紹數據建模的技術實現和相關模式。但是，在介紹這些技術之前，先來一段序言：

• NoSQL 數據模型設計一般從業務應用的具體數據查詢入手，而不是數據間的關係：
• 關係型的數據模型基本上是分析數據間的結構和關係。其設計理念是： ”What answers do I have?”
• NoSQL 數據模型基本上是從應用對數據的存取方式入手，如：我需要支持某種數據查詢。其設計理念是 ”What questions do I have?”
• NoSQL 數據模型設計比關係型數據庫需要對數據結構和算法的更深的瞭解。在這篇文章中我會和大家說那些盡人皆知的數據結構，這些數據結構並不只是被NoSQL使用，但是對於NoSQL的數據模型卻非常有幫助。
• 數據冗餘和反規格化是一等公民。
• 關係型數據庫對於處理層級數據和圖式數據非常的不方便。NoSQL用來解決圖式數據明顯是一個非常好的解決方案，幾乎所有的NoSQL數據庫可以很強地解決此類問題。這就是為什麼這篇文章專門拿出一章來說明層級數據模型。

下面是NoSQL的分類表，也是我用來寫這篇文章時做實踐的產品：

• Key-Value 存儲: Oracle Coherence, Redis, Kyoto Cabinet
• 類BigTable存儲: Apache HBase, Apache Cassandra
• 文檔數據庫: MongoDB, CouchDB
• 全文索引: Apache Lucene, Apache Solr
• 圖數據庫: neo4j, FlockDB

概念技術 Conceptual Techniques

這一節主要介紹NoSQL數據模型的基本原則。

(1) 反規格化 Denormalization

反規格化 Denormalization 可以被認為是把相同的數據拷貝到不同的文檔或是表中，這樣就可以簡化和優化查詢，或是正好適合用戶的某中特別的數據模型。這篇文章中所說的絕大多數技術都或多或少地導向了這一技術。

總體來說，反規格化需要權衡下面這些東西：

• 查詢數據量 /查詢IO VS 總數據量。使用反規格化，一方面可以把一條查詢語句所需要的所有數據組合起來放到一個地方存儲。這意味著，其它不同不同查詢所需要的相同的數據，需要放在別不同的地方。因此，這產生了很多冗餘的數據，從而導致了數據量的增大。
• 處理複雜度 VS 總數據量. 在符合範式的數據模式上進行表連接的查詢，很顯然會增加了查詢處理的複雜度，尤其對於分佈式系統來說更是。反規格化的數據模型允許我們以方便查詢的方式來存構造數據結構以簡化查詢複雜度。

適用性: Key-Value Store 鍵值對數據庫， Document Databases文檔數據庫， BigTable風格的數據庫。

(2) 聚合 Aggregates

所有類型的NoSQL數據庫都會提供靈活的Schema（數據結構，對數據格式的限制）：

• Key-Value Stores 和 Graph Databases 基本上來說不會Value的形式，所以Value可以是任意格式。這樣一來，這使得我們可以任意組合一個業務實體的keys。比如，我們有一個用戶帳號的業務實體，其可以被如下這些key組合起來： UserID_name, UserID_email, UserID_messages 等等。如果一個用戶沒有email或message，那麼相應也不會有這樣的記錄。
• BigTable 模型通過列集合來支持靈活的Schema，我們稱之為列族（column family）。BigTable還可以在同一記錄上出現不同的版本（通過時間戳）。
• Document databases 文檔數據庫是一種層級式的“去Schema”的存儲，雖然有些這樣的數據庫允許檢驗需要保存的數據是否滿足某種Schema。

靈活的Schema允許你可以用一種嵌套式的內部數據方式來存儲一組有關聯的業務實體（陳皓注：類似於JSON這樣的數據封裝格式）。這樣可以為我們帶來兩個好處。

• 最小化“一對多”關係——可以通過嵌套式的方式來存儲實體，這樣可以少一些表聯結。
• 可以讓內部技術上的數據存儲更接近於業務實體，特別是那種混合式的業務實體。可能存於一個文檔集或是一張表中。

下圖示意了這兩種好處。圖中描給了電子商務中的商品模型（陳皓注：我記得我在“挑戰無處不在”一文中說到過電商中產品分類數據庫設計的挑戰）

• 首先，所有的商品Product都會有一個ID，Price 和 Description。
• 然後，我們可以知道不同的類型的商品會有不同的屬性。比如，作者是書的屬性，長度是牛仔褲的屬性。其些屬性可能是“一對多”或是“多對多”的關係，如：唱片中的曲目。
• 接下來，我們知道，某些業務實體不可能使用固定的類型。如：牛仔褲的屬性並不是所有的牌子都有的，而且，有些名牌還會搞非常特別的屬性。

對於關係型數據庫來說，要設計這樣的數據模型並不簡單，而且設計出來的絕對離優雅很遠很遠。而我們NoSQL中靈活的Schema允許你使用一個聚合 Aggregate (product) 可以建出所有不同種類的商品和他們的不同的屬性：

Entity Aggregation

上圖中我們可以比較關係型數據庫和NoSQL的差別。但是我們可以看到在數據更新上，非規格化的數據存儲在性能和一致性上會有很大的影響，這就是我們需要重點注意和不得不犧牲的地方。

適用性: Key-Value Store 鍵值對數據庫， Document Databases文檔數據庫， BigTable風格的數據庫。

(3) 應用層聯結 Application Side Joins

表聯結基本上不被NoSQL支持。正如我們前面所說的，NoSQL是“面向問題”而不是“面向答案”的，不支持表聯結就是“面向問題”的後果。表的聯結是在設計時被構造出來的，而不是在執行時建造出來的。所以，表聯結在運行時是有很大開銷的（陳皓注：搞過SQL表聯結的都知道笛卡爾積是什麼東西，大可以在參看以前酷殼的“圖解數據庫表Joins”），但是在使用了 Denormalization 和 Aggregates 技術後，我們基本不用進行表聯結，如：你們使用嵌套式的數據實體。當然，如果你需要聯結數據，你需要在應用層完成這個事。下面是幾個主要的Use Case：

• 多對多的數據實體關係——經常需要被連接或聯結。
• 聚合 Aggregates 並不適用於數據字段經常被改變的情況。對此，我們需要把那些經常被改變的字段分到另外的表中，而在查詢時我們需要聯結數據。例如，我們有個Message系統可以有一個User實體，其包括了一個內嵌的Message實體。但是，如果用戶不斷在附加 message，那麼，最好把message拆分到另一個獨立的實體，但在查詢時聯結這User和Message這兩個實體。如下圖：

適用性: Key-Value Store 鍵值對數據庫， Document Databases文檔數據庫， BigTable風格的數據庫， Graph Databases 圖數據庫。

通用建模技術 General Modeling Techniques

在本書中，我們將討論NoSQL中各種不同的通用的數據建模技術。

(4) 原子聚合 Atomic Aggregates

很多NoSQL的數據庫（並不是所有）在事務處理上都是短板。在某些情況下，他們可以通過分佈式鎖技術或是應用層管理的MVCC技術來實現其事務性（陳皓注：可參看本站的“多版本併發控制(MVCC)在分佈式系統中的應用”）但是，通常來說只能使用聚合Aggregates技術來保證一些ACID原則。

這就是為什麼我們的關係型數據庫需要有強大的事務處理機制——因為關係型數據庫的數據是被規格化存放在了不同的地方。所以，Aggregates聚合允許我們把一個業務實體存成一個文檔、存成一行，存成一個key-value，這樣就可以原子式的更新了：

Atomic Aggregates

當然，原子聚合 Atomic Aggregates 這種數據模型並不能實現完全意義上的事務處理，但是如果支持原子性，鎖，或 test-and-set 指令，那麼， Atomic Aggregates 是可以適用的。

適用性: Key-Value Store 鍵值對數據庫， Document Databases文檔數據庫， BigTable風格的數據庫。

(5) 可枚舉鍵 Enumerable Keys

也許，對於無順序的Key-Value最大的好處是業務實體可以被容易地hash以分區在多個服務器上。而排序了的key會把事情搞複雜，但是有些時候，一個應用能從排序key中獲得很多好處，就算是數據庫本身不提供這個功能。讓我們來思考下email消息的數據模型：

1. 一些NoSQL的數據庫提供原子計數器以允許生一些連續的ID。在這種情況下，我們可以使用 userID_messageID 來做為一個組合key。如果我們知道最新的message ID，就可以知道前一個message，也可能知道再前面和後面的Message。
2. Messages可以被打包。比如，每天的郵件包。這樣，我們就可以對郵件按指定的時間段來遍歷。

適用性: Key-Value Store 鍵值對數據庫。

(6) 降維 Dimensionality Reduction

Dimensionality Reduction 降維是一種技術可以允許把一個多維的數據映射成一個Key-Value或是其它非多給的數據模型。

傳統的地理位置信息系統使用一些如“四分樹QuadTree” 或 “R-Tree” 來做地理位置索引。這些數據結構的內容需要被在適當的位置更新，並且，如果數據量很大的話，操作成本會很高。另一個方法是我們可以遍歷一個二維的數據結構並把其扁平化成一個列表。一個眾所周知的例子是Geohash（地理哈希）。一個Geohash使用“之字形”的路線掃描一個2維的空間，而且遍歷中的移動可以被簡單地用0和1來表示其方向，然後在移動的過程中產生0/1串。下圖展示了這一算法：（陳皓注：先把地圖分成四份，經度為第一位，緯度為第二位，於是左邊的經度是0，右邊的是1，緯度也一樣，上面是為1，下面的為0，這樣，經緯度就可以組合成01，11，00，10這四個值，其標識了四塊區域，我們可以如此不斷的遞歸地對每個區域進行四分，然後可以得到一串1和0組成的字串，然後使用0-9，b-z 去掉（去掉a, i, l, o）這32個字母進行base32編碼得到一個8個長度的編碼，這就是Geohash的算法）

Geohash Index

Geohash的最強大的功能是使用簡單的位操作就可以知道兩個區域間的距離，就像圖中所示（陳皓：proximity框著的那兩個，這個很像IP地址了）。Geohash把一個二維的座標生生地變成了一個一維的數據模型，這就是降維技術。BigTable的降維技術參看到文章後面的 [6.1]。更多的關於Geohash和其它技術可以參看 [6.2] 和 [6.3]。

適用性: Key-Value Store 鍵值對數據庫， Document Databases文檔數據庫， BigTable風格的數據庫。

(7) 索引表 Index Table

Index Table 索引表是一個非常直白的技術，其可以你在不支持索引的數據庫中得到索引的好處。BigTable是這類最重要的數據庫。這需要我們維護一個有相應存取模式的特別表。例如，我們有一個主表存著用戶帳號，其可以被UserID存取。某查詢需要查出某個城市裡所有的用戶，於是我們可以加入一張表，這張表用城市做主鍵，所有和這個城市相關的UserID是其Value，如下所示：

Geohash Index

Geohash的最強大的功能是使用簡單的位操作就可以知道兩個區域間的距離，就像圖中所示（陳皓：proximity框著的那兩個，這個很像IP地址了）。Geohash把一個二維的座標生生地變成了一個一維的數據模型，這就是降維技術。BigTable的降維技術參看到文章後面的 [6.1]。更多的關於Geohash和其它技術可以參看 [6.2] 和 [6.3]。

適用性: Key-Value Store 鍵值對數據庫， Document Databases文檔數據庫， BigTable風格的數據庫。

(7) 索引表 Index Table

Index Table 索引表是一個非常直白的技術，其可以你在不支持索引的數據庫中得到索引的好處。BigTable是這類最重要的數據庫。這需要我們維護一個有相應存取模式的特別表。例如，我們有一個主表存著用戶帳號，其可以被UserID存取。某查詢需要查出某個城市裡所有的用戶，於是我們可以加入一張表，這張表用城市做主鍵，所有和這個城市相關的UserID是其Value，如下所示：

Index Table Example

可見，城市索引表的需要和對主表用戶表保持一致性，因此，主表的每一個更新可能需要對索引表進行更新，不然就是一個批處理更新。無論哪個方式，這都會損傷一些性能，因為需要保持一致性。

Index Table 索引表可以被認為是關係型數據庫中的視圖的等價物。

適用性: BigTable 數據庫。

(8) 鍵組合索引 Composite Key Index

Composite key 鍵組合是一個很常用的技術，對此，當我們的數據庫支持鍵排序時能得到極大的好處。Composite key組合鍵的拼接成為第二排序字段可以讓你構建出一種多維索引，這很像我們之前說過的 Dimensionality Reduction 降維技術。例如，我們需要存取用戶統計。如果我們需要根據不同的地區來統計用戶的分佈情況，我們可以把Key設計成這樣的格式 (State:City:UserID)，這樣一來，就使得我們可以通過State到City來按組遍歷用戶，特別是我們的NoSQL數據庫支持在key上按區查詢（如：BigTable類的系統）：

1

2

SELECT Values WHERE state="CA:*"

SELECT Values WHERE city="CA:San Francisco*"

Composite Key Index

適用性: BigTable 數據庫。

(9) 鍵組合聚合 Aggregation with Composite Keys

Composite keys 鍵組合技術並不僅僅可以用來做索引，同樣可以用來區分不用的類型的數據以支持數據分組。考慮一個例子，我們有一個海量的日誌數組，這個日誌記錄了互聯網上的用戶的訪問來源。我們需要計算從某一網站過來的獨立訪客的數量，在關係型數據庫中，我們可能需要下面這樣的SQL查詢語句：

1

SELECT count(distinct(user_id)) FROM clicks GROUP BY site

我們可以在NoSQL中建立如下的數據模型：

Counting Unique Users using Composite Keys

這樣，我們就可以把數據按UserID來排序，我們就可以很容易把同一個用戶的數據（一個用戶並不會產生太多的event）進行處理，去掉那些重複的站點（使用hash table或是別的什麼）。另一個可選的技術是，我們可以對每一個用戶建立一個數據實體，然後把其站點來源追加到這個數據實體中，當然，這樣一來，數據的更新在性能相比之下會有一定損失。

適用性: Ordered Key-Value Store 排序鍵值對數據庫， BigTable風格的數據庫。

(10) 反轉搜索 Inverted Search – 直接聚合 Direct Aggregation

這個技術更多的是數據處理技術，而不是數據建模技術。儘管如此，這個技術還是會影響數據模型。這個技術最主要的想法是使用一個索引來找到滿足某條件的數據，但是把數據聚合起需要使用全文搜索。還是讓我們來說一個示例。還是用上面那個例子，我們有很多的日誌，其中包括互聯網用戶和他們的訪問來源。讓我們假定每條記錄都有一個UserID，還有用戶的種類 (Men, Women, Bloggers, 等)，以及用戶所在的城市，和訪問過的站點。我們要乾的事是，為每個用戶種類找到滿足某些條件（訪問源，所在城市，等）的的獨立用戶。

很明顯，我們需要搜索那些滿足條件的用戶，如果我們使用反轉搜索，這會讓我們把這事幹得很容易，如： {Category -> [user IDs]} 或 {Site -> [user IDs]}。使用這樣的索引， 我們可以取兩個或多個UserID要的交集或並集（這個事很容易幹，而且可以乾得很快，如果這些UserID是排好序的）。但是，我們要按用戶種類來生成報表會變得有點麻煩，因為我們用語句可能會像下面這樣

1

SELECT count(distinct(user_id)) ... GROUP BY category

但這樣的SQL很沒有效率，因為category數據太多了。為了應對這個問題，我們可以建立一個直接索引 {UserID -> [Categories]} 然後我們用它來生成報表：

Counting Unique Users using Inverse and Direct Indexes

最後，我們需要明白，對每個UserID的隨機查詢是很沒有效率的。我們可以通過批查詢處理來解決這個問題。這意味著，對於一些用戶集，我們可以進行預處理（不同的查詢條件）。

適用性: Key-Value Store 鍵值對數據庫， Document Databases文檔數據庫， BigTable風格的數據庫。

層級式模型 Hierarchy Modeling Techniques

(11) 樹形聚合Tree Aggregation

樹形或是任意的圖（需反規格化）可以被直接打成一條記錄或文檔存放。

• 當樹形結構被一次性取出時這會非常有效率（如：我們需要展示一個blog的樹形評論）
• 搜索和任何存取這個實體都會存在問題。
• 對於大多數NoSQL的實現來說，更新數據都是很不經濟的（相比起獨立結點來說）

Tree Aggregation

適用性: Key-Value 鍵值對數據庫, Document Databases 文檔數據庫

(12) 鄰接列表 Adjacency Lists

Adjacency Lists 鄰接列表是一種圖 – 每一個結點都是一個獨立的記錄，其包含了 所有的父結點或子結點。這樣，我們就可以通過給定的父或子結點來進行搜索。當然，我們需要通過hop查詢遍歷圖。這個技術在廣度和深度查詢，以及得到某個結點的子樹上沒有效率。

適用性: Key-Value 鍵值對數據庫, Document Databases 文檔數據庫

(13) Materialized Paths

Materialized Paths 可以幫助避免遞歸遍歷（如：樹形結構）。這個技術也可以被認為是反規格化的一種變種。其想法是為每個結點加上父結點或子結點的標識屬性，這樣就可以不需要遍歷就知道所有的後裔結點和祖先結點了：

Materialized Paths for eShop Category Hierarchy

這個技術對於全文搜索引擎來說非常有幫助，因為其可以允許把一個層級結構轉成一個文檔。上面的示圖中我們可以看到所有的商品或Men’s Shoes下的子分類可以被一條很短的查詢語句處理——只需要給定個分類名。

Materialized Paths 可以存儲一個ID的集合，或是一堆ID拼出的字符串。後者允許你通過一個正則表達式來搜索一個特定的分支路徑。下圖展示了這個技術（分支的路徑包括了結點本身）：

Query Materialized Paths using RegExp

適用性: Key-Value 鍵值對數據庫, Document Databases 文檔數據, Search Engines 搜索引擎

(14) 嵌套集 Nested Sets

Nested sets 嵌套集是樹形結構的標準技術。它被廣泛地用在了關係性數據庫中，它完全地適用於 Key-Value 鍵值對數據庫 和 Document Databases 文檔數據庫。這個技術的想法是把葉子結點存儲成一個數組，並通過使用索引的開始和結束來映射每一個非葉子結點到一個葉子結點集，就如下圖所示一樣：

Modeling of eCommerce Catalog using Nested Sets

這樣的數據結構對於immutable data不變的數據 有非常不錯的效率，因為其點內存空間小，並且可以很快地找出所有的葉子結點而不需要樹的遍歷。儘管如此，在插入和更新上需要很高的性能成本，因為新的葉子結點需要大規模地更新索引。

適用性: Key-Value Stores 鍵值數據庫, Document Databases 文檔數據庫

(15) 嵌套文檔扁平化：有限的字段名 Nested Documents Flattening: Numbered Field Names

搜索引擎基本上來說和扁平文檔一同工作，如：每一個文檔是一個扁平的字段和值的例表。這種數據模型的用來把業務實體映射到一個文本文檔上，如果你的業務實體有很複雜的內部結構，這可能會變得很有挑戰。一個典型的挑戰是把一個有層級的文檔映映射出來。例如，文檔中嵌套另一個文檔。讓我們看看下面的示例：

Nested Documents Problem

上面的每一個業務實體代碼一種簡歷。其包括了人名和一個技能列表。我把這個層級文檔映射成一個文本文檔，一種方法是創建 Skill 和 Level 字段。這個模型可以通過技術或是等級來搜索一個人，而上圖標註的那樣的組合查詢則會失敗。（陳皓注：因為分不清Excellent是否是Math還是Poetry上的）

在引用中的 [4.6] 給出了一種解決方案。其為每個字段都標上數字 Skill_i 和 Level_i，這樣就可以分開搜索每一個對（下圖中使用了OR來遍歷查找所有可能的字段）:

Nested Document Modeling using Numbered Field Names

這樣的方式根本沒有擴展性，對於一些複雜的問題來說只會讓代碼複雜度和維護工作變大。

適用性: Search Engines 全文搜索

(16)嵌套文檔扁平化：鄰近查詢 Nested Documents Flattening: Proximity Queries

在附錄 [4.6]中給出了這個技術用來解決扁平層次文檔。它用鄰近的查詢來限制可被查詢的單詞的範圍。下圖中，所有的技能和等級被放在一個字段中，叫 SkillAndLevel，查詢中出現的 “Excellent” 和 “Poetry” 必需一個緊跟另一個：

Nested Document Modeling using Proximity Queries

附錄 [4.3] 中講述了這個技術被用在Solr中的一個成功案例。

適用性: Search Engines 全文搜索

(17) 圖結構批處理 Batch Graph Processing

Graph databases 圖數據庫，如 neo4j 是一個出眾的圖數據庫，尤其是使用一個結點來探索鄰居結點，或是探索兩個或少量結點前的關係。但是處理大量的圖數據是很沒有效率的，因為圖數據庫的性能和擴展性並不是其目的。分佈式的圖數據處理可以被 MapReduce 和 Message Passing pattern 來處理。如： 在我前一篇的文章中的那個示例。這個方法可以讓 Key-Value stores, Document databases, 和 BigTable-style databases 適合於處理大圖。

Applicability: Key-Value Stores, Document Databases, BigTable-style Databases

參考

Finally, I provide a list of useful links related to NoSQL data modeling:

1. Key-Value Stores:
2. http://www.devshed.com/c/a/MySQL/Database-Design-Using-KeyValue-Tables/
3. http://antirez.com/post/Sorting-in-key-value-data-model.html
4. http://stackoverflow.com/questions/3554169/difference-between-document-based-and-key-value-based-databases
5. http://dbmsmusings.blogspot.com/2010/03/distinguishing-two-major-types-of_29.html
6. BigTable-style Databases:
7. http://www.slideshare.net/ebenhewitt/cassandra-datamodel-4985524
8. http://www.slideshare.net/mattdennis/cassandra-data-modeling
9. http://nosql.mypopescu.com/post/17419074362/cassandra-data-modeling-examples-with-matthew-f-dennis
10. http://s-expressions.com/2009/03/08/hbase-on-designing-schemas-for-column-oriented-data-stores/
11. http://jimbojw.com/wiki/index.php?title=Understanding_Hbase_and_BigTable
12. Document Databases:
13. http://www.slideshare.net/mongodb/mongodb-schema-design-richard-kreuters-mongo-berlin-preso
14. http://www.michaelhamrah.com/blog/2011/08/data-modeling-at-scale-mongodb-mongoid-callbacks-and-denormalizing-data-for-efficiency/
15. http://seancribbs.com/tech/2009/09/28/modeling-a-tree-in-a-document-database/
16. http://www.mongodb.org/display/DOCS/Schema+Design
17. http://www.mongodb.org/display/DOCS/Trees+in+MongoDB
18. http://blog.fiesta.cc/post/11319522700/walkthrough-mongodb-data-modeling
19. Full Text Search Engines:
20. http://www.searchworkings.org/blog/-/blogs/query-time-joining-in-lucene
21. http://www.lucidimagination.com/devzone/technical-articles/solr-and-rdbms-basics-designing-your-application-best-both
22. http://blog.griddynamics.com/2011/07/solr-experience-search-parent-child.html
23. http://www.lucidimagination.com/blog/2009/07/18/the-spanquery/
24. http://blog.mgm-tp.com/2011/03/non-standard-ways-of-using-lucene/
25. http://www.slideshare.net/MarkHarwood/proposal-for-nested-document-support-in-lucene
26. http://mysolr.com/tips/denormalized-data-structure/
27. http://sujitpal.blogspot.com/2010/10/denormalizing-maps-with-lucene-payloads.html
28. http://java.dzone.com/articles/hibernate-search-mapping-entit
29. Graph Databases:
30. http://docs.neo4j.org/chunked/stable/tutorial-comparing-models.html
31. http://blog.neo4j.org/2010/03/modeling-categories-in-graph-database.html
32. http://skillsmatter.com/podcast/nosql/graph-modelling
33. http://www.umiacs.umd.edu/~jimmylin/publications/Lin_Schatz_MLG2010.pdf
34. Demensionality Reduction:
35. http://www.slideshare.net/mmalone/scaling-gis-data-in-nonrelational-data-stores
36. http://blog.notdot.net/2009/11/Damn-Cool-Algorithms-Spatial-indexing-with-Quadtrees-and-Hilbert-Curves
37. http://www.trisis.co.uk/blog/?p=1287