DynamoDB Single-Table Pattern: Hierarchical Data

Product categories. Org charts. Threaded comment trees. File system directories. Every application eventually needs to model a tree: each node has exactly one parent and potentially many children, with arbitrary depth.

DynamoDB has no built-in support for recursive queries. The solution combines two classical techniques: the adjacency list (each node stores its parent ID) for parent-child traversal, and a materialized path (each node stores its full path from root) for efficient subtree queries.

Access patterns

Five access patterns. One entity type. Two GSIs.

The two-index approach

No single index structure handles all tree operations efficiently in DynamoDB:

• Adjacency list alone (parent → children) handles AP1 and AP4 well, but getting a full subtree requires N sequential queries (one per level), which is unsuitable for deep trees.
• Materialized path alone (full path stored on each node) handles AP2 well with begins_with, but requires a full path update when a node moves.

Combined: adjacency list via GSI1 for direct-child queries; materialized path via GSI2 for subtree queries. Both write on the same item, so one PutItem per category creates both index entries automatically.

Table design

Primary key structure

GSI design

GSI1: adjacency list. All children of a parent share the same GSI1 partition key. Querying GSI1(pk=PARENT#cat_electronics) returns all direct children of Electronics. Top-level categories use parentId = "ROOT", so GSI1(pk=PARENT#ROOT) returns the homepage navigation.

GSI2: materialized path. All categories share one GSI2 partition key (CATALOG). The sort key is the materialized path suffixed with the category ID for uniqueness. Querying GSI2(pk=CATALOG, sk begins_with PATH#electronics/) returns Electronics and all its descendants at any depth in one Query call, no recursion.

The CATALOG constant as GSI2’s partition key means all categories land in one GSI partition. For category trees up to tens of thousands of nodes this is fine, since category reads are infrequent relative to product reads. At very large scale (millions of categories), shard by root category: CATALOG#electronics, CATALOG#clothing, etc.

Sample data

ROOT is a sentinel value, not a stored row. Top-level categories (Electronics, Clothing) set parentId = "ROOT" so Query(GSI1, pk=PARENT#ROOT) returns them as a group. There is no CAT#cat_root item.

Resolving each access pattern

AP1 — Get all direct children of Electronics:

Query(GSI1, gsi1pk=PARENT#cat_el)

Returns Smartphones and Laptops. Sorted by catId (deterministic but not alphabetical, so sort by name client-side if needed).

AP2 — Get full subtree under Electronics (for product listing):

Query(GSI2, gsi2pk=CATALOG, gsi2sk begins_with PATH#electronics/)

Returns Electronics, Smartphones, Laptops, iPhone. The entire subtree at all depths, in one call. This is the key win of the materialized path: no recursive queries.

AP3 — Get a specific category by ID:

GetItem(pk=CAT#cat_sm, sk=#METADATA)

One read, O(1).

AP4 — Get top-level categories (for homepage navigation):

Query(GSI1, gsi1pk=PARENT#ROOT)

Returns Electronics and Clothing.

AP5 — Breadcrumb for the iPhone category:

No extra query. The path attribute is electronics/smartphones/iphone. Split by /, capitalize, and you have the breadcrumb. If you need the full category names (not slugs), fetch each node by ID using BatchGetItem:

// iPhone path: "electronics/smartphones/iphone"
// Category IDs from the path segments would be stored separately,
// or you store the full ID path: "cat_el/cat_sm/cat_ip"
const breadcrumbIds = category.idPath.split('/')
const { Responses } = await dynamodb.batchGet({
  RequestItems: {
    [TABLE]: breadcrumbIds.map(id => ({ Key: { pk: `CAT#${id}`, sk: '#METADATA' } }))
  }
}).promise()

This is why storing both path (slug path) and idPath (ID path) on each category is useful: slug path for URL generation, ID path for breadcrumb batch lookups.

ElectroDB entity definition

export const CategoryEntity = new Entity({
  model: { entity: "category", version: "1", service: "catalog" },
  attributes: {
    catId:    { type: "string", required: true },
    name:     { type: "string", required: true },
    parentId: { type: "string", required: true }, // "ROOT" for top-level
    path:     { type: "string", required: true }, // "electronics/smartphones"
    depth:    { type: "number", required: true, default: 0 },
    createdAt: {
      type: "string",
      required: true,
      default: () => new Date().toISOString(),
      readOnly: true,
    },
  },
  indexes: {
    // AP3: Get a specific category by ID
    primary: {
      pk: { field: "pk",     composite: ["catId"],    template: "CAT#${catId}" },
      sk: { field: "sk",     composite: [],           template: "#METADATA" },
    },
    // AP1: Get direct children of a parent
    byParent: {
      index: "GSI1",
      pk: { field: "gsi1pk", composite: ["parentId"], template: "PARENT#${parentId}" },
      sk: { field: "gsi1sk", composite: ["catId"],    template: "CAT#${catId}" },
    },
    // AP2: Get subtree by path prefix
    byPath: {
      index: "GSI2",
      pk: { field: "gsi2pk", composite: [],           template: "CATALOG" },
      sk: { field: "gsi2sk", composite: ["path", "catId"], template: "PATH#${path}/${catId}" },
    },
  },
}, { client, table })

Why this design

Materialized path is the right subtree approach for DynamoDB. The alternative is recursive application-level queries: fetch children of root, then children of each child, and so on. For a tree with depth D and branching factor B, that’s B^D sequential round trips. For a product catalog with depth 4, that’s potentially thousands of requests. The materialized path collapses this to one begins_with query regardless of tree depth.

Moves are the tradeoff. Moving a subtree requires updating the path attribute on the moved node and all its descendants. In a category tree with 1,000 categories under Electronics, moving Electronics requires 1,000 UpdateItem calls. In practice category moves are rare admin operations, so the write cost is acceptable. For frequently-moved nodes, consider an adjacency-list-only approach and accept multiple-query subtree traversal.

The ROOT sentinel for parentId. Top-level nodes need a parentId that isn’t another category. Using a constant string "ROOT" (rather than null or undefined) ensures the GSI1 row is always written, making top-level category queries consistent with child queries. undefined values in ElectroDB don’t write GSI attributes.

Sort key uniqueness. The GSI2 sort key is PATH#<path>/<catId>. The catId suffix ensures uniqueness even if two categories share the same slug path (unlikely but possible during migrations or multi-tenant setups). Without the ID suffix, two categories with path electronics would collide in the GSI.

Handling deep trees and alternative patterns

For trees with depth > 10 or frequent subtree moves, consider:

Nested sets (preorder tree traversal): stores left and right integers on each node. Subtree queries are a range query on those integers. Extremely fast reads, expensive updates (every ancestor’s integers change on insert). Rarely used in DynamoDB. Better suited to read-heavy taxonomies in Postgres.

Closure table: stores every ancestor-descendant pair explicitly. O(depth) extra rows per node, but subtree queries are O(1) and moves are clean. Works in DynamoDB but write amplification grows with tree depth.

For most application category trees (depth 3–6, thousands of nodes, infrequent moves), the adjacency list + materialized path approach in this pattern is the right call.

Design this visually → coming soon

Category trees are the kind of schema that’s instantly obvious in a diagram and hard to hold in your head from a table. The parent-child arrows, the GSI projections, the path format. That’s what singletable.dev is building.

Join the waitlist →

Part of the SingleTable pattern library.