L'estensione dell'albero di PostgreSQL offre percorsi materializzati con superpoteri nativi del database: indici GiST, operatori specializzati come @> e <@Se sei impegnato a PostgreSQL e vuoi le migliori prestazioni di query gerarchiche, ltree è difficile da battere.

Buone notizie: La Npgsql EF Core provider supporta le traduzioni LINQ per le operazioni ltree attraverso il LTree tipo. È possibile utilizzare metodi come IsAncestorOf(), IsDescendantOf(), e MatchesLQuery() Tuttavia, EF Core non supporta ancora i CTE ricorsivi, quindi avrai bisogno di SQL raw per le operazioni che li richiedono (come costruire risultati completi di sotto-albero con profondità calcolate).

Grazie a Shay RojanskyCity name (optional, probably does not need a translation) per indicare il supporto di traduzione LINQ!

Navigazione serie

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

---

Che cos'è ltree?

ltree è un'estensione PostgreSQL che fornisce un tipo di dati nativo per i percorsi gerarchici delle etichette. Percorso materializzato con superpoteri - il database comprende la struttura e fornisce operatori ottimizzati, funzioni e supporto all'indice GiST.

Invece di trattare il percorso come una stringa stupida e usando query LIKE, PostgreSQL può:

• Utilizzare operatori specializzati (@> per "è antenato di," <@ per "è discendente di")
• Applica gli indici GiST per le query gerarchiche efficienti
• Corrispondere i modelli con i caratteri jolly (Top.*.Europe)
• Esegui operazioni impostate sui percorsi

Intuizione chiave: ltree è il migliore di entrambi i mondi - la semplicità di percorsi materializzati con ottimizzazione database-native. Il trade-off è PostgreSQL lock-in, e mentre molte operazioni ltree funzionano tramite LINQ, CTE ricorsive richiedono ancora raw SQL.

Formato percorso ltree

Percorsi in albero usano periodi come separatori ed etichette alfanumeriche:

Top.Countries.Europe.UK
Top.Countries.Asia.Japan.Tokyo
Top.Products.Electronics.Computers.Laptops

Regole:

• Le etichette possono contenere lettere, cifre e sottolineature
• Le etichette sono sensibili al caso
• La lunghezza massima dell'etichetta è di 256 caratteri
• La lunghezza massima del percorso è di 65535 etichette

Per i sistemi di commento, useremmo gli ID come etichette: 1.3.7 che significa "commento 7 sotto il commento 3 sotto il commento 1" .

Impostazione dell'albero

In primo luogo, abilitare l'estensione (richiede privilegi superutente database):

CREATE EXTENSION IF NOT EXISTS ltree;

O attraverso la migrazione EF Core:

protected override void Up(MigrationBuilder migrationBuilder)
{
    migrationBuilder.Sql("CREATE EXTENSION IF NOT EXISTS ltree");
}

Definizione dell'entità

Il provider Npgsql include un LTree tipo che mappa direttamente l'albero di PostgreSQL e fornisce metodi traslabili LINQ:

using Microsoft.EntityFrameworkCore;

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

    // ========== LTREE PATH ==========

    // The hierarchical path in ltree format
    // Format: ancestor1.ancestor2.thisNode
    // Examples:
    //   Root comment: "1"
    //   Child of 1: "1.5"
    //   Grandchild: "1.5.12"
    //
    // Using the LTree type enables LINQ translations for ltree operators
    public LTree Path { get; set; }

    // Keep ParentCommentId for convenience
    public int? ParentCommentId { get; set; }
    public Comment? ParentComment { get; set; }
    public ICollection<Comment> Children { get; set; } = new List<Comment>();

    // ========== HELPER METHODS ==========

    // Helper to get depth - LTree has NLevel property for this
    public int GetDepth() => Path.NLevel - 1;

    public IEnumerable<int> GetAncestorIds()
    {
        var pathString = Path.ToString();
        if (string.IsNullOrEmpty(pathString)) yield break;

        var parts = pathString.Split('.');
        // All except last (which is this node)
        for (int i = 0; i < parts.Length - 1; i++)
        {
            if (int.TryParse(parts[i], out var id))
                yield return id;
        }
    }
}

Configurazione del nucleo EF

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

        // ========== PATH COLUMN ==========
        // The LTree type is automatically mapped to PostgreSQL's ltree type
        // by the Npgsql provider - no explicit column type needed
        builder.Property(c => c.Path)
            .IsRequired();

        // Relationship to blog post
        builder.HasOne(c => c.Post)
            .WithMany(p => p.Comments)
            .HasForeignKey(c => c.PostId)
            .OnDelete(DeleteBehavior.Cascade);

        // Self-referencing
        builder.HasOne(c => c.ParentComment)
            .WithMany(c => c.Children)
            .HasForeignKey(c => c.ParentCommentId)
            .OnDelete(DeleteBehavior.Restrict);

        // Standard indexes
        builder.HasIndex(c => c.PostId);
        builder.HasIndex(c => c.ParentCommentId);
    }
}

Aggiungere l'indice GiST attraverso la migrazione:

protected override void Up(MigrationBuilder migrationBuilder)
{
    // GiST index for ltree - enables efficient @>, <@, and ~ operators
    migrationBuilder.Sql(
        "CREATE INDEX ix_comments_path_gist ON comments USING GIST (path)");

    // Alternative: B-tree index for exact match and sorting
    // migrationBuilder.Sql(
    //     "CREATE INDEX ix_comments_path_btree ON comments USING BTREE (path)");
}

Operatori

ltree fornisce operatori potenti. Il provider Npgsql EF Core traduce LTree metodi per tali operatori:

Operatore	Significato	Metodo LINQ	Esempio SQL
@>	È antenato di (contiene)	ltree1.IsAncestorOf(ltree2)	'1.3'::ltree @> '1.3.7'::ltree → true
<@	È discendente di (contenuto da)	ltree1.IsDescendantOf(ltree2)	'1.3.7'::ltree <@ '1.3'::ltree → true
~	Matches lquery pattern	ltree.MatchesLQuery(pattern)	'1.3.7'::ltree ~ '1.*'::lquery → true
@	Matches ltxtquery	ltree.MatchesLTxtQuery(query)	'1.3.7'::ltree @ '3 & 7'::ltxtquery → true
||	Percorsi concatenati	(usare concatenazione stringa)	'1.3'::ltree || '7'::ltree → '1.3.7'
<, >, <=, >=	Confronto	Operatori standard	Per selezione

Ulteriori proprietà e metodi traducibili LINQ:

• ltree.NLevel → nlevel(ltree) - numero di etichette nel percorso
• ltree.Subtree(start, end) → subltree(ltree, start, end) - gamma di etichette di estrazione
• ltree.Subpath(offset) → subpath(ltree, offset) - suffisso da offset
• ltree.Subpath(offset, len) → subpath(ltree, offset, len) - sottostringa
• ltree.Index(subpath) → index(ltree, subpath) - trovare la posizione del sottopath
• LTree.LongestCommonAncestor(ltree1, ltree2) → lca(ltree1, ltree2) - antenato comune più basso

Operazioni

Inserisci un nuovo commento

public async Task<Comment> AddCommentAsync(
    int postId,
    int? parentId,
    string author,
    string content,
    CancellationToken ct = default)
{
    string path;

    if (parentId.HasValue)
    {
        // Get parent's path
        var parentPath = await context.Comments
            .Where(c => c.Id == parentId.Value)
            .Select(c => c.Path)
            .FirstOrDefaultAsync(ct);

        if (parentPath == null)
            throw new InvalidOperationException($"Parent comment {parentId} not found");

        // Create comment first to get the ID
        var comment = new Comment
        {
            PostId = postId,
            ParentCommentId = parentId,
            Author = author,
            Content = content,
            CreatedAt = DateTime.UtcNow,
            Path = string.Empty  // Temporary
        };

        context.Comments.Add(comment);
        await context.SaveChangesAsync(ct);

        // Build path: parentPath.newId
        // ltree uses periods as separators
        comment.Path = $"{parentPath}.{comment.Id}";
        await context.SaveChangesAsync(ct);

        logger.LogInformation("Added comment {CommentId} with ltree path {Path}",
            comment.Id, comment.Path);
        return comment;
    }
    else
    {
        // Root comment - path is just the ID
        var comment = new Comment
        {
            PostId = postId,
            ParentCommentId = null,
            Author = author,
            Content = content,
            CreatedAt = DateTime.UtcNow,
            Path = string.Empty
        };

        context.Comments.Add(comment);
        await context.SaveChangesAsync(ct);

        comment.Path = comment.Id.ToString();
        await context.SaveChangesAsync(ct);

        return comment;
    }
}

Ottieni bambini immediati

Utilizzando ParentCommentId (semplice) o ltree pattern corrispondenti:

public async Task<List<Comment>> GetChildrenAsync(int commentId, CancellationToken ct = default)
{
    // Option 1: Simple ParentCommentId lookup
    return await context.Comments
        .AsNoTracking()
        .Where(c => c.ParentCommentId == commentId)
        .OrderBy(c => c.CreatedAt)
        .ToListAsync(ct);
}

// Option 2: Using ltree pattern (demonstration)
public async Task<List<Comment>> GetChildrenLtreeAsync(int commentId, CancellationToken ct = default)
{
    // Get parent path first
    var parentPath = await context.Comments
        .Where(c => c.Id == commentId)
        .Select(c => c.Path)
        .FirstOrDefaultAsync(ct);

    if (parentPath == null)
        return new List<Comment>();

    // Children match pattern: parentPath.*{1}
    // The {1} means exactly one more label (immediate children only)
    var sql = @"
        SELECT * FROM comments
        WHERE path ~ ($1 || '.*{1}')::lquery
        ORDER BY created_at";

    return await context.Comments
        .FromSqlRaw(sql, parentPath)
        .AsNoTracking()
        .ToListAsync(ct);
}

Ottieni tutti gli antenati

Utilizzando LINQ con il IsAncestorOf metodo (traduci a @> operatore):

public async Task<List<Comment>> GetAncestorsAsync(int commentId, CancellationToken ct = default)
{
    var targetPath = await context.Comments
        .Where(c => c.Id == commentId)
        .Select(c => c.Path)
        .FirstOrDefaultAsync(ct);

    if (targetPath == default)
        return new List<Comment>();

    // Find all nodes whose path is an ancestor of this path
    // Using IsAncestorOf which translates to @> operator
    return await context.Comments
        .AsNoTracking()
        .Where(c => c.Path.IsAncestorOf(targetPath) && c.Id != commentId)
        .OrderBy(c => c.Path.NLevel)
        .ToListAsync(ct);
}

Ottieni tutti i discendenti

Utilizzando LINQ con il IsDescendantOf metodo (traduci a <@ operatore):

public async Task<List<Comment>> GetDescendantsAsync(int commentId, CancellationToken ct = default)
{
    var parentPath = await context.Comments
        .Where(c => c.Id == commentId)
        .Select(c => c.Path)
        .FirstOrDefaultAsync(ct);

    if (parentPath == default)
        return new List<Comment>();

    // Find all nodes whose path is a descendant of this path
    // Using IsDescendantOf which translates to <@ operator
    return await context.Comments
        .AsNoTracking()
        .Where(c => c.Path.IsDescendantOf(parentPath) && c.Id != commentId)
        .OrderBy(c => c.Path)
        .ToListAsync(ct);
}

Ottieni discendenti alla profondità massima

Uso di LINQ con NLevel per la limitazione della profondità:

public async Task<List<Comment>> GetDescendantsToDepthAsync(
    int commentId,
    int maxDepth,
    CancellationToken ct = default)
{
    var comment = await context.Comments
        .FirstOrDefaultAsync(c => c.Id == commentId, ct);

    if (comment == null)
        return new List<Comment>();

    var basePath = comment.Path;
    var baseLevel = comment.Path.NLevel;

    // NLevel property translates to nlevel() function
    // Filter descendants within maxDepth levels
    return await context.Comments
        .AsNoTracking()
        .Where(c => c.Path.IsDescendantOf(basePath) 
                 && c.Id != commentId
                 && c.Path.NLevel - baseLevel <= maxDepth)
        .OrderBy(c => c.Path)
        .ToListAsync(ct);
}

// If you need the depth value in results, you can project it:
public async Task<List<CommentWithDepth>> GetDescendantsWithDepthAsync(
    int commentId,
    int maxDepth,
    CancellationToken ct = default)
{
    var comment = await context.Comments
        .FirstOrDefaultAsync(c => c.Id == commentId, ct);

    if (comment == null)
        return new List<CommentWithDepth>();

    var basePath = comment.Path;
    var baseLevel = comment.Path.NLevel;

    return await context.Comments
        .AsNoTracking()
        .Where(c => c.Path.IsDescendantOf(basePath) 
                 && c.Id != commentId
                 && c.Path.NLevel - baseLevel <= maxDepth)
        .OrderBy(c => c.Path)
        .Select(c => new CommentWithDepth
        {
            Id = c.Id,
            Content = c.Content,
            Author = c.Author,
            CreatedAt = c.CreatedAt,
            PostId = c.PostId,
            ParentCommentId = c.ParentCommentId,
            Path = c.Path.ToString(),
            Depth = c.Path.NLevel - baseLevel
        })
        .ToListAsync(ct);
}

Interviste corrispondenti al modello

ltree supporta potenti modelli di lquery. MatchesLQuery in LINQ:

// Find all comments at exactly depth 2 under comment 1
public async Task<List<Comment>> GetAtDepthAsync(int commentId, int depth, CancellationToken ct = default)
{
    var path = await context.Comments
        .Where(c => c.Id == commentId)
        .Select(c => c.Path)
        .FirstOrDefaultAsync(ct);

    if (path == default) return new List<Comment>();

    // Pattern: path.*{depth} matches exactly 'depth' more levels
    var pattern = $"{path}.*{{{depth}}}";
    
    return await context.Comments
        .AsNoTracking()
        .Where(c => c.Path.MatchesLQuery(pattern))
        .OrderBy(c => c.Path)
        .ToListAsync(ct);
}

// Find all paths matching a pattern like "1.*.7" (any path through 1 ending in 7)
public async Task<List<Comment>> MatchPatternAsync(string pattern, CancellationToken ct = default)
{
    // MatchesLQuery translates to the ~ operator
    return await context.Comments
        .AsNoTracking()
        .Where(c => c.Path.MatchesLQuery(pattern))
        .OrderBy(c => c.Path)
        .ToListAsync(ct);
}

Elimina un sottoalbero

È possibile utilizzare LINQ per selezionare il sottoalbero, quindi eliminare:

public async Task DeleteSubtreeAsync(int commentId, CancellationToken ct = default)
{
    var path = await context.Comments
        .Where(c => c.Id == commentId)
        .Select(c => c.Path)
        .FirstOrDefaultAsync(ct);

    if (path == default)
        throw new InvalidOperationException($"Comment {commentId} not found");

    // Delete all descendants (nodes where path is descendant of this path)
    // Note: ExecuteDeleteAsync requires EF Core 7+
    var deleted = await context.Comments
        .Where(c => c.Path.IsDescendantOf(path))
        .ExecuteDeleteAsync(ct);

    logger.LogInformation("Deleted {Count} comments with path prefix {Path}", deleted, path);
}

Sposta un sottoalbero

ltree fornisce funzioni per aiutare con la manipolazione del percorso:

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 cycles
        if (newParent.Path.StartsWith(node.Path))
            throw new InvalidOperationException("Cannot move under own descendant");

        var oldPath = node.Path;
        var newPath = $"{newParent.Path}.{node.Id}";

        // Update all descendants: replace old path prefix with new one
        // subpath(path, nlevel(oldPath)) gets the suffix after oldPath
        // We concatenate newPath with that suffix
        var sql = @"
            UPDATE comments
            SET path = $2::ltree || subpath(path, nlevel($1::ltree))
            WHERE path <@ $1::ltree";

        await context.Database.ExecuteSqlRawAsync(
            sql,
            new object[] { oldPath, newPath },
            ct);

        // Update parent reference
        node.ParentCommentId = newParentId;
        await context.SaveChangesAsync(ct);

        await transaction.CommitAsync(ct);

        logger.LogInformation("Moved subtree from {OldPath} to {NewPath}", oldPath, newPath);
    }
    catch
    {
        await transaction.RollbackAsync(ct);
        throw;
    }
}

Riferimento funzioni ltree

PostgreSQL offre molte utili funzioni ltree:

Function	Description	Example
nlevel(ltree)	Numero di etichette	nlevel('1.3.7') → 3
subpath(ltree, offset)	Suffisso da offset	subpath('1.3.7', 1) → '3.7'
subpath(ltree, offset, len)	Sottostringa	subpath('1.3.7', 1, 1) → '3'
subltree(ltree, start, end)	Gamma di etichette	subltree('1.3.7', 0, 2) → '1.3'
lca(ltree, ltree)	Antenato comune più basso	lca('1.3.7', '1.3.9') → '1.3'
text2ltree(text)	Converti testo in ltree	text2ltree('1.3.7')
ltree2text(ltree)	Convertire albero in testo	ltree2text('1.3.7'::ltree)

Visualizzazione del flusso di interrogazione

sequenceDiagram
    participant App as Application
    participant EF as EF Core
    participant PG as PostgreSQL + ltree

    Note over App,PG: Getting Descendants (GiST index)
    App->>EF: GetDescendantsAsync(commentId)
    EF->>PG: SELECT path FROM comments WHERE id = @id
    PG-->>EF: Path "1.3"
    EF->>PG: SELECT * FROM comments WHERE path <@ '1.3'::ltree
    Note over PG: Uses GiST index - O(log n)
    PG-->>EF: All descendants
    EF-->>App: List<Comment>

    Note over App,PG: Pattern Match Query
    App->>EF: MatchPatternAsync("1.*.7")
    EF->>PG: SELECT * FROM comments WHERE path ~ '1.*.7'::lquery
    Note over PG: GiST index supports pattern matching
    PG-->>EF: Matching comments
    EF-->>App: List<Comment>

Caratteristiche di prestazione

Funzionamento	Complessità	Note
Inserire	O(1)	Impostare semplicemente la stringa del percorso
Ottieni figli	O(1)	Corrispondenza schema con indice GiST
Ottieni antenati	O(1)	@> operatore con indice GiST
Ottieni discendenti	O(1)	<@ operatore con indice GiST
Corrispondenza schema	O(log n)	L'indice GiST supporta lquery
Move subtree	O(s)	Update s discendent paths
Elimina sottoalbero	O(1)	<@ operatore per la selezione

Con gli indici GiST, le query dell'albero sono estremamente efficienti - tipicamente O(log n) indipendentemente dalla profondità dell'albero.

Pro e contro

Pros	Cons
Ottimizzazione nativa del database	Solo PostgreSQL
Indice GiST per tutte le query gerarchiche	Dipendenza estensione
Potente corrispondenza del modello	Etichette limitate all'alfabeto
Funzioni di manipolazione del percorso incorporato	Le CTE ricorsive richiedono SQL grezzo
O(1) query antenati/discendenti	Soluzioni EF Core meno portatili di quelle pure
Stoccaggio compatto
Supporto LINQ tramite Npgsql LTree tipo

Quando usare ltree

Scegli ltree quando:

• Sei impegnato con PostgreSQL
• Le prestazioni sono critiche per le query gerarchiche
• Hai bisogno di uno schema corrispondente (trova tutto X.*.Y sentieri)
• Vuoi il meglio dei percorsi materializzati
• Vuoi il supporto LINQ per la maggior parte delle operazioni gerarchiche

Evitare ltree quando:

• È necessaria la portabilità del database (SQL Server, MySQL, ecc.)
• Il tuo team non ha familiarità con le estensioni PostgreSQL
• Le etichette hanno bisogno di caratteri non alfanumerici
• Hai bisogno di CTE ricorsive e vuoi evitare qualsiasi SQL grezzo

Confronto con il percorso materializzato

Aspetto	Percorso materializzato	albero
Tipo di indice	Albero B (solo prefisso)	GiST (tutti i modelli)
Corrispondenza schema	Solo 'prefisso%' LIKE	Carte jolly complete
Operatori	Confronto stringa	Nativo @>, <@, ~
Portabilità	Qualsiasi banca dati	Solo PostgreSQL
Supporto del nucleo dell'impronta ambientale	LINQ completo	LINQ via LTree tipo (CTE hanno bisogno di SQL grezzo)
Performance	Good with index	Excellent with GiST
Funzioni	Nessuno (analisi manuale)	Ricca libreria di funzioni

Esempio: interrogazione completa dell'albero di commento

Mettere tutto insieme - ottenere un intero albero di commento con profondità per un post sul blog:

public async Task<List<CommentTreeItem>> GetPostCommentTreeAsync(
    int postId,
    int maxDepth = 5,
    CancellationToken ct = default)
{
    // Get all comments for the post with calculated depth
    // nlevel() counts the labels in the path
    var sql = @"
        WITH root_comments AS (
            -- Find root comments for this post (no dot in path = root)
            SELECT path, nlevel(path) as root_level
            FROM comments
            WHERE post_id = $1 AND path !~ '*.*'
        )
        SELECT
            c.id,
            c.content,
            c.author,
            c.created_at,
            c.post_id,
            c.parent_comment_id,
            c.path::text as path,
            nlevel(c.path) - COALESCE(
                (SELECT root_level FROM root_comments r
                 WHERE c.path <@ r.path
                 ORDER BY nlevel(r.path) DESC LIMIT 1),
                nlevel(c.path)
            ) as depth
        FROM comments c
        WHERE c.post_id = $1
          AND nlevel(c.path) <= $2 + 1  -- +1 because depth is 0-indexed
        ORDER BY c.path";  -- Perfect depth-first order!

    return await context.Database
        .SqlQueryRaw<CommentTreeItem>(sql, postId, maxDepth)
        .ToListAsync(ct);
}

public class CommentTreeItem
{
    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 string Path { get; set; } = string.Empty;
    public int Depth { get; set; }
}

Navigazione serie

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

Cosa c'e' dopo?

Questa serie ha coperto cinque approcci ai dati gerarchici utilizzando EF Core. Parte 2 esplorerà utilizzando raw SQL e Dapper per un controllo ancora più sulle query gerarchiche - in arrivo!