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
Sulkemistaulukot ennakoivat ja tallentavat jokaisen esi-isä-päättäjä-suhteen, vaihtavat säilytystilaa loistaviin nopeisiin lukuihin. Tämä on se lähestymistapa, jota tämä blogi käyttää kommenttijärjestelmässään - kun lukee valtavan paljon enemmän, ylimääräinen inserttikompleksi kannattaa O(1) -kyselyillä esi-isille, jälkeläisille ja syvyysrajoitetuille alapuille.
Sulkemistaulukko on erillinen taulukko, joka Ennakoi ja varastoi jokaisen esi-isän ja alentuvan suhteen Sen sijaan, että olisimme selvittäneet "Keitä Comment 7:n esi-isät ovat?" kyselyhetkellä, olemme jo tallentaneet vastauksen: rivit, joissa sanotaan (1, 7), (3, 7), (7, 7) eli "Kommentit 1, 3 ja 7 ovat kaikki Comment 7:n esi-isiä" (ja 7 on itse esi-isä syvyydessä 0).
Avainnäkemys: Vaihdamme säilytystilaa ja kirjoitamme monimutkaisuutta flash-fast-lukemiinEsi-isien tai jälkeläisten saaminen muuttuu yksinkertaiseksi indeksoiduksi katseeksi rekursiivisen rajanylityspaikan sijaan.
Juuri tätä lähestymistapaa tämä blogi käyttää kommenttijärjestelmässään - kun lataat kommentteja viestiin, voimme hakea koko kierteisen rakenteen tehokkailla kyselyillä.
Jokainen toisiinsa liittyvä solmupari (edistäjä jälkeläiselle) saa rivin sulkemispöytään. Tärkeää on, että säilytämme myös syvyys - Kuinka monta hyppyä ne ovatkaan.
flowchart TD
subgraph "Comment Tree"
C1[Comment 1]
C2[Comment 2]
C3[Comment 3]
C4[Comment 4]
end
C1 --> C2
C1 --> C3
C3 --> C4
subgraph "Closure Table Entries"
direction LR
E1["(1,1,0) - 1 is ancestor of 1 at depth 0"]
E2["(2,2,0) - 2 is ancestor of 2 at depth 0"]
E3["(3,3,0) - 3 is ancestor of 3 at depth 0"]
E4["(4,4,0) - 4 is ancestor of 4 at depth 0"]
E5["(1,2,1) - 1 is ancestor of 2 at depth 1"]
E6["(1,3,1) - 1 is ancestor of 3 at depth 1"]
E7["(1,4,2) - 1 is ancestor of 4 at depth 2"]
E8["(3,4,1) - 3 is ancestor of 4 at depth 1"]
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
Huomautus:
WHERE descendant_id = 4WHERE ancestor_id = 1Tarvitsemme kaksi kokonaisuutta: itse Kommentti ja Sulkemiskirjaukset:
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; }
// Foreign key - which blog post this comment belongs to
public int PostId { get; set; }
public BlogPost Post { get; set; } = null!;
// ========== CLOSURE TABLE: Relationships stored in separate table ==========
// We still keep ParentCommentId for convenience - it's useful for:
// 1. Getting immediate parent without joining closure table
// 2. Keeping the option to use EF Core navigation properties
// 3. Human readability when debugging
public int? ParentCommentId { get; set; }
public Comment? ParentComment { get; set; }
public ICollection<Comment> Children { get; set; } = new List<Comment>();
// Navigation to the closure entries (optional - sometimes useful for eager loading)
// AncestorClosures: entries where THIS comment is the descendant
// DescendantClosures: entries where THIS comment is the ancestor
public ICollection<CommentClosure> AncestorClosures { get; set; } = new List<CommentClosure>();
public ICollection<CommentClosure> DescendantClosures { get; set; } = new List<CommentClosure>();
}
// The Closure Table entity
// Each row represents: "AncestorId is an ancestor of DescendantId at distance Depth"
public class CommentClosure
{
// Composite primary key: (AncestorId, DescendantId)
// This prevents duplicate entries and enables efficient lookups
public int AncestorId { get; set; }
public int DescendantId { get; set; }
// How many levels apart are they?
// 0 = same node (self-reference)
// 1 = immediate parent/child
// 2 = grandparent/grandchild
// etc.
public int Depth { get; set; }
// Navigation properties for joining back to Comments
public Comment Ancestor { get; set; } = null!;
public Comment Descendant { get; set; } = null!;
}
Konfiguraatio on enemmän mukana, koska meillä on kaksi kokonaisuutta, joilla on useita suhteita:
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);
// Relationship to blog post
builder.HasOne(c => c.Post)
.WithMany(p => p.Comments)
.HasForeignKey(c => c.PostId)
.OnDelete(DeleteBehavior.Cascade);
// Self-referencing relationship (kept for convenience, not strictly needed)
builder.HasOne(c => c.ParentComment)
.WithMany(c => c.Children)
.HasForeignKey(c => c.ParentCommentId)
.OnDelete(DeleteBehavior.Restrict);
// Indexes for common queries
builder.HasIndex(c => c.PostId);
builder.HasIndex(c => c.ParentCommentId);
builder.HasIndex(c => new { c.PostId, c.CreatedAt });
}
}
public class CommentClosureConfiguration : IEntityTypeConfiguration<CommentClosure>
{
public void Configure(EntityTypeBuilder<CommentClosure> builder)
{
// ========== COMPOSITE PRIMARY KEY ==========
// The combination of (AncestorId, DescendantId) uniquely identifies each relationship
// This also creates an implicit index on (AncestorId, DescendantId)
builder.HasKey(cc => new { cc.AncestorId, cc.DescendantId });
// ========== RELATIONSHIPS ==========
// Each closure entry has an Ancestor - the "higher up" comment
// One Comment can be the ancestor in MANY closure entries
// (a root comment is ancestor to all its descendants)
builder.HasOne(cc => cc.Ancestor)
.WithMany(c => c.DescendantClosures) // Comment's DescendantClosures = where it's the ancestor
.HasForeignKey(cc => cc.AncestorId)
.OnDelete(DeleteBehavior.Cascade); // Delete closures when comment is deleted
// Each closure entry has a Descendant - the "lower down" comment
// One Comment can be the descendant in MANY closure entries
// (a deeply nested comment has many ancestors)
builder.HasOne(cc => cc.Descendant)
.WithMany(c => c.AncestorClosures) // Comment's AncestorClosures = where it's the descendant
.HasForeignKey(cc => cc.DescendantId)
.OnDelete(DeleteBehavior.Cascade);
// ========== INDEXES ==========
// Index for "get all descendants of X" queries
// WHERE ancestor_id = @id
builder.HasIndex(cc => cc.AncestorId);
// Index for "get all ancestors of X" queries
// WHERE descendant_id = @id
builder.HasIndex(cc => cc.DescendantId);
// Index for "get immediate children" (depth = 1 queries)
// WHERE ancestor_id = @id AND depth = 1
builder.HasIndex(cc => new { cc.AncestorId, cc.Depth });
// Index for depth-limited queries
// WHERE ancestor_id = @id AND depth <= @maxDepth
builder.HasIndex(cc => new { cc.DescendantId, cc.Depth });
}
}
Tuloksena on kaksi taulukkoa:
erDiagram
COMMENT {
int id PK
string content
string author
datetime created_at
int post_id FK
int parent_comment_id FK "optional - for convenience"
}
COMMENT_CLOSURE {
int ancestor_id PK,FK
int descendant_id PK,FK
int depth "0=self, 1=parent, 2=grandparent..."
}
BLOG_POST {
int id PK
string title
string content
}
BLOG_POST ||--o{ COMMENT : "has"
COMMENT ||--o{ COMMENT : "parent-child"
COMMENT ||--o{ COMMENT_CLOSURE : "as ancestor"
COMMENT ||--o{ COMMENT_CLOSURE : "as descendant"
Tässä kohtaa sulkemistaulukot vaativat enemmän työtä kuin adjacence-listat. Jokaiselle esi-isälle on lisättävä sulkemispaikat:
public async Task<Comment> AddCommentAsync(
int postId,
int? parentId,
string author,
string content,
CancellationToken ct = default)
{
// Use a transaction to ensure atomicity
// We need to insert the comment AND all its closure entries together
await using var transaction = await context.Database.BeginTransactionAsync(ct);
try
{
// Step 1: Create the comment
var comment = new Comment
{
PostId = postId,
ParentCommentId = parentId,
Author = author,
Content = content,
CreatedAt = DateTime.UtcNow
};
context.Comments.Add(comment);
await context.SaveChangesAsync(ct);
// Step 2: Add the self-referencing closure entry
// EVERY node has a row pointing to itself at depth 0
// This simplifies queries - "get all ancestors including self" just needs depth >= 0
var selfClosure = new CommentClosure
{
AncestorId = comment.Id,
DescendantId = comment.Id,
Depth = 0
};
context.Set<CommentClosure>().Add(selfClosure);
// Step 3: If this is a reply, copy parent's closure entries with depth + 1
if (parentId.HasValue)
{
// Find all ancestors of the parent
// These become ancestors of our new comment too, but one level deeper
var parentClosures = await context.Set<CommentClosure>()
.Where(cc => cc.DescendantId == parentId.Value)
.ToListAsync(ct);
// For each ancestor of parent, add a closure to our new comment
foreach (var parentClosure in parentClosures)
{
var newClosure = new CommentClosure
{
AncestorId = parentClosure.AncestorId, // Same ancestor
DescendantId = comment.Id, // Points to new comment
Depth = parentClosure.Depth + 1 // One level deeper
};
context.Set<CommentClosure>().Add(newClosure);
}
}
await context.SaveChangesAsync(ct);
await transaction.CommitAsync(ct);
logger.LogInformation("Added comment {CommentId} with {ClosureCount} closure entries",
comment.Id, parentId.HasValue ? "multiple" : "1");
return comment;
}
catch
{
await transaction.RollbackAsync(ct);
throw;
}
}
Toisin kuin adjacency-lista, jossa kysymme ParentCommentIdiltä, suljemme kyselyn syvyydellä = 1:
public async Task<List<Comment>> GetChildrenAsync(int commentId, CancellationToken ct = default)
{
// Find all descendants at exactly depth 1 (immediate children)
// The closure table makes this a simple indexed lookup
return await context.Set<CommentClosure>()
.AsNoTracking()
.Where(cc => cc.AncestorId == commentId && cc.Depth == 1)
.Select(cc => cc.Descendant) // Navigate to the actual Comment
.OrderBy(c => c.CreatedAt)
.ToListAsync(ct);
}
Tässä sulkeutumistaulukot loistavat - yksi indeksoitu kysely, ei rekursiota:
public async Task<List<Comment>> GetAncestorsAsync(int commentId, CancellationToken ct = default)
{
// All ancestors = all closure entries where this comment is the descendant
// Exclude depth 0 (self-reference) unless you want "including self"
return await context.Set<CommentClosure>()
.AsNoTracking()
.Where(cc => cc.DescendantId == commentId && cc.Depth > 0)
.OrderByDescending(cc => cc.Depth) // Root ancestor first
.Select(cc => cc.Ancestor)
.ToListAsync(ct);
}
// Version that includes the comment itself
public async Task<List<Comment>> GetAncestorsIncludingSelfAsync(int commentId, CancellationToken ct = default)
{
return await context.Set<CommentClosure>()
.AsNoTracking()
.Where(cc => cc.DescendantId == commentId) // Depth >= 0
.OrderByDescending(cc => cc.Depth)
.Select(cc => cc.Ancestor)
.ToListAsync(ct);
}
Yhtä yksinkertaista - käännä kysely:
public async Task<List<Comment>> GetDescendantsAsync(int commentId, CancellationToken ct = default)
{
// All descendants = all closure entries where this comment is the ancestor
return await context.Set<CommentClosure>()
.AsNoTracking()
.Where(cc => cc.AncestorId == commentId && cc.Depth > 0)
.OrderBy(cc => cc.Depth) // Closest descendants first
.ThenBy(cc => cc.Descendant.CreatedAt)
.Select(cc => cc.Descendant)
.ToListAsync(ct);
}
Yhteinen vaatimus on rajoittaa pesintäsyvyyttä suoritus- tai UX-syistä:
public async Task<List<CommentWithDepth>> GetDescendantsToDepthAsync(
int commentId,
int maxDepth,
CancellationToken ct = default)
{
// The depth column makes this trivial - just add a WHERE clause
return await context.Set<CommentClosure>()
.AsNoTracking()
.Where(cc => cc.AncestorId == commentId
&& cc.Depth > 0
&& cc.Depth <= maxDepth)
.OrderBy(cc => cc.Depth)
.ThenBy(cc => cc.Descendant.CreatedAt)
.Select(cc => new CommentWithDepth
{
Id = cc.Descendant.Id,
Content = cc.Descendant.Content,
Author = cc.Descendant.Author,
CreatedAt = cc.Descendant.CreatedAt,
PostId = cc.Descendant.PostId,
ParentCommentId = cc.Descendant.ParentCommentId,
Depth = cc.Depth
})
.ToListAsync(ct);
}
public class CommentWithDepth
{
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 int? ParentCommentId { get; set; }
public int Depth { get; set; }
}
Esittääksesi kaikki kommentit viestissä, jossa on kierteitysrakenne:
public async Task<List<CommentTreeNode>> GetCommentTreeAsync(int postId, CancellationToken ct = default)
{
// STRATEGY:
// 1. Get all root comments for this post (no parent)
// 2. For each root, get its descendants from closure table
// 3. Build tree structure in memory
// First, get all comments for the post with their depths relative to root
var allComments = await context.Comments
.AsNoTracking()
.Where(c => c.PostId == postId)
.ToListAsync(ct);
if (!allComments.Any())
return new List<CommentTreeNode>();
// Get root comment IDs (comments with no parent)
var rootIds = allComments
.Where(c => c.ParentCommentId == null)
.Select(c => c.Id)
.ToHashSet();
// Get all closure entries to know the depths
var closures = await context.Set<CommentClosure>()
.AsNoTracking()
.Where(cc => allComments.Select(c => c.Id).Contains(cc.DescendantId)
&& rootIds.Contains(cc.AncestorId))
.ToListAsync(ct);
// Build lookup: comment ID -> its depth under its root ancestor
var depthLookup = closures
.GroupBy(cc => cc.DescendantId)
.ToDictionary(
g => g.Key,
g => g.Min(cc => cc.Depth) // Take minimum depth (from its root)
);
// Build the tree
var lookup = allComments.ToLookup(c => c.ParentCommentId);
return BuildTree(lookup, null);
}
private List<CommentTreeNode> BuildTree(ILookup<int?, Comment> lookup, int? parentId)
{
return lookup[parentId]
.Select(c => new CommentTreeNode
{
Comment = c,
Children = BuildTree(lookup, c.Id)
})
.ToList();
}
Sulkemistaulukot tekevät tästä suoraviivaista - löydä kaikki jälkeläiset sulkemisen kautta ja poista:
public async Task DeleteSubtreeAsync(int commentId, CancellationToken ct = default)
{
await using var transaction = await context.Database.BeginTransactionAsync(ct);
try
{
// Step 1: Find all descendants (including the comment itself)
var descendantIds = await context.Set<CommentClosure>()
.Where(cc => cc.AncestorId == commentId)
.Select(cc => cc.DescendantId)
.ToListAsync(ct);
// Step 2: Delete closure entries for all these nodes
// This includes both:
// - Entries where they are descendants (their ancestor relationships)
// - Entries where they are ancestors (their descendant relationships)
await context.Set<CommentClosure>()
.Where(cc => descendantIds.Contains(cc.AncestorId)
|| descendantIds.Contains(cc.DescendantId))
.ExecuteDeleteAsync(ct);
// Step 3: Delete the comments themselves
await context.Comments
.Where(c => descendantIds.Contains(c.Id))
.ExecuteDeleteAsync(ct);
await transaction.CommitAsync(ct);
logger.LogInformation("Deleted {Count} comments in subtree rooted at {CommentId}",
descendantIds.Count, commentId);
}
catch
{
await transaction.RollbackAsync(ct);
throw;
}
}
Täällä sulkemispöydät ovat kalliita. Subtreen siirtäminen edellyttää:
public async Task MoveSubtreeAsync(
int commentId,
int newParentId,
CancellationToken ct = default)
{
await using var transaction = await context.Database.BeginTransactionAsync(ct);
try
{
// Step 1: Get all descendants of the moving subtree (including itself)
var subtreeIds = await context.Set<CommentClosure>()
.Where(cc => cc.AncestorId == commentId)
.Select(cc => cc.DescendantId)
.ToListAsync(ct);
// Step 2: Get ancestors of the subtree root (nodes we're disconnecting from)
var oldAncestorIds = await context.Set<CommentClosure>()
.Where(cc => cc.DescendantId == commentId && cc.Depth > 0)
.Select(cc => cc.AncestorId)
.ToListAsync(ct);
// Step 3: Prevent cycles - can't move under own descendant
if (subtreeIds.Contains(newParentId))
{
throw new InvalidOperationException("Cannot move a node under its own descendant");
}
// Step 4: Delete old ancestor relationships
// Remove all closure entries that link old ancestors to subtree nodes
await context.Set<CommentClosure>()
.Where(cc => oldAncestorIds.Contains(cc.AncestorId)
&& subtreeIds.Contains(cc.DescendantId))
.ExecuteDeleteAsync(ct);
// Step 5: Get new ancestors (ancestors of new parent + new parent itself)
var newAncestors = await context.Set<CommentClosure>()
.Where(cc => cc.DescendantId == newParentId)
.ToListAsync(ct);
// Step 6: Get current subtree structure (relative depths within subtree)
var subtreeClosures = await context.Set<CommentClosure>()
.Where(cc => cc.AncestorId == commentId)
.ToListAsync(ct);
// Step 7: Create new closure entries
// For each new ancestor, link to each subtree node
var newClosures = new List<CommentClosure>();
foreach (var ancestorClosure in newAncestors)
{
foreach (var subtreeClosure in subtreeClosures)
{
// New depth = distance to new parent + 1 + depth within subtree
newClosures.Add(new CommentClosure
{
AncestorId = ancestorClosure.AncestorId,
DescendantId = subtreeClosure.DescendantId,
Depth = ancestorClosure.Depth + 1 + subtreeClosure.Depth
});
}
}
context.Set<CommentClosure>().AddRange(newClosures);
// Step 8: Update the direct parent reference on the root of moved subtree
var comment = await context.Comments.FindAsync(new object[] { commentId }, ct);
if (comment != null)
{
comment.ParentCommentId = newParentId;
}
await context.SaveChangesAsync(ct);
await transaction.CommitAsync(ct);
logger.LogInformation("Moved subtree of {Count} nodes from comment {CommentId} to new parent {NewParentId}",
subtreeIds.Count, commentId, newParentId);
}
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 (Simple lookup)
App->>EF: GetDescendantsAsync(commentId)
EF->>DB: SELECT * FROM closure WHERE ancestor_id = @id
DB-->>EF: Results (indexed lookup, O(1))
EF-->>App: List<Comment>
Note over App,DB: Inserting with Closures
App->>EF: AddCommentAsync(parentId, ...)
EF->>DB: INSERT comment
DB-->>EF: New ID
EF->>DB: SELECT * FROM closure WHERE descendant_id = parent_id
DB-->>EF: Parent's ancestors
EF->>DB: INSERT multiple closure entries
DB-->>EF: Done
EF-->>App: Comment
Toiminta Monimutkaisuus Tietokanta Kysymyksiä Muistiinpanoja |-----------|------------|------------------|-------| Lisää O(d) 2 = syvyys; yksi + sulkeminen Hanki lapsia O(1) Yksinkertaisesti indeksoituna MIHIN YHDYSVALLAT YHDYSVALLAT YHDYSVALLAT "Saadaan jälkeläisiä"(1) "Yksinkertaiseen indeksoituun MIHIN" Lisää syvyyden suodatin Move subtreet O(s) × d) Useita s = subtreet-koko, d = syvyys Remote subtreet O(s) 2 Etsi + irtotavarana
Sulkutaulukossa säilytetään O(n × d)-rivejä, joissa n = solmujen lukumäärä ja d = keskimääräinen syvyys:
Useimpien blogikommenttijärjestelmien kohdalla tämä yleisarvio on mitätön verrattuna kyselyn tuloshyötyihin.
Plussat ja miinukset |------|------| O(1) Esi-isän ja päähenkilön kyselyt O(d) insert kompleksisuus (syvempi insertti) Syvyyden rajatut kyselyt ovat vähäpätöisiä Varasto kasvaa syvyyden myötä (O(n × d) rivit) Ei rekursiivista SQL:tä tarvita Liikkuvat subtreet ovat kalliita "Kaikki syvyydessä N" tehokkaasti, monimutkaisempi inserttilogiikka Toimii minkä tahansa SQL-tietokannan kanssa Kaksi taulukkoa, joilla ylläpitää SQL-tietokantaa "Erinomainen raskaaseen työmäärään" "Erityinen työmäärään", "Erityinen työmäärään", "Erityinen työmäärään", "Erityinen työmäärään", "Erityinen työmäärään", "Erityinen työmäärään", "Erityinen työmäärään", "Erityinen työmäärään", "Erityinen työmäärään", "Erityinen työmäärään", "Erityinen työmäärään", "Erityinen työmäärään", "Erityinen"
Valitse sulkemistaulukko, kun:
Vältä sulkemistaulukkoa, kun:
Tämän blogin kommenttijärjestelmässä käytetään juuri tätä kaavaa. Valinta tehtiin, koska:
Sulkemistaulukon lukutehokkuuden hyödyt ovat huomattavasti suuremmat kuin sen kirjallisuuden monimutkaisuus tässä käyttökotelossa.
© 2026 Scott Galloway — Unlicense — All content and source code on this site is free to use, copy, modify, and sell.