vizlearn

Key-Value and Graph Models

Databases & SQLBy Updated

Two models at opposite ends: one that does almost nothing very fast, and one built entirely around following relationships.

Overview

Key-value: doing less on purpose

The interface is three ops:

get(key)  ->  value
put(key, value)
delete(key)

The value is opaque — a blob the store doesn't read. You can't query by its contents, sort by it, or join on it. There's no schema and no query language.

That poverty is the point. With no query planner, no join methods and no secondary indexes to maintain, a lookup is a hash and a read. Redis, Memcached, DynamoDB in its simplest mode and etcd all live here. They're fast in a way a all-round DB can't match, because they've far less to do.

The cost is that each access path must be designed in advance, coded in the key. Fetching a user by id means user:1234. Fetching them by email means keeping a second key, email:ada@example.com -> 1234, and keeping the two in step yourself — there's no unique constraint and no transaction spanning them.

The first variant above shows the shape: a two-column table used as nothing but a key lookup.

Where it fits. Caches, sessions, feature flags, rate limiters, leaderboards, service find. any of it with one obvious access path and a strong preference for speed.

Where it doesn't. any of it needing an ad-hoc question. "How many active sessions are from Leeds" isn't answerable without scanning each key, which the model isn't built for.

Key-Value and Graph Models

Both models, and the SQL equivalents

query.sql SQLite
Result

Worth knowing

A key-value store supports get, put and delete on an opaque value. That is the entire interface.
The narrowness is the feature: no query planner, no joins, and a lookup that is a hash away.
A graph model makes relationships first-class. Traversing them costs the same whether the graph is small or huge.
In SQL, a graph traversal is a recursive CTE — possible, and verbose enough to show why a dedicated model exists.

Key-Value and Graph Models

The simplest data model and the most tie-centred one. When each is worth leaving SQL for.

Graph: relationships as the primary thing

A graph model stores nodes and edges, and both can carry properties. The edges aren't derived from matching values, as a foreign key is. They're stored objects, and traversing one is following a pointer.

The difference shows up in queries about *paths*. "Who reports to Ada, right or indirectly, to any depth" is one traversal in a graph and a recursive CTE in SQL — run the variant and compare it against the plain join beside it.

The gap widens with depth. Each level of a relational traversal is another join, and the planner's guesses degrade as they compound. A graph engine follows edges right, and cost scales with the number of edges really visited rather than with the size of the tables.

Where it fits. Social networks, org charts, fraud rings, dependency graphs, recommendation paths, network topology, knowledge graphs. The test is whether your notable questions are about links rather than about fields.

Where it doesn't. Aggregating over millions of rows. A graph engine is often worse at "total revenue by month" than any relational DB.

The honest comparison

Key-valueRelationalGraph
Lookup by idfastestfastfast
Ad-hoc queriesnoyeslimited
Joinsnoyesnative, as traversal
Variable-depth pathsnorecursive CTEnative
Aggregationnoyesweak
Schema enforcementnonestrongusually light

Do you need to leave SQL?

Often not, and the variants above are the arg.

A key-value table in Postgres. A main key and a jsonb column — gets you most of the model with transactions and the option of querying the value later. Redis wins on raw latency. If that isn't the binding constraint, the simpler operational story often is.

Recursive CTEs handle graph traversal, and for a few hundred thousand edges at modest depth they're just right good. Dedicated graph engines start winning at deep traversals over large graphs, and at query *expressibility* — Cypher and Gremlin say in one line what a recursive CTE says in fifteen.

The strong arg for a separate store is when the workload is overwhelmingly of one shape. The weak arg is that the model is fashionable.

Why traversal depth is where graphs win

The graph edge isn't vague. It scales with depth, and the math shows where the crossover is. "Friends of friends of friends" over a social graph with an mean of 100 links per person touches, level by level, roughly 100 then 10,000 then 1,000,000 people. A relational engine reaches each level with another join, and the planner's row guesses degrade as they times:

depthpeople reached (branching ~100)relational cost
1100one join
210,000join of a join
31,000,000three joins, estimates compounding

A graph engine follows stored edges right. So Its cost tracks *edges really visited* rather than the product of table sizes, and it doesn't re-guess a join at each level. At depth one or two a recursive CTE is just right good. By depth three or four over a large graph the relational plan is doing work proportional to the tables while the graph is doing work proportional to the answer. That divergence — not lookup speed — is the real reason to reach for a graph.

The lookup, and why it is O(1)

The reason a key-value store outruns a general DB on its one job is the lack of a tree. A relational main-key lookup descends a B-tree — about log2(n) steps — while a hash-based key-value get finds one hash and does one read, even so of size:

keys storedB-tree lookuphash lookup
1,000,000~20 steps~1 probe
1,000,000,000~30 steps~1 probe

The B-tree's cost grows, slowly, forever. The hash's doesn't grow at all. That flat line is the whole value proposition, and it's bought by giving up all a tree enables — sorted scans, range queries, "the next key after this one" — none of which a hash can answer. So the choice isn't "key-value is faster" but "key-value is faster at point lookups and can't do ranges at all", which is just the trade to weigh before moving a workload off SQL for speed.

Questions people ask about Key-Value and Graph Models

What is a key-value store good for? Fast lookups by a known key, such as sessions, caches and counters. It does one thing and does it quickly.

Why is a key-value lookup O(1)? The key is hashed to find where the value is stored, so lookup time does not grow with the number of entries.

What is a graph database? A database that stores nodes and the relationships between them, and makes following those links a primary operation.

When does a graph beat SQL joins? When queries follow connections several hops deep, such as friends of friends. Each hop in SQL adds a join, while a graph follows stored links.

Can I query a key-value store by value? Not directly. You can only look up by key unless the store adds secondary indexes, so design keys around your queries.

Do I need to leave SQL for these workloads? Often not. Recursive CTEs handle many graph questions, and a table with a key column works as a simple key-value store. Switch when scale or traversal depth demands it.

Where it goes wrong with Key-Value and Graph Models

Using a key-value store as the system of record without a plan for secondary access. The second access path is your problem, forever.

given a graph DB is faster at all. It's faster at traversals and often slower at aggregates.

Recursive CTEs without a depth limit. A cycle in the data is an infinite loop. The variant here carries a guard for just that reason.

Modelling all as a graph. If the questions are about fields rather than links, a table is the better graph.

Check yourself

0 of 3

Answer without scrolling back up.

  1. Why is a key-value store fast?

  2. How does a graph edge differ from a SQL foreign key?

  3. What is a graph database usually worse at than a relational one?

Cheat sheet

Key-Value and Graph Models

Compare key-value and graph models against relational tables, see the queries each answers in one hop, and learn when leaving SQL pays off.

DATABASE · vizlearn.in/database/key_value_and_graph_models.html

More in Database

DatabaseOLTP, OLAP and Columnar StorageDatabaseStar Schema: Facts and DimensionsDatabaseSQL Injection and Parameterised QueriesDatabaseWhat are Relational Databases?

About the author

Ashish Jangra builds and maintains VizLearn. Every module here is written and the visualisation behind it hand-built, so the numbers in a readout come from the same code that draws the picture. Corrections are genuinely welcome and get priority over everything else — if a page states something wrong, or an animation misrepresents what the algorithm does, get in touch.

About VizLearnGitHubLinkedInContact