NoSQL — document (MongoDB), key-value (Redis), column (Cassandra), graph (Neo4j): Foundations

Before you can read the parent note, you need to own every word and symbol it throws at you. This page builds each one from nothing — plain words first, then the picture, then why the topic can't live without it. Read top to bottom; each idea leans on the one above it.

This is the foundations page for NoSQL — four data models.

0. What is a "database" at all?

Picture a giant filing cabinet. The data model is the shape of the drawers — are they row-shaped, key-shaped, or a web of strings connecting cards? NoSQL is the claim that one cabinet shape does not fit every job.

Figure — NoSQL — document (MongoDB), key-value (Redis), column (Cassandra), graph (Neo4j)

The parent note names four cabinet shapes: document, key-value, wide-column, graph. Everything below is the vocabulary needed to understand those four.

1. The arrow " $\to$ " — our very first symbol

Two arrows show up all over this topic, so we earn them before anything uses them.

Whenever you see $\to$ on this page or the parent note, translate it in your head to "leads straight to".

2. Row, column, table (the SQL baseline)

You cannot understand "NoSQL" without the "SQL" it reacts against. See SQL Relational Databases.

Why the topic needs this: the parent note's phrase "force every row into a rigid table" only lands once you can see the grid and feel why nested or irregular data fights against it.

3. Key and value

This exact idea is the whole Redis model, and _id in MongoDB is a key too.

4. Hash map — how a key finds its value fast

This is the single most reused idea in the topic. See Hashing and Hash Maps.

Here comes our first piece of maths notation — earn it now:

Why the topic needs this: the parent claims Redis is " $O (1)$ " and an un-indexed Mongo scan is " $O (n)$ ". Those symbols are the whole reason one is a cache and the other is not.

5. JSON and BSON — the shape of a document

{
  "name": "Asha",
  "emails": ["asha@x.com"],
  "address": { "city": "Pune", "pin": 411001 }
}

BSON is just JSON stored in a compact binary form (faster for the machine, same idea). MongoDB stores BSON. This "one parcel = one entity" picture is exactly why documents avoid joins (§8).

6. Nodes, edges, and a graph

Needed for Neo4j. See Graph Traversal Algorithms (BFS/DFS).

Why the topic needs this: "friends-of-friends" is just two hops. In SQL that means joining a table to itself repeatedly, and the cost explodes. The graph picture is what makes traversal cheap.

7. Distributed system: nodes, replicas, partitions

The parent's CAP/BASE section lives entirely in this world. Prereqs: Sharding and Replication.

This doorway-slam is the entire drama of the CAP theorem — hold this picture into §9.

8. Join, index, and denormalisation

Why the topic needs these three: they are the exact levers each NoSQL family pulls — documents denormalise, Cassandra bans joins, everyone relies on indexes.

9. CAP: the letters C, A, P and why you drop one

You will meet these in the CAP box of the parent note. Meet them clean first, with a picture.

10. BASE and eventual consistency

If a system chooses A over C during a partition, its replicas disagree for a while. That "for a while" needs a name — this is the edge case CAP leaves you in.

11. Quorums: the letters $N$ , $W$ , $R$ and the overlap rule

The parent's quorum formula controls how much consistency you buy back.

Now derive the overlap rule step by step. Follow the figure alongside.

Formula Deriving

$W + R > N$ Step 1 — the goal (WHAT). We want a read to be guaranteed to touch at least one replica that saw the newest write. Step 2 — the sets (WHAT IT LOOKS LIKE). Out of $N$ replicas, the write landed on a set of $W$ of them; the read pulls from a set of $R$ of them. Picture two coloured groups drawn on the same row of $N$ boxes (see figure). Step 3 — count the worst case (WHY). To avoid any overlap, the $W$ writers and $R$ readers would have to sit in completely separate boxes. That needs at least $W + R$ distinct boxes. But there are only $N$ boxes. Step 4 — the pigeonhole. If $W + R > N$ , they cannot fit without sharing — at least $W + R - N \geq 1$ box must belong to both sets. That shared box holds the newest write, so the read sees it. Conclusion. A read is guaranteed to see the latest write exactly when $W + R > N$

How these foundations feed the topic

Node IDs below are abbreviations; the label inside each box spells out the full idea.

Equipment checklist

Cover the right side and answer aloud. If any stumps you, reread that section before the parent note.

What does the arrow

\to

mean?

"maps to / points to" — follow the left side and you land straight on the right side.

What does

O (1)

mean in plain words?

The work is constant — it does not grow as the data grows (instant lookup).

What does

O (n)

mean?

The work grows in step with the number of items

n

— you may touch all of them (a full scan).

What does

O (lo g n)

mean and where does it appear?

Work grows very slowly — doubling the data adds just one step; it's the cost of a B-tree index lookup.

What is a hash map and why is it usually fast?

A key-to-value store where a hash function computes the slot directly, so lookup is

O (1)

on average — no searching.

When does a hash-map lookup degrade, and to what?

Under a collision storm (many keys in one slot), worst-case lookup degrades to

O (n)

Why does JSON nesting matter for documents?

The whole entity sits in one self-contained parcel, so one read returns it — no joins.

What is a "hop" in a graph?

Following exactly one edge from a node to a neighbour; in Neo4j it costs

O (1)

What is a network partition?

When cluster machines can't talk, splitting into groups that keep serving but can't sync.

What do the CAP letters C, A, P mean?

Consistency = reads see the latest write; Availability = every request gets a non-error answer; Partition tolerance = the system keeps running when nodes can't talk.

What do

\neg

and

\land

mean, and what does

\neg (C \land A)

say?

\neg

= "not",

\land

= "and";

\neg (C \land A)

= "you cannot have both C and A" (true during a partition).

What is eventual consistency?

Replicas may return stale answers just after a write but converge to the latest value once the network heals — temporary, not corruption.

What does BASE stand for?

Basically Available, Soft state, Eventually consistent — the AP opposite of ACID.

What do

N

W

R

stand for?

N

= replicas,

W

= replicas that must ack a write,

R

= replicas read from.

Why is lowercase

n

different from uppercase

N

n

= number of data items (Big-O);

N

= number of replicas (quorum) — unrelated counts, watch the case.

Walk the derivation of

W + R > N

To avoid overlap the write set and read set need

W + R

separate replicas; only

N

exist, so if

W + R > N

they must share at least

W + R - N \geq 1

replica holding the latest write.

What are the two meanings of "node"?

A graph dot (a data thing) vs a machine/server in a cluster — context decides.