Graph-Native Data Structures in C#, Part 2: Trees and Hierarchies with NebulaGraph

Part 1 of this series covered the property graph basics: VID design, tag schemas, basic CRUD, and standing up a NebulaPool singleton. If you landed here first, read that one before you carry on, because everything here builds on it.

The running example is an e-commerce category tree, Electronics > Phones > Smartphones > Android, with an org chart as a side note where the same patterns apply without any change.

Why Relational Hierarchy Models Break Down

Every .NET team builds a category tree in SQL eventually. The first attempt is an adjacency list: a ParentId column on the same table, a recursive CTE at query time, and some hope that the tree stays shallow. It works at a few hundred nodes and three levels.

Then the pressure comes from two directions. Depth first: recursive CTEs in SQL Server and PostgreSQL have no bound by default, and performance gets worse than linearly as depth and fan out grow. Writes second: the nested sets model buys fast reads with terrible write amplification, because every insert or move runs an UPDATE ... SET lft/rgt that rewrites a large part of the table. Moving a subtree of 200 categories under a new parent turns into thousands of row updates.

Org charts hit both at once. A company of 10,000 people with a matrix structure gets fan out at the top, depth at the leaves, and frequent reorganisations, which on nested sets is pure write pain.

A graph models this directly. Depth bounded traversal is a normal operation, and moving a subtree is two edge changes no matter how big the subtree is.

Modeling the Hierarchy

Schema and VID Design

The schema is small:

CREATE TAG category(name STRING, slug STRING);
CREATE EDGE parent_of();

VIDs follow the 'cat:' + slug convention from Part 1. Set vid_type = FIXED_STRING(64) on the space so real slugs fit. The default fixed length VID is 8 bytes, which is far too short.

Edge direction is parent to child. That feels backwards if you are used to "a child knows its parent", but REVERSELY makes walking up to ancestors easy, and walking down a subtree then follows the natural direction. Pointing parent_of downward is the right call.

Enforcing a Single Parent

NebulaGraph has no constraint that stops a second parent_of edge pointing at the same child. You have to enforce it in C# before the insert. Run this first:

GO 1 STEPS FROM 'cat:phones' OVER parent_of REVERSELY YIELD dst(edge) AS parentVid

If it returns a row, the node already has a parent, so throw before inserting the edge. Since 3.3.0 every vertex also needs at least one tag, and a bare VID insert is a schema error, so always pair INSERT VERTEX with the category tag.

Reading Subtrees

To walk down a subtree, use MATCH with a depth bounded variable length pattern:

MATCH p=(r:category)-[:parent_of*1..5]->(d:category)
WHERE id(r)=='cat:electronics'
RETURN id(d) AS vid, d.category.name AS name, d.category.slug AS slug, length(p) AS depth

Always set the upper bound. *1.. with no ceiling can time out or run out of memory on a graph that turns out to be deeper than you thought, or that has a cycle in it. For category trees *1..10 is a safe limit. For org charts you might go to *1..20.

One thing worth knowing: MATCH and GO treat cycles differently. If a back edge sneaks in, MATCH stops quietly at the edge it would revisit, which is safe but silent. GO keeps traversing vertices, although not the same edge twice. Use MATCH for subtree reads and you get the safer behaviour by default.

For direct children only, GO is shorter:

GO FROM 'cat:electronics' OVER parent_of YIELD dst(edge) AS childVid

For ancestors, the breadcrumb trail, use GO REVERSELY:

GO 1 TO 10 STEPS FROM 'cat:phones' OVER parent_of REVERSELY YIELD dst(edge) AS ancestorVid

Rebuilding the Tree in C#

The query gives you a flat list of (vid, name, slug, depth) rows. Rebuild the tree in memory with a dictionary keyed by VID:

public record CategoryNode(string Vid, string Name, string Slug, int Depth)
{
    public List<CategoryNode> Children { get; } = new();
}
 
public async Task<CategoryNode?> GetSubtreeAsync(string rootVid, int maxDepth = 5)
{
    var nql = $"""
        MATCH p=(r:category)-[:parent_of*1..{maxDepth}]->(d:category)
        WHERE id(r)=='{rootVid}'
        RETURN id(r) AS rootVid, id(d) AS vid,
               d.category.name AS name, d.category.slug AS slug,
               length(p) AS depth
        """;
 
    await using var session = await _nebulaPool.GetSessionAsync();
    var rows = await session.ExecuteAsync(nql)
                            .ToListAsync<FlatCategoryRow>();
    session.Release();
 
    if (rows.Count == 0) return null;
 
    // Build root from first row's rootVid (we didn't fetch root's own properties here;
    // for brevity assume a separate fetch or include root in a UNION)
    var index = new Dictionary<string, CategoryNode>();
    var root = new CategoryNode(rootVid, rows[0].RootName, rows[0].RootSlug, 0);
    index[rootVid] = root;
 
    // Sort ascending by depth so parents are always indexed before children
    foreach (var row in rows.OrderBy(r => r.Depth))
    {
        var node = new CategoryNode(row.Vid, row.Name, row.Slug, row.Depth);
        index[row.Vid] = node;
    }
 
    // Wire children. Needs a parent VID per row, so adjust the query
    // to RETURN id(nodes[-2]) as parentVid
    foreach (var row in rows.OrderBy(r => r.Depth))
    {
        if (index.TryGetValue(row.ParentVid, out var parent))
            parent.Children.Add(index[row.Vid]);
    }
 
    return root;
}

The shape is deliberate: one round trip, one flat result set, assembly in memory. Do not fetch children level by level in a loop. That brings back the N+1 problem a graph database is supposed to remove.

Mutations from C#

public async Task InsertNodeAsync(string parentVid, string name, string slug)
{
    var childVid = $"cat:{slug}";
 
    // Guard: child must not already have a parent
    var existingParentNql = $"GO 1 STEPS FROM '{childVid}' OVER parent_of REVERSELY YIELD dst(edge)";
    await using var session = await _nebulaPool.GetSessionAsync();
    var existing = await session.ExecuteAsync(existingParentNql).ToListAsync<VidRow>();
    if (existing.Count > 0)
        throw new InvalidOperationException($"Node {childVid} already has a parent.");
 
    // Guard: inserting childVid as child of parentVid must not create a cycle.
    // A cycle would exist if childVid is already an ancestor of parentVid.
    var ancestorsNql = $"GO 1 TO 10 STEPS FROM '{parentVid}' OVER parent_of REVERSELY YIELD dst(edge) AS vid";
    var ancestors = await session.ExecuteAsync(ancestorsNql).ToListAsync<VidRow>();
    if (ancestors.Any(a => a.Vid == childVid))
        throw new InvalidOperationException("Insert would create a cycle.");
 
    var batch = $"""
        INSERT VERTEX category(name, slug) VALUES '{childVid}':('{name}', '{slug}');
        INSERT EDGE parent_of() VALUES '{parentVid}'->'{childVid}':();
        """;
 
    await session.ExecuteAsync(batch);
    session.Release();
}
 
public async Task MoveSubtreeAsync(string nodeVid, string newParentVid)
{
    // Delete the old parent_of edge and insert the new one, two DML ops in one call.
    // Not atomic, so design callers to be idempotent on partial failure.
    var oldParentNql = $"GO 1 STEPS FROM '{nodeVid}' OVER parent_of REVERSELY YIELD dst(edge) AS vid";
    await using var session = await _nebulaPool.GetSessionAsync();
    var oldParents = await session.ExecuteAsync(oldParentNql).ToListAsync<VidRow>();
    if (oldParents.Count == 0) throw new InvalidOperationException("Node has no parent to move from.");
 
    var oldParentVid = oldParents[0].Vid;
    var batch = $"""
        DELETE EDGE parent_of '{oldParentVid}'->'{nodeVid}';
        INSERT EDGE parent_of() VALUES '{newParentVid}'->'{nodeVid}':();
        """;
    await session.ExecuteAsync(batch);
    session.Release();
}
 
public async Task<List<string>> GetAncestorsAsync(string nodeVid)
{
    var nql = $"GO 1 TO 10 STEPS FROM '{nodeVid}' OVER parent_of REVERSELY YIELD dst(edge) AS vid";
    await using var session = await _nebulaPool.GetSessionAsync();
    var rows = await session.ExecuteAsync(nql).ToListAsync<VidRow>();
    session.Release();
    return rows.Select(r => r.Vid).ToList(); // ordered outward from the node by hop count
}

MoveSubtreeAsync is the operation that destroys nested sets. Here it is two edge changes. The subtree itself needs nothing done to it, because every descendant edge is still correct. The catch is atomicity. NebulaGraph does not give you a multi statement transaction across an edge delete and an edge insert by default. Put both statements in the same session call, separated by semicolons, and make your application layer safe to retry.

Performance and Safety

Deep Trees and Fan Out

Bounding the depth is not optional. *1..N with a realistic ceiling is what stops an accidental unbounded walk. Fan out at a super node, a category with hundreds of direct children, is where things slow down. NebulaGraph v5.2, released in November 2025, added a SAMPLE clause that throttles traversal at super nodes so response times stay stable. If your tree has a very wide root, it is worth a look.

GET SUBGRAPH is an alternative to MATCH p=... when you want the whole induced subgraph, vertices and edges, instead of a path annotated result. On wide subtrees where you do not need the depth, it can be faster.

Checking for Cycles

A tree with a back edge is not a tree any more, and NebulaGraph enforces nothing at the schema level. The guards in InsertNodeAsync cover the normal case: before you insert a parent_of edge from P to C, check that C is not already in P's ancestor chain. If it is, that insert closes a cycle.

The same check applies to MoveSubtreeAsync. Confirm the new parent is not inside the subtree you are moving. You can reuse GetSubtreeAsync to list the subtree VIDs and assert the new parent is not one of them.

The GQL stored procedures in v5.2 make it possible to push cycle detection into the server and save a round trip. Worth watching as that feature settles.

A Note on Portability

Every MATCH query here is openCypher compatible and will move to another property graph engine. GO ... REVERSELY is nGQL only. NebulaGraph v5.0 was the first distributed graph database to implement ISO/IEC 39075 GQL and v5.2 goes further, so if portability matters to your team, prefer MATCH and the WITH clause over nGQL pipes (|) for compound queries.

The NebulaGraph migration article on this site covers the schema upgrade path if you are moving from a 3.x space to a 5.x deployment.

What Is Next

Part 3 moves from trees to general graphs: many to many relationships, weighted edges, and shortest path queries. Those are the cases where the relational model does not just strain, it gives up.