关闭表格预先计算并存储了每一个祖先- 后代的关系, 交换存储空间用于燃烧快速读取。 这是博客用于评论系统的方法 — — 当阅读数量大大超过写作时, 附加的复杂内容会用O(1)查询祖先、 后代和深度有限的亚树来弥补 。
审结表是一张单独的表格, 预估和储存所有祖先与后代的关系 我们没有找出“第7项评论的祖先是谁?” 在询问时,我们通过翻过这棵树,已经储存了答案:一行说(1、7、3、7、7、7、7、7),意思是“第1、3和7项评论都是第7项评论的祖先”(7项在深度是7项评论的祖先)。
关键的洞察力: 我们交换存储空间 并写出复杂的 燃烧快读使祖先或后代成为简单的索引搜索,而不是累进式跨行。
这是博客在评论系统上所使用的方法, 当您在文章上加载评论时, 我们可以通过有效的查询来获取整个线条结构。
每一对相关节点(祖先与后代)在封闭表上划一行。 关键是, 我们还保存 深度深度 - 有多少跳 分开他们。
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
通知 :
WHERE descendant_id = 4WHERE ancestor_id = 1我们需要两个实体:评论本身和关闭条目:
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!;
}
由于我们有两个实体存在多重关系, 组合的参与程度更高:
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 });
}
}
由此产生的方案有两个表格:
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"
关闭表需要比相邻列表更多的工作。 我们必须为每个祖先添加关闭条目 :
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;
}
}
与我们根据家长CommentId 查询的相邻列表不同, 关闭时我们通过深度查询 = 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);
}
这是关闭表光照的地方 - 单一索引查询, 不重复 :
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);
}
同样简单 - 只需翻转查询 :
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);
}
一个共同的要求是,由于性能或UX的原因,限制嵌套深度:
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; }
}
用于显示带有线索结构的邮件上的所有批注 :
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();
}
封闭表使这一点直截了当 -- -- 通过封闭找到所有后代,然后删除:
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;
}
}
这是关闭表昂贵的地方。 移动子树需要 :
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
操作 复杂度 数据库查询 备注 备注
|-----------|------------|------------------|-------|
插入 O(d) 2 d = 深度; 1 插入 + 关闭创建
让孩子 O(1) \ \ 1 \ 简单的索引到哪里 \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \
获得祖先 O(1) 1 简单索引
让后代 O(1) \ \ 1 \ 简单索引到哪里 \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \
关闭表存储 O(n x d) 行,其中 n = 节点数, d = 平均深度:
对于大多数博客评论系统来说,与询问的绩效效益相比,这一间接费用微不足道。
|------|------| O(1) 祖先/后代查询 O(d) 插入复杂性(深度插入) 深度限制的查询是无关紧要的 储量随深度增长 (O(n) × d) 行) 不需要循环 SQL 移动子树是昂贵的 能够有效查询“所有深度N” 更复杂的插入逻辑 使用任何 SQL 数据库
选择关闭表格的时间 :
避免关闭表格时:
这个博客的评论系统正是使用这个模式。
结束表阅读的绩效效益远远超过了这一使用案例的写作复杂性。
© 2026 Scott Galloway — Unlicense — All content and source code on this site is free to use, copy, modify, and sell.