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
La liste d'adjacence est l'approche la plus simple et la plus intuitive pour stocker des données hiérarchiques - chaque rangée pointe juste à son parent. C'est ce que la plupart des développeurs atteignent pour la première fois, et pour les arbres peu profonds avec des déplacements fréquents, c'est souvent le bon choix. Cet article couvre les détails d'implémentation, y compris les CTE récursifs pour traverser l'arbre et construire des structures imbriquées pour l'affichage UI.
Le modèle de liste d'adjacence est l'approche que la plupart des développeurs atteignent pour la première fois, et avec une bonne raison - c'est intuitif. Chaque noeud stocke simplement une référence à son parent. Si vous avez déjà dessiné un arbre généalogique, vous avez déjà compris ce modèle.
La caractéristique clé: chaque rangée n'est au courant que de son parent immédiat. Pour trouver des grands-parents ou des petits-enfants, vous avez besoin de multiples recherches ou requêtes récursives.
C'est le modèle le plus souvent documenté et est bien soutenu par Relations d'auto-référencement d'EF Core.
L'entité est remarquablement simple - nous ajoutons simplement une auto-référence nulle :
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!;
// ========== ADJACENCY LIST: The hierarchy is defined by these three properties ==========
// ParentCommentId is nullable because:
// - Root-level comments (direct replies to the post) have NULL
// - Nested replies have the ID of the comment they're replying to
public int? ParentCommentId { get; set; }
// Navigation property to load the parent comment when needed
// Useful for breadcrumb trails: "Post > Comment by Alice > Comment by Bob"
public Comment? ParentComment { get; set; }
// Navigation property to load immediate children (NOT grandchildren!)
// EF Core populates this when you use .Include(c => c.Children)
// NOTE: This only gives you ONE level deep - you won't see replies to replies
public ICollection<Comment> Children { get; set; } = new List<Comment>();
}
La configuration met en place la relation d'auto-référencement et ajoute des index pour les requêtes que nous allons exécuter le plus souvent:
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);
// Standard relationship: comment belongs to a blog post
// Cascade delete here is safe - deleting a post should remove all its comments
builder.HasOne(c => c.Post)
.WithMany(p => p.Comments)
.HasForeignKey(c => c.PostId)
.OnDelete(DeleteBehavior.Cascade);
// ========== THE SELF-REFERENCING RELATIONSHIP ==========
// This is what makes it an adjacency list - each comment points to its parent
builder.HasOne(c => c.ParentComment)
.WithMany(c => c.Children) // One parent has many children
.HasForeignKey(c => c.ParentCommentId)
.OnDelete(DeleteBehavior.Restrict); // WARNING: Don't use Cascade here!
// Why Restrict and not Cascade?
// With Cascade, deleting a parent would automatically delete ALL children,
// grandchildren, etc. This can be:
// 1. Unexpected behaviour for users
// 2. A database performance issue (many deletes)
// 3. A data integrity risk (accidental mass deletion)
// Better to handle subtree deletion explicitly in application code
// ========== INDEXES: Critical for performance ==========
// Index on ParentCommentId - used when loading children
// "SELECT * FROM comments WHERE parent_comment_id = @id"
builder.HasIndex(c => c.ParentCommentId);
// Index on PostId - used when loading all comments for a post
// "SELECT * FROM comments WHERE post_id = @id"
builder.HasIndex(c => c.PostId);
// Composite index for the most common query:
// "Get all comments for a post, ordered by creation date"
builder.HasIndex(c => new { c.PostId, c.CreatedAt });
}
}
Le schéma qui en résulte est minimal - une seule clé étrangère auto-référencée :
erDiagram
COMMENT {
int id PK
string content
string author
datetime created_at
int post_id FK
int parent_comment_id FK "nullable - NULL for root comments"
}
BLOG_POST {
int id PK
string title
string content
}
BLOG_POST ||--o{ COMMENT : "has"
COMMENT ||--o{ COMMENT : "has children"
Les inserts sont magnifiquement simples - le motif de liste d'adjacence brille vraiment ici:
public async Task<Comment> AddCommentAsync(
int postId,
int? parentId, // NULL for root comment, parent's ID for a reply
string author,
string content,
CancellationToken ct = default)
{
// Creating a comment is just setting the parent reference
// No need to update closure tables, recalculate paths, or renumber anything
var comment = new Comment
{
PostId = postId,
ParentCommentId = parentId, // This single reference defines the hierarchy
Author = author,
Content = content,
CreatedAt = DateTime.UtcNow
};
context.Comments.Add(comment);
await context.SaveChangesAsync(ct);
logger.LogInformation("Added comment {CommentId} to post {PostId}", comment.Id, postId);
return comment;
}
Une seule requête indexée - rapide et simple:
public async Task<List<Comment>> GetChildrenAsync(int commentId, CancellationToken ct = default)
{
// This is WHERE adjacency lists shine - getting children is trivial
// Single indexed lookup: WHERE parent_comment_id = @id
return await context.Comments
.AsNoTracking() // Read-only, no tracking overhead
.Where(c => c.ParentCommentId == commentId) // Uses the index we defined
.OrderBy(c => c.CreatedAt) // Chronological order
.ToListAsync(ct);
}
Voici où les listes d'adjacence montrent leur faiblesse. Sans requêtes récursives, vous devriez faire plusieurs voyages aller-retour : obtenir le parent, obtenir le parent du parent, obtenir grand-parent... et ainsi de suite.
Heureusement, PostgreSQL CTE récursifs venir à la rescousse :
public async Task<List<Comment>> GetAncestorsAsync(int commentId, CancellationToken ct = default)
{
// WHY RAW SQL?
// EF Core doesn't have great support for recursive CTEs
// We need to drop down to raw SQL for this
// HOW THE CTE WORKS:
// 1. Start with the target comment (WHERE id = {0})
// 2. UNION ALL joins each result with its parent (JOIN on parent_comment_id)
// 3. PostgreSQL keeps doing this until no more parents are found
// 4. We exclude the starting comment (WHERE id != {0}) to get only ancestors
var sql = @"
WITH RECURSIVE ancestors AS (
-- Base case: start with our target comment
SELECT * FROM comments WHERE id = {0}
UNION ALL
-- Recursive case: join each result with its parent
SELECT c.*
FROM comments c
INNER JOIN ancestors a ON c.id = a.parent_comment_id
)
-- Return all ancestors except the starting comment, in ID order (root first)
SELECT * FROM ancestors WHERE id != {0}
ORDER BY id";
return await context.Comments
.FromSqlRaw(sql, commentId)
.AsNoTracking()
.ToListAsync(ct);
}
Il faut aussi un CTE récursif, mais cette fois nous suivons la profondeur au fur et à mesure :
public async Task<List<CommentWithDepth>> GetDescendantsWithDepthAsync(
int commentId,
CancellationToken ct = default)
{
// Similar to ancestors, but we go DOWN the tree instead of UP
// We also track depth so we know how to indent in the UI
var sql = @"
WITH RECURSIVE descendants AS (
-- Base case: start with our target comment at depth 0
SELECT *, 0 as depth FROM comments WHERE id = {0}
UNION ALL
-- Recursive case: find children of each result, incrementing depth
SELECT c.*, d.depth + 1
FROM comments c
INNER JOIN descendants d ON c.parent_comment_id = d.id
)
-- Return all descendants, ordered for display
-- depth first, then by creation time within each level
SELECT id, content, author, created_at, post_id, parent_comment_id, depth
FROM descendants
WHERE id != {0}
ORDER BY depth, created_at";
// Note: We need a special DTO to capture the depth column
// EF Core's FromSqlRaw won't automatically map extra columns to entity properties
return await context.Database
.SqlQueryRaw<CommentWithDepth>(sql, commentId)
.ToListAsync(ct);
}
// DTO to hold comment data plus computed depth
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; } // Computed by the CTE
}
Souvent, ce dont vous avez réellement besoin pour le rendu est une structure d'arbre, pas une liste plate. Voici comment construire un efficacement:
public async Task<List<CommentTreeNode>> GetCommentTreeAsync(int postId, CancellationToken ct = default)
{
// STRATEGY:
// 1. Load ALL comments for the post in a single query (fast, one round trip)
// 2. Build the tree structure in memory (also fast, just pointer manipulation)
// Step 1: Get all comments for this post
var allComments = await context.Comments
.AsNoTracking()
.Where(c => c.PostId == postId)
.OrderBy(c => c.CreatedAt) // Consistent ordering
.ToListAsync(ct);
// Step 2: Create a lookup by parent ID
// This gives us O(1) access to children of any comment
var lookup = allComments.ToLookup(c => c.ParentCommentId);
// Step 3: Build the tree starting from root comments (ParentCommentId = null)
return BuildTree(lookup, null);
}
private List<CommentTreeNode> BuildTree(
ILookup<int?, Comment> lookup,
int? parentId)
{
// Recursively build tree nodes
// lookup[parentId] gives us all comments whose parent is 'parentId'
return lookup[parentId]
.Select(c => new CommentTreeNode
{
Comment = c,
Children = BuildTree(lookup, c.Id) // Recurse to get children
})
.ToList();
}
public class CommentTreeNode
{
public Comment Comment { get; set; } = null!;
public List<CommentTreeNode> Children { get; set; } = new();
// Convenience property for UI
public bool HasChildren => Children.Count > 0;
}
Il faut d'abord trouver tous les descendants :
public async Task DeleteSubtreeAsync(int commentId, CancellationToken ct = default)
{
// We need to find and delete all descendants, then the comment itself
// Using a CTE to get all IDs, then bulk delete
var sql = @"
WITH RECURSIVE subtree AS (
SELECT id FROM comments WHERE id = {0}
UNION ALL
SELECT c.id FROM comments c
INNER JOIN subtree s ON c.parent_comment_id = s.id
)
DELETE FROM comments WHERE id IN (SELECT id FROM subtree)";
var deleted = await context.Database.ExecuteSqlRawAsync(sql, new object[] { commentId }, ct);
logger.LogInformation("Deleted {Count} comments in subtree rooted at {CommentId}",
deleted, commentId);
}
C'est là que les listes d'adjacence brillent vraiment - le déménagement est trivial:
public async Task MoveSubtreeAsync(
int commentId,
int newParentId,
CancellationToken ct = default)
{
// In adjacency list, moving a subtree is just updating ONE row!
// All descendants automatically move with their parent because
// their ParentCommentId still points to their direct parent
var comment = await context.Comments.FindAsync(new object[] { commentId }, ct);
if (comment == null)
{
throw new InvalidOperationException($"Comment {commentId} not found");
}
// Prevent creating a cycle (moving a node under its own descendant)
// This would create an infinite loop in our tree
var ancestors = await GetAncestorsAsync(newParentId, ct);
if (ancestors.Any(a => a.Id == commentId))
{
throw new InvalidOperationException("Cannot move a comment under its own descendant");
}
comment.ParentCommentId = newParentId;
await context.SaveChangesAsync(ct);
logger.LogInformation("Moved comment {CommentId} to new parent {NewParentId}",
commentId, newParentId);
}
sequenceDiagram
participant App as Application
participant EF as EF Core
participant DB as PostgreSQL
Note over App,DB: Getting Children (Simple - O(1))
App->>EF: GetChildrenAsync(commentId)
EF->>DB: SELECT * FROM comments WHERE parent_id = @id
DB-->>EF: Results (indexed lookup)
EF-->>App: List<Comment>
Note over App,DB: Getting Ancestors (Recursive - O(d) where d=depth)
App->>EF: GetAncestorsAsync(commentId)
EF->>DB: WITH RECURSIVE ancestors AS (...)
DB->>DB: Traverse parent_id chain recursively
DB-->>EF: All ancestors
EF-->>App: List<Comment>
Fonctionnement Complexité Base de données Voyages ronds Remarques |-----------|------------|---------------------|-------| Ajouter O(1)=1=1 Il suffit de définir ParentCommentaireId= Obtenir des enfants Obtenir des enfants Obtenir une recherche indexée Obtenir un enfant Obtenir un enfant Obtenir un enfant Obtenir un enfant Obtenir un enfant Obtenir un enfant Obtenir un enfant Obtenir un enfant Obtenir un enfant Obtenir un enfant Obtenir un enfant Obtenir un enfant Obtenir un enfant Obtenir un enfant Obtenir un enfant Obtenir un enfant Obtenir un enfant Obtenir un enfant Obtenir un enfant Obtenir un enfant Obtenez des ancêtres O(d)=1 (avec CTE)=d=profondeur, CTE fonctionne en DB= Obtenez le sous-arbre O(n)=1 (avec CTE)=n = taille du sous-arbre Déplacer le sous-tree O(1)=1=1 Il suffit de mettre à jour une ligne=1=1=1=1=1=1=1=1=1=1=1=1=1=1=1=1=1=1=1=1=1=1=1=1=1=1=1=1=1=1=1=1=1=1=1=1=1=1=1=1=1=1=1=1=1=1=1=1=1=1=1=1=1=1=1=1=1=1=1=1=1=1=1=1=1=1=1=1=1=1=1=1=1=1=1=1=1=1=1=1=1=1=1=1=1=1=1=1=1=1=1=1=1=1=1=1=1=1=1=1=1=1=1=1=1=1=1=1=1=1=1=1=1=1=1=1=1=1=1=1=1=1=1=1=1=1=1=1=1=1=1=1=1=1=1=1=1=1=1=1=1=1=1=1=1=1=1=1=1=1= Supprimer le sous-arbre O(n)=1 (avec CTE)=n = taille du sous-arbre
Points positifs |------|------| Simple à comprendre et à mettre en œuvre Obtenir des ancêtres/descendants nécessite des requêtes récursives Les CTE récursifs peuvent être lents sur des arbres très profonds. Déplacement d'un sous-arbre est trivial (mise à jour d'une ligne) Les propriétés de navigation EF Core fonctionnent naturellement. Impossible de compter facilement les descendants sans les charger. Aucune redondance de données à maintenir. Requêtes répétées pour les problèmes N+1 si ce n'est prudent.
Choisissez la liste d'adjacence lorsque :
Éviter la liste d'adjacence lorsque :
© 2026 Scott Galloway — Unlicense — All content and source code on this site is free to use, copy, modify, and sell.