Skip to content

Adjacency List

An adjacency list is a pattern for modeling graph relationships in DynamoDB. Each node stores pointers to its adjacent nodes (parent, children, or related entities) using the sort key to represent the relationship.

The core structure

In a many-to-many relationship (e.g., Users ↔ Teams), the adjacency list stores a record for each edge:

pk = TEAM#t1, sk = MEMBER#u1   → "user u1 is in team t1"
pk = TEAM#t1, sk = MEMBER#u2   → "user u2 is in team t1"
pk = TEAM#t2, sk = MEMBER#u1   → "user u1 is in team t2"

Querying pk = TEAM#t1, sk begins_with MEMBER# returns all members of team t1. This is the adjacency list: each team partition contains a list of adjacent user nodes.

The inverse direction

The adjacency list above answers “who is in this team?” It does not directly answer “what teams is this user in?” That requires either:

  1. A duplicate record in the opposite direction: pk = USER#u1, sk = TEAM#t1
  2. A GSI inverse: project the relationship onto a GSI keyed by user ID

Most single-table designs use a GSI inverse to avoid duplicate records. See the Many-to-Many pattern for the full design.

In hierarchical data

For parent-child relationships (category trees, org charts), the adjacency list stores the parent reference:

pk = CAT#cat_smartphones, sk = #METADATA
Attributes: { parentId: "cat_electronics", name: "Smartphones", path: "electronics/smartphones" }

Each node stores its parent ID. Querying all children requires a GSI keyed by parentId. Querying the full subtree requires a materialized path approach (each node stores its full path from root). The adjacency list alone requires recursive queries for deep traversal. See the Hierarchical Data pattern for the combined adjacency list + materialized path design.

Adjacency list vs join table

In relational databases, many-to-many relationships use a join table. DynamoDB’s adjacency list is conceptually the same: a record per relationship edge stored within the single-table design. The difference is that the “join table” doesn’t exist as a separate table. The relationship records live alongside entity records in the same DynamoDB table, distinguished by sort key prefix.

See Hierarchical Data pattern for tree traversal and Many-to-Many Relationships pattern for the full adjacency list + GSI inverse approach.

← All glossary terms