NoSQL Data Models Overview

A data model specifies how data is structured, how it is queried, and what consistency guarantees hold across operations. The relational model fixes all three: data is organized into tables with a declared schema, queried via a relationally-complete language (SQL), and protected by ACID transactions across arbitrary sets of rows. NoSQL systems deliberately unfix one or more of these to gain something else, usually horizontal scalability or throughput on a specific access pattern. The four canonical NoSQL data models are distinguished by what unit of data they treat as atomic and addressable. A key-value store treats an opaque blob as the unit, addressed by a single key, with no visibility into its internal structure. A document store treats a semi-structured, typically JSON-like document as the unit; the system can index and query into the document's internal fields even though different documents may have different fields. A column-family store (sometimes called a wide-column store) treats a row identified by a row key as a sparse, extensible collection of column families, each holding an arbitrary and independently-evolving set of columns, physically stored column-family by column-family rather than row by row. A graph database treats nodes and the edges connecting them as first-class stored objects with properties, optimizing traversal — following an edge from one node to another — as a constant-time pointer dereference rather than an indexed join. Every one of these models can be understood as a special case of the general relational model with a constraint relaxed: key-value drops query-ability of the value entirely; document drops schema rigidity while keeping partial query-ability; column-family drops row-uniform schema and reorganizes physical layout for column-oriented scans; graph drops the join-as-search-time-operation in favor of persisted adjacency. None of these models is "more powerful" than relational in an absolute sense — each is a different point on a Pareto frontier of consistency, schema flexibility, query power, and horizontal scalability, and the correct choice depends on the dominant access pattern of the application.

The mechanism of each NoSQL model is best understood through its core operations and its physical storage layout, since the storage layout is precisely what makes its dominant access pattern fast.

Key-value stores (e.g., Redis, DynamoDB's core, Riak) support essentially two operations: `PUT(key, value)` and `GET(key)`, plus sometimes `DELETE(key)`. Internally these are backed by a hash table (for pure in-memory speed) or a log-structured merge tree / B-tree (for durable, disk-backed stores). Partitioning is done by hashing the key, typically with consistent hashing so that adding or removing nodes only reshuffles a small fraction of keys. ``` function PUT(key, value): partition_id = hash(key) mod num_partitions // or consistent-hash ring lookup node = partition_table[partition_id] replicate_to(node.replicas, key, value) // e.g. write to W of N replicas return ACK when quorum_W replicas acknowledge function GET(key): partition_id = hash(key) mod num_partitions node = partition_table[partition_id] responses = read_from(node.replicas, key) // read from R of N replicas return reconcile(responses) // e.g. last-write-wins, vector clocks ``` The quorum condition `W + R > N` (from Dynamo-style systems) guarantees at least one replica in any read quorum overlaps any prior write quorum, which is the basis for tunable consistency discussed under Eventual Consistency and Consistency Models.

Document stores (e.g., MongoDB, Couchbase) extend the key-value idea by parsing the value as a structured document (commonly BSON/JSON) and building secondary indexes over fields inside it. ``` function INSERT(collection, document): doc_id = document._id or generate_id() validate_against(collection.optional_schema) // may be absent or partial store(collection, doc_id, document) for each indexed_field in collection.indexes: index_entry = extract(document, indexed_field) update_index(collection.indexes[indexed_field], index_entry -> doc_id) function QUERY(collection, predicate): if predicate.field has an index: candidate_ids = index_lookup(collection.indexes[predicate.field], predicate.value) else: candidate_ids = full_collection_scan(collection) // O(n) return [fetch(collection, id) for id in candidate_ids if matches(predicate, id)] ``` Because documents in the same collection may have different fields, there is no schema-conformance check at write time unless the application (or an optional schema validator) enforces one — this is schema-on-read rather than schema-on-write.

Column-family stores (e.g., Cassandra, HBase, Bigtable) organize storage so that all values for a given column family, across many rows, are physically clustered together on disk, sorted by row key within each column family's file (SSTable). This means a query touching only a few columns across millions of rows reads a tiny fraction of the data a row-oriented store would. ``` function GET_COLUMN(row_key, column_family, column): memtable_hit = lookup_memtable(row_key, column_family, column) if memtable_hit: return memtable_hit for sstable in sstables_for(column_family) in newest_to_oldest_order: if row_key in sstable.bloom_filter: // O(1) probabilistic skip value = sstable.lookup(row_key, column) if value found: return value return NOT_FOUND function PUT_COLUMN(row_key, column_family, column, value, timestamp): append_to_commit_log(row_key, column_family, column, value, timestamp) write_to_memtable(row_key, column_family, column, value, timestamp) if memtable.size > threshold: flush_memtable_to_new_sstable() // async compaction later merges SSTables ```

Graph databases (e.g., Neo4j, JanusGraph, Amazon Neptune) store nodes and edges directly, with each node holding pointers (physical or logical) to its adjacent edges — this is index-free adjacency. Traversal from a node to its neighbors is a direct dereference, independent of total graph size. ``` function TRAVERSE(start_node, relationship_type, max_hops): visited = {start_node} frontier = [start_node] for hop in 1..max_hops: next_frontier = [] for node in frontier: for edge in node.adjacency_list: // stored directly on the node if edge.type == relationship_type and edge.target not in visited: visited.add(edge.target) next_frontier.append(edge.target) frontier = next_frontier return visited ```

Key-value stores. `GET`/`PUT` cost is `O(1)` expected time for hash-table-backed stores, and `O(log n)` for tree-backed durable stores (LSM-tree or B-tree), where `n` is the number of keys in the relevant partition. Space is `O(total data)`, replicated `N` times for fault tolerance, so `O(N · data size)` overall. Correctness of the quorum protocol follows from the pigeonhole argument: if a write quorum has size `W` and a read quorum has size `R`, and there are `N` total replicas, then `W + R > N` guarantees the read and write quorums intersect in at least one replica, so any read quorum contains at least one replica holding the most recent acknowledged write — this is the invariant underlying read-your-writes and strong quorum consistency in Dynamo-style systems. If `W + R ≤ N`, quorums can be disjoint and reads may miss the latest write, which is exactly the relaxation that buys higher availability under The CAP Theorem.

Document stores. A query on an indexed field costs `O(log n + k)`, where `k` is the number of matching documents, via a B-tree or hash index on that field — identical asymptotically to a relational secondary index. A query on an unindexed field costs `O(n)`, a full collection scan, since there is no guarantee every document even contains that field. The absence of enforced schema means there is no static correctness guarantee that a given field exists or has a consistent type; correctness of application logic becomes the responsibility of the reading application, a genuine tradeoff versus relational schema-on-write validation.

Column-family stores. A point lookup with a bloom filter costs expected `O(1)` per SSTable check (the bloom filter gives a `false-positive rate ≈ (1 - e^{-kn/m})^k` for `m` bits, `n` inserted keys, `k` hash functions, tunable arbitrarily close to zero) plus `O(log s)` for the actual sorted lookup within a matching SSTable of size `s`. Writes are `O(1)` amortized: an append to a commit log and an insert into an in-memory memtable (itself a balanced tree, `O(log m)` for memtable size `m`), with the expensive merge (compaction) deferred and amortized over many writes — this is precisely the LSM-tree argument: batch small random writes into large sequential writes, trading read amplification (must check multiple SSTables) for write throughput. Total space overhead versus raw data is bounded by a compaction factor, typically `O(data size · log(data size / memtable size))` before compaction reclaims space.

Graph databases. Index-free adjacency gives traversal cost `O(1)` per hop (dereference an edge pointer) rather than `O(log n)` or worse for a join-based relational traversal that must look up matching foreign keys through an index at every hop. A breadth-first traversal to depth `d` from a node with average out-degree `b` costs `O(b^d)` in the worst case — the same combinatorial blow-up any graph search faces — but each individual step is asymptotically cheaper than the equivalent relational self-join, which costs `O(log n)` per hop for an indexed join or `O(n)` for an unindexed one. The correctness argument is structural: because adjacency is materialized as a stored pointer rather than recomputed by a join predicate at query time, traversal correctness reduces to graph reachability correctness, which is preserved as long as edge insertion/deletion keeps adjacency lists consistent — an invariant enforced at write time by the storage engine.

Honest tradeoffs. None of these speedups are free. Key-value stores sacrifice all query expressiveness over the value. Document stores sacrifice compile-time schema guarantees. Column-family stores sacrifice efficient multi-row transactions and ad hoc row-oriented queries (a `SELECT *` across a row is expensive since data for that row is scattered across column families). Graph databases sacrifice efficient bulk aggregate queries (e.g., "average order total across all users") since that pattern is better served by scanning a column-oriented structure than by traversing pointers node by node. Choosing a data model is choosing which of these costs your workload can tolerate.

Consider a social shopping app with users, their orders, and their follows relationships (who follows whom). We model the identical scenario across all four NoSQL types and the relational baseline, then trace one query: "find the total amount Ada has spent."

Relational baseline: ```sql SELECT SUM(total) FROM orders WHERE user_id = 1042; ``` Cost: `O(log n)` to find matching rows via an index on `user_id`, then `O(k)` to sum `k` matching rows. Requires a pre-declared schema and a foreign key `orders.user_id → users.id`.

Key-value model. We store a single blob per user containing a serialized list of order totals: `key = "orders:1042"`, `value = [59.00, 12.50]` (serialized). To answer the query: ``` value = GET("orders:1042") total = sum(deserialize(value)) ``` Cost: `O(1)` for the GET, `O(k)` to sum `k` items after deserializing — but the store itself has no idea what's inside that blob; if we wanted "total spending across all users above $50" we would need to scan every key, `O(n)`, since there is no secondary index into blob contents.

Document model. Each order is a document with an embedded or referenced user id, and MongoDB-style aggregation can index the `user_id` field: ```json { "_id": "o883", "user_id": 1042, "total": 59.00, "items": ["hat","gloves"] } { "_id": "o901", "user_id": 1042, "total": 12.50, "items": ["mug"] } ``` ``` db.orders.aggregate([ { match: { user_id: 1042 } }, { group: { _id: "user_id", spent: { sum: "$total" } } } ]) ``` With an index on `user_id`, cost is `O(log n + k)` — the same shape as the relational plan, because the document store built a real secondary index over a nested field.

Column-family model. Row key is the user id; one column family `orders` holds one column per order: | row key | orders:o883 | orders:o901 | |---|---|---| | u1042 | 59.00 | 12.50 | ``` row = GET_ROW("u1042", column_family="orders") total = sum(row.values()) ``` Cost: one bloom-filter-guided SSTable lookup per relevant SSTable, `O(1)` expected per SSTable, then `O(k)` to sum the `k` order columns actually stored for that row — this scales well even if the table has a billion rows, because a scan touching only the `orders` column family for one row key never reads the `profile` column family's data at all.

Graph model. `Ada` is a node; each order is either a property bundle on an edge `Ada -[:PLACED]-> Order` or a separate `Order` node. ``` ada = FIND_NODE(name="Ada") total = 0 for edge in ada.adjacency_list: if edge.type == "PLACED": total += edge.target.properties["total"] ``` Cost: `O(deg(ada))`, the out-degree of Ada's node — independent of total graph size, which is exactly the win index-free adjacency provides, though this model is a poor fit for a bulk aggregate like "average spend across all 10 million users," which would require visiting every node.

The NoSQL movement did not emerge from a single lab; it emerged from internet-scale engineering teams hitting the limits of relational systems under massive, geographically distributed load, and publishing the systems they built to cope.

Key-value stores underpin session storage, caching layers, and shopping carts at massive scale: Redis and Memcached serve as caching tiers in front of nearly every high-traffic web architecture, and DynamoDB powers core services at Amazon and countless AWS-hosted applications. Document stores like MongoDB and Couchbase are the default choice for content-management systems, mobile app backends, and any domain where the record shape evolves quickly during early product development. Column-family stores like Cassandra, HBase, and Bigtable back time-series data, sensor telemetry, and any workload with billions of rows and a narrow, predictable set of columns queried per row — Cassandra was built at Facebook originally for the inbox-search feature and now underpins large parts of Netflix's and Apple's infrastructure. Graph databases like Neo4j and Amazon Neptune power fraud-detection systems, recommendation engines, and social-network "who do you know" features, where the query is fundamentally about relationship depth rather than tabular aggregation. Understanding all four models is the necessary foundation for the deeper treatments of Column-Family and Column Stores and Graph Data Models, and for situating any individual system within the broader Big Data Systems Landscape.

Ask the tutor: How would you redesign the "Ada's order total" query if the access pattern shifted from single-user lookups to "top 100 spenders across all users"?