This is a viewer only at the moment see the article on how this works.
To update the preview hit Ctrl-Alt-R (or ⌘-Alt-R on Mac) or Enter to refresh. The Save icon lets you save the markdown file to disk
This is a preview from the server running through my markdig pipeline
Saturday, 06 December 2025
Nested sets coderen de gehele boomstructuur in slechts twee gehele getallen per node - Links en rechts grenzen vanaf een diepte-eerste wandeling. Het vinden van alle afstammelingen wordt een eenvoudige bereik query, en ORDER BY Left geeft u perfecte weergave orde. De vangst? Elke invoegsel verschuift potentieel duizenden rijen, waardoor dit ideaal alleen voor read-heavy, zelden-gewijzigde hiërarchieën.
De Nested Set model (ook wel Modified Preorder Tree Traversal of MPTT genoemd), gepopulariseerd door Joe Celko, kent elk knooppunt twee nummers toe: Left en Right. Deze getallen worden toegewezen tijdens een diepte-eerste doorkruising van de boom, met Links toegewezen bij het invoeren van een knooppunt en Rechts toegewezen bij het verlaten.
De magische eigenschap: Alle afstammelingen van een knooppunt hebben Linkse en Rechtse waarden tussen links en rechtse knooppunten. Dit transformeert hiërarchische queries in eenvoudige range queries.
Belangrijkste inzicht: In plaats van op te slaan "wie is mijn ouder" (een relatie), slaan we op "waar pas ik in de traversale orde" (een positie). WHERE Left > @myLeft AND Right < @myRight.
Stel je voor dat je rond de boom loopt, nummering als je gaat:
flowchart TD
subgraph "Tree with Nested Set Numbers"
C1["Comment 1<br/>L=1, R=8"]
C2["Comment 2<br/>L=2, R=3"]
C3["Comment 3<br/>L=4, R=7"]
C4["Comment 4<br/>L=5, R=6"]
end
C1 --> C2
C1 --> C3
C3 --> C4
subgraph "The Traversal Walk"
direction LR
W["Start at root: L=1<br/>↓ Enter Comment 2: L=2<br/>↑ Leave Comment 2: R=3<br/>↓ Enter Comment 3: L=4<br/>↓ Enter Comment 4: L=5<br/>↑ Leave Comment 4: R=6<br/>↑ Leave Comment 3: R=7<br/>↑ Leave root: R=8"]
end
style C1 stroke:#6366f1,stroke-width:2px
style C2 stroke:#8b5cf6,stroke-width:2px
style C3 stroke:#8b5cf6,stroke-width:2px
style C4 stroke:#a855f7,stroke-width:2px
Let op de patronen:
De Links/Rechtse waarden coderen de gehele boomstructuur in slechts twee gehele getallen per knooppunt!
public class Comment
{
public int Id { get; set; }
public string Content { get; set; } = string.Empty;
public string Author { get; set; } = string.Empty;
public DateTime CreatedAt { get; set; }
public int PostId { get; set; }
public BlogPost Post { get; set; } = null!;
// ========== NESTED SETS ==========
// Left boundary - assigned when entering this node in depth-first walk
// Smaller values are "earlier" in the traversal
public int Left { get; set; }
// Right boundary - assigned when leaving this node in depth-first walk
// Always greater than Left for the same node
// Right - Left - 1 = number of descendants (times 2)
public int Right { get; set; }
// We keep ParentCommentId for:
// 1. Easier insert operations (need to know where to insert)
// 2. Moving nodes (need to track parent relationship)
// 3. EF Core navigation properties
// Note: The nested set values are the "source of truth" for hierarchy queries
public int? ParentCommentId { get; set; }
public Comment? ParentComment { get; set; }
public ICollection<Comment> Children { get; set; } = new List<Comment>();
// ========== COMPUTED HELPERS ==========
// A leaf node has no space between Left and Right for children
public bool IsLeaf => Right - Left == 1;
// Number of descendants = (Right - Left - 1) / 2
public int DescendantCount => (Right - Left - 1) / 2;
}
public class CommentConfiguration : IEntityTypeConfiguration<Comment>
{
public void Configure(EntityTypeBuilder<Comment> builder)
{
builder.HasKey(c => c.Id);
builder.Property(c => c.Content)
.IsRequired()
.HasMaxLength(10000);
builder.Property(c => c.Author)
.IsRequired()
.HasMaxLength(200);
// Left and Right are required - they define the hierarchy
builder.Property(c => c.Left).IsRequired();
builder.Property(c => c.Right).IsRequired();
// Relationship to blog post
builder.HasOne(c => c.Post)
.WithMany(p => p.Comments)
.HasForeignKey(c => c.PostId)
.OnDelete(DeleteBehavior.Cascade);
// Self-referencing (optional but useful for inserts)
builder.HasOne(c => c.ParentComment)
.WithMany(c => c.Children)
.HasForeignKey(c => c.ParentCommentId)
.OnDelete(DeleteBehavior.Restrict);
// ========== INDEXES ==========
// Critical for nested set queries!
// Most queries use Left for range comparisons
builder.HasIndex(c => c.Left);
// Right is used for "contains" queries
builder.HasIndex(c => c.Right);
// Composite index for the classic descendant query:
// WHERE Left > @left AND Right < @right
builder.HasIndex(c => new { c.Left, c.Right });
// Index for finding nodes in a specific post
builder.HasIndex(c => c.PostId);
// Index for ordering and display
builder.HasIndex(c => new { c.PostId, c.Left });
}
}
erDiagram
COMMENT {
int id PK
string content
string author
datetime created_at
int post_id FK
int parent_comment_id FK "optional"
int left "nested set left boundary"
int right "nested set right boundary"
}
BLOG_POST {
int id PK
string title
string content
}
BLOG_POST ||--o{ COMMENT : "has"
COMMENT ||--o{ COMMENT : "parent-child"
Dit is waar geneste sets tonen hun grootste zwakte. Om een nieuwe knooppunt in te voegen, moeten we alle knooppunten naar rechts verplaatsen om ruimte te maken:
public async Task<Comment> AddCommentAsync(
int postId,
int? parentId,
string author,
string content,
CancellationToken ct = default)
{
await using var transaction = await context.Database.BeginTransactionAsync(ct);
try
{
int newLeft, newRight;
if (parentId.HasValue)
{
// Get the parent's Right value - we'll insert just before it
var parent = await context.Comments
.FirstOrDefaultAsync(c => c.Id == parentId.Value, ct);
if (parent == null)
throw new InvalidOperationException($"Parent comment {parentId} not found");
// New node will be inserted at parent's Right position
// (making it the last child of this parent)
newLeft = parent.Right;
newRight = parent.Right + 1;
// ========== THE EXPENSIVE PART ==========
// Shift ALL nodes with Left >= newLeft to the right by 2
// This makes room for our new node's Left and Right values
// Update Right values first (nodes that "end" after our insert point)
await context.Comments
.Where(c => c.PostId == postId && c.Right >= newLeft)
.ExecuteUpdateAsync(s => s.SetProperty(c => c.Right, c => c.Right + 2), ct);
// Update Left values (nodes that "start" after our insert point)
await context.Comments
.Where(c => c.PostId == postId && c.Left >= newLeft)
.ExecuteUpdateAsync(s => s.SetProperty(c => c.Left, c => c.Left + 2), ct);
}
else
{
// Root comment - find the max Right value and add after
var maxRight = await context.Comments
.Where(c => c.PostId == postId)
.MaxAsync(c => (int?)c.Right, ct) ?? 0;
newLeft = maxRight + 1;
newRight = maxRight + 2;
// No shifting needed - we're adding at the end
}
// Create the new comment with calculated Left/Right
var comment = new Comment
{
PostId = postId,
ParentCommentId = parentId,
Author = author,
Content = content,
CreatedAt = DateTime.UtcNow,
Left = newLeft,
Right = newRight
};
context.Comments.Add(comment);
await context.SaveChangesAsync(ct);
await transaction.CommitAsync(ct);
logger.LogInformation("Added comment {CommentId} at L={Left}, R={Right}",
comment.Id, newLeft, newRight);
return comment;
}
catch
{
await transaction.RollbackAsync(ct);
throw;
}
}
Het vinden van directe kinderen is een beetje lastig - we hebben knooppunten nodig die door de ouder, maar niet door een tussenknoop:
public async Task<List<Comment>> GetChildrenAsync(int commentId, CancellationToken ct = default)
{
// Option 1: Use ParentCommentId (simple, if you've kept it)
return await context.Comments
.AsNoTracking()
.Where(c => c.ParentCommentId == commentId)
.OrderBy(c => c.Left) // Order by position in tree
.ToListAsync(ct);
// Option 2: Pure nested set approach (more complex)
// A child is a node that:
// - Is contained by the parent (Left > parent.Left AND Right < parent.Right)
// - Is not contained by any other node that is also contained by the parent
//
// This requires a subquery or additional logic - ParentCommentId is simpler
}
Een enkele bereik query - zeer efficiënt:
public async Task<List<Comment>> GetAncestorsAsync(int commentId, CancellationToken ct = default)
{
var comment = await context.Comments
.AsNoTracking()
.FirstOrDefaultAsync(c => c.Id == commentId, ct);
if (comment == null)
return new List<Comment>();
// Ancestors are nodes that CONTAIN this node
// A node contains another if: ancestor.Left < node.Left AND ancestor.Right > node.Right
return await context.Comments
.AsNoTracking()
.Where(c => c.Left < comment.Left && c.Right > comment.Right)
.OrderBy(c => c.Left) // Root first (smallest Left)
.ToListAsync(ct);
}
Dit is waar geneste sets echt schijnen:
public async Task<List<Comment>> GetDescendantsAsync(int commentId, CancellationToken ct = default)
{
var comment = await context.Comments
.AsNoTracking()
.FirstOrDefaultAsync(c => c.Id == commentId, ct);
if (comment == null)
return new List<Comment>();
// Descendants are nodes CONTAINED BY this node
// Simple range query - extremely efficient with indexes
return await context.Comments
.AsNoTracking()
.Where(c => c.Left > comment.Left && c.Right < comment.Right)
.OrderBy(c => c.Left) // Depth-first order - perfect for display!
.ToListAsync(ct);
}
Eén query geeft alles terug in perfecte weergavevolgorde:
public async Task<List<CommentWithDepth>> GetTreeInOrderAsync(int postId, CancellationToken ct = default)
{
// The beauty of nested sets: ORDER BY Left gives you depth-first order!
// This is the exact order you'd want for displaying a threaded view
// Calculate depth using a subquery that counts ancestors
var sql = @"
SELECT
c.*,
(SELECT COUNT(*)
FROM comments ancestor
WHERE ancestor.post_id = c.post_id
AND ancestor.left < c.left
AND ancestor.right > c.right
) as depth
FROM comments c
WHERE c.post_id = {0}
ORDER BY c.left";
return await context.Database
.SqlQueryRaw<CommentWithDepth>(sql, postId)
.ToListAsync(ct);
}
Of zonder ruwe SQL (minder efficiënte maar pure EF Core):
public async Task<List<CommentWithDepth>> GetTreeInOrderEfCoreAsync(
int postId,
CancellationToken ct = default)
{
// Get all comments ordered by Left (depth-first order)
var comments = await context.Comments
.AsNoTracking()
.Where(c => c.PostId == postId)
.OrderBy(c => c.Left)
.ToListAsync(ct);
// Calculate depth for each by counting ancestors in memory
var result = new List<CommentWithDepth>();
foreach (var comment in comments)
{
// Count how many other comments contain this one
var depth = comments.Count(c =>
c.Left < comment.Left && c.Right > comment.Right);
result.Add(new CommentWithDepth
{
Id = comment.Id,
Content = comment.Content,
Author = comment.Author,
CreatedAt = comment.CreatedAt,
PostId = comment.PostId,
ParentCommentId = comment.ParentCommentId,
Depth = depth
});
}
return result;
}
Verwijderen is eenvoudig, maar vereist hernummering:
public async Task DeleteSubtreeAsync(int commentId, CancellationToken ct = default)
{
await using var transaction = await context.Database.BeginTransactionAsync(ct);
try
{
var comment = await context.Comments
.FirstOrDefaultAsync(c => c.Id == commentId, ct);
if (comment == null)
throw new InvalidOperationException($"Comment {commentId} not found");
var postId = comment.PostId;
var left = comment.Left;
var right = comment.Right;
// Width of the subtree being deleted
var width = right - left + 1;
// Delete all nodes in the range
var deleted = await context.Comments
.Where(c => c.Left >= left && c.Right <= right)
.ExecuteDeleteAsync(ct);
// Shift all nodes to the right of deleted subtree LEFT by width
// (closing the gap)
await context.Comments
.Where(c => c.PostId == postId && c.Right > right)
.ExecuteUpdateAsync(s => s.SetProperty(c => c.Right, c => c.Right - width), ct);
await context.Comments
.Where(c => c.PostId == postId && c.Left > right)
.ExecuteUpdateAsync(s => s.SetProperty(c => c.Left, c => c.Left - width), ct);
await transaction.CommitAsync(ct);
logger.LogInformation("Deleted {Count} comments, shifted remaining nodes by {Width}",
deleted, width);
}
catch
{
await transaction.RollbackAsync(ct);
throw;
}
}
Dit is de meest complexe bewerking voor geneste sets:
public async Task MoveSubtreeAsync(
int commentId,
int newParentId,
CancellationToken ct = default)
{
await using var transaction = await context.Database.BeginTransactionAsync(ct);
try
{
var node = await context.Comments.FirstOrDefaultAsync(c => c.Id == commentId, ct);
var newParent = await context.Comments.FirstOrDefaultAsync(c => c.Id == newParentId, ct);
if (node == null || newParent == null)
throw new InvalidOperationException("Node or parent not found");
// Prevent cycle: can't move node under its own descendant
if (newParent.Left >= node.Left && newParent.Right <= node.Right)
throw new InvalidOperationException("Cannot move node under its own descendant");
var postId = node.PostId;
var width = node.Right - node.Left + 1;
// This is complex! The algorithm:
// 1. Mark nodes to move (using temporary negative values)
// 2. Close the gap where nodes were
// 3. Make room at new position
// 4. Move nodes to new position
// 5. Fix the signs back
// Use a stored procedure or multiple updates for production
// This simplified version shows the concept:
var oldLeft = node.Left;
var oldRight = node.Right;
var newPosition = newParent.Right;
// Step 1: Temporarily mark nodes by making Left/Right negative
await context.Comments
.Where(c => c.PostId == postId && c.Left >= oldLeft && c.Right <= oldRight)
.ExecuteUpdateAsync(s => s
.SetProperty(c => c.Left, c => -c.Left)
.SetProperty(c => c.Right, c => -c.Right), ct);
// Step 2: Close gap
await context.Comments
.Where(c => c.PostId == postId && c.Left > 0 && c.Right > oldRight)
.ExecuteUpdateAsync(s => s.SetProperty(c => c.Right, c => c.Right - width), ct);
await context.Comments
.Where(c => c.PostId == postId && c.Left > oldRight)
.ExecuteUpdateAsync(s => s.SetProperty(c => c.Left, c => c.Left - width), ct);
// Recalculate newPosition (it may have shifted)
var updatedParent = await context.Comments.FirstAsync(c => c.Id == newParentId, ct);
newPosition = updatedParent.Right;
// Step 3: Make room at new position
await context.Comments
.Where(c => c.PostId == postId && c.Left > 0 && c.Right >= newPosition)
.ExecuteUpdateAsync(s => s.SetProperty(c => c.Right, c => c.Right + width), ct);
await context.Comments
.Where(c => c.PostId == postId && c.Left >= newPosition)
.ExecuteUpdateAsync(s => s.SetProperty(c => c.Left, c => c.Left + width), ct);
// Step 4: Calculate offset and move nodes
var offset = newPosition - oldLeft;
await context.Comments
.Where(c => c.PostId == postId && c.Left < 0)
.ExecuteUpdateAsync(s => s
.SetProperty(c => c.Left, c => -c.Left + offset)
.SetProperty(c => c.Right, c => -c.Right + offset), ct);
// Step 5: Update parent reference
node = await context.Comments.FirstAsync(c => c.Id == commentId, ct);
node.ParentCommentId = newParentId;
await context.SaveChangesAsync(ct);
await transaction.CommitAsync(ct);
logger.LogInformation("Moved subtree of width {Width} from position {OldPos} to {NewPos}",
width, oldLeft, newPosition);
}
catch
{
await transaction.RollbackAsync(ct);
throw;
}
}
sequenceDiagram
participant App as Application
participant EF as EF Core
participant DB as PostgreSQL
Note over App,DB: Getting Descendants (Range query)
App->>EF: GetDescendantsAsync(commentId)
EF->>DB: SELECT * FROM comments WHERE id = @id
DB-->>EF: Node (L=4, R=11)
EF->>DB: SELECT * FROM comments WHERE left > 4 AND right < 11
DB-->>EF: All descendants
EF-->>App: List<Comment>
Note over App,DB: Insert (Expensive!)
App->>EF: AddCommentAsync(parentId, ...)
EF->>DB: SELECT right FROM comments WHERE id = @parentId
DB-->>EF: Parent's right = 11
EF->>DB: UPDATE comments SET right = right + 2 WHERE right >= 11
EF->>DB: UPDATE comments SET left = left + 2 WHERE left >= 11
EF->>DB: INSERT comment (left=11, right=12)
EF-->>App: Comment
Operatie Complexiteit Database Queries Notes |-----------|------------|------------------|-------| Moet alle nodes naar rechts verplaatsen
Opmerking: De O(n) complexiteit voor inserts/deletes is problematisch voor schrijfzware toepassingen. Elke insert raakt mogelijk elke rij in de boom!
Bedankt voor je hulp. |------|------| O(1) afstammeling/lanceur queries O(n) invoegen complexiteit - elke invoegsel verschuift rijen Perfecte weergavevolgorde van ORDER BY Left O(n) verwijderen en verplaatsen complexiteit Depth calculable via voorouders tellen Schrijf sloten kan leiden tot onweerlegbaarheid Minimale opslag (slechts 2 gehele getallen) Aantallen kunnen zeer groot worden met vele updates Single query geeft hele subtree terug modificaties zijn gevaarlijk. Geen joins of recursieve CTE's nodig • Vereist transactie voor elke schrijven •
Kies geneste verzamelingen wanneer:
Nested Sets vermijden wanneer:
Als Links/Rechtse waarden beschadigd raken of als je geneste verzamelingen moet toevoegen aan bestaande gegevens:
public async Task RebuildNestedSetsAsync(int postId, CancellationToken ct = default)
{
await using var transaction = await context.Database.BeginTransactionAsync(ct);
try
{
// Load all comments with parent relationships
var comments = await context.Comments
.Where(c => c.PostId == postId)
.OrderBy(c => c.CreatedAt)
.ToListAsync(ct);
// Build parent-children lookup
var childrenLookup = comments.ToLookup(c => c.ParentCommentId);
// Walk the tree depth-first, assigning Left/Right
int counter = 0;
void Walk(int? parentId)
{
foreach (var comment in childrenLookup[parentId])
{
counter++;
comment.Left = counter;
Walk(comment.Id); // Recurse to children
counter++;
comment.Right = counter;
}
}
Walk(null); // Start with root nodes
await context.SaveChangesAsync(ct);
await transaction.CommitAsync(ct);
logger.LogInformation("Rebuilt nested sets for post {PostId}: {Count} comments",
postId, comments.Count);
}
catch
{
await transaction.RollbackAsync(ct);
throw;
}
}
Om de frequentie van hernummering te verminderen, kunt u hiaten achterlaten:
// Instead of consecutive: 1, 2, 3, 4, 5, 6, 7, 8
// Use gaps: 100, 200, 300, 400, 500, 600, 700, 800
// Inserts can fit in gaps without shifting:
// Insert between 200 and 300: use 250
// Only renumber when gaps run out
Dit vermindert de kosten van hernummering, maar voegt complexiteit toe.
© 2026 Scott Galloway — Unlicense — All content and source code on this site is free to use, copy, modify, and sell.