La lista dell'adiacenza è l'approccio più semplice e intuitivo alla memorizzazione dei dati gerarchici - ogni riga punta solo al suo genitore. È ciò che la maggior parte degli sviluppatori raggiunge per primo, e per gli alberi poco profondi con frequenti mosse, è spesso la scelta giusta. Questo articolo copre i dettagli di implementazione, compresi i CTE ricorsivi per attraversare l'albero e costruire strutture annidate per visualizzare l'interfaccia utente.

Navigazione serie

• Parte 1: Panoramica - Introduzione e confronto
• Parte 1.1: Elenco degli adiacenze (questo articolo)
• Parte 1.2: Tabella di chiusura
• Parte 1.3: Percorso materializzato
• Parte 1.4: Set nidificati
• Parte 1.5: Albero

Che cos'è una lista di adiacenze?

Il modello di lista adjacence è l'approccio più sviluppatori raggiungono per primo, e con buona ragione - è intuitivo. Ogni nodo memorizza semplicemente un riferimento al suo genitore. Se hai mai disegnato un albero genealogico, hai già capito questo modello.

La caratteristica chiave: ogni riga conosce solo il suo genitore immediato. Per trovare nonni o nipoti, è necessario più ricerche o domande ricorsive.

Questo è il modello più comunemente documentato ed è ben supportato da Le relazioni di auto-referenziazione dell'EF Core.

Definizione dell'entità

L'entità è straordinariamente semplice - basta aggiungere un auto-riferimento annullabile:

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>();
}

Configurazione del nucleo EF

La configurazione imposta il rapporto di auto-referenziazione e aggiunge in modo cruciale gli indici per le query che eseguiremo più spesso:

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 });
    }
}

Schema della banca dati

Lo schema risultante è minimo - solo una chiave di auto-referenziazione straniera:

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"

Operazioni

Inserisci un nuovo commento

Gli inserti sono splendidamente semplici - il modello di lista di adiacenza brilla davvero qui:

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;
}

Ottieni bambini immediati

Interrogazione indicizzata singola - veloce e semplice:

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);
}

Ottenere antenati (la parte dura)

Qui è dove le liste dell'adiacenza mostrano la loro debolezza. Senza query ricorsive, dovreste fare più viaggi di andata e ritorno: ottenere il genitore, ottenere il genitore, ottenere il nonno... e così via.

Per fortuna, PostgreSQL CTE ricorsive Vieni in soccorso:

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);
}

Ottieni intero sottoalbero con profondità

Richiede anche un CTE ricorsivo, ma questa volta seguiamo la profondità mentre andiamo:

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
}

Costruire una struttura a Albero Nestato per UI

Spesso ciò di cui hai bisogno per il rendering è una struttura ad albero, non una lista piatta. Ecco come costruirne uno in modo efficiente:

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;
}

Elimina un sottoalbero

L'eliminazione richiede di trovare tutti i discendenti prima:

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);
}

Sposta un sottoalbero

Qui è dove le liste di adiacenza realmente brillano - muoversi è banale:

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);
}

Visualizzazione del flusso di interrogazione

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>

Caratteristiche di prestazione

Pro e contro

Quando usare l'elenco Adiacenza

Scegliere Lista Adjacence quando:

• La vostra gerarchia è bassa (meno di 5-6 livelli)
• Sposta spesso i sottopiani
• Vuoi che le proprietà di navigazione di EF Core funzionino in modo naturale
• Requisiti semplici per i CTE ricorsivi accettabili
• Inserisci prestazioni è più importante delle prestazioni di lettura

Evitare l'elenco di adjacency quando:

• Hai gerarchie profonde (10+ livelli)
• Si interroga spesso "tutti i discendenti" o "tutti gli antenati"
• La lettura delle prestazioni è fondamentale
• Devi contare i discendenti senza caricarli

Navigazione serie

• Parte 1: Panoramica
• Parte 1.1: Elenco degli adiacenze (questo articolo)
• Parte 1.2: Tabella di chiusura
• Parte 1.3: Percorso materializzato
• Parte 1.4: Set nidificati
• Parte 1.5: Albero