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 asettaa koko puurakenteen koodattavaksi vain kahdeksi kokonaisuudeksi solmua kohti - Vasen ja Oikea -rajoille syvyyden ensimmäisestä kävelylenkistä. Kaikkien jälkeläisten löytämisestä tulee yksinkertainen valikoimakysely, ja Order By Left antaa sinulle täydellisen näyttöjärjestyksen. Saalis? Jokainen insertti siirtää mahdollisesti tuhansia rivejä, mikä tekee tästä ihanteellisen vain luetuille, harvoin muokatuille hierarkioille.
Erytropoietiini Nested Set -malli (kutsutaan myös Modified Preorder Tree Traversal tai MPTT) Joe Celko, antaa kukin solmu kaksi numeroa: Left sekä Right. Nämä numerot on annettu puun syvän ensimmäisen ylityksen yhteydessä, ja Vasen on merkitty mennessään solmuun ja Oikea lähtiessä.
Maaginen ominaisuus: kaikilla noodin jälkeläisillä on vasemmisto- ja oikeistoarvot solmun oman vasemmiston ja oikeiston välilläTämä muuttaa hierarkkiset kyselyt yksinkertaisiksi valikoimakyselyiksi.
Avainymmärrys: Sen sijaan, että varastoisimme "kuka on minun vanhempani" (suhde), tallennamme "mikä on minun paikkani rajanylitysjärjestyksessä" (asento). WHERE Left > @myLeft AND Right < @myRight.
Kuvittele käveleväsi puun ympäri numeroin kulkiessasi:
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
Huomaa kuviot:
Vasen/oikea -arvot koodaavat koko puun rakenteen vain kahdeksi kokonaisuudeksi solmua kohti!
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"
Tässä pesät osoittavat suurimman heikkoutensa. siirrä kaikki solmut oikealle tehdä tilaa:
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;
}
}
Välittömien lasten löytäminen on hieman hankalaa - tarvitsemme solmuja, joita vanhemmat pitävät sisällään, mutta emme mitään välisolmuketta:
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
}
Yhden valikoiman kysely - erittäin tehokas:
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);
}
Täällä pesät todella loistavat:
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);
}
Yksi kysely palauttaa kaiken täydellisessä näyttöjärjestyksessä:
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);
}
Tai ilman raakaa SQL:tä (vähemmän tehokas, mutta puhdas 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;
}
Poistaminen on yksinkertaista, mutta vaatii uudelleenlukua:
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;
}
}
Tämä on monimutkaisin operaatio pesivien sarjojen osalta:
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
Toiminta Monimutkaisuus Tietokanta Kysymyksiä Muistiinpanoja |-----------|------------|------------------|-------| Kaikki solmut on siirrettävä oikealle. Hae lapsia O(1) If using ParentCommentId Hae esi-isiä O(1) Range query Hae jälkeläisiä O(1) Range query Järjestetään puu kuntoon 1 § Vasemmalla = täydellinen järjestys Move subtreet O(n) Monia kompleksinumeroita numeroidaan uudelleen 3. . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . .
Huomaa: O(n)-kompleksi inserteille/deleteille on ongelmallinen kirjapainosovelluksissa. Jokainen insertti saattaa koskettaa puun jokaista riviä!
Plussat ja miinukset |------|------| O(1) jälkeläinen/esi-isä kyselee O(n) inserttikompleksisuutta - jokainen insertti vaihtaa riviä Täydellinen näyttöjärjestys Order By Left O(n) poistaa ja siirtää monimutkaisuutta Syvyys laskettavissa esi-isien lukumäärän avulla Kirjoittakaa -lukot voivat aiheuttaa kiistaa Minimaalinen tallennustila (vain 2 kokonaislukua) Numerot voivat olla hyvin suuria monilla päivityksillä Single query palauttaa kokonaisen subtreen Rinnakkaiset muutokset ovat vaarallisia Ei liity tai rekursiivisia CTE:itä tarvitaan Vaatii liiketoimen jokaista kirjoitusta varten
Valitse Nested Setit, kun:
Vältä Nested Settejä, kun:
Jos vasen/oikea -arvot vioittuvat tai sinun täytyy lisätä pesityt sarjat olemassa olevaan dataan:
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;
}
}
Uudelleenlukutaajuuden vähentämiseksi voit jättää aukkoja:
// 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
Tämä vähentää numeroinnin kustannuksia, mutta lisää monimutkaisuutta.
© 2026 Scott Galloway — Unlicense — All content and source code on this site is free to use, copy, modify, and sell.