Back to "Hiérarchies de données Partie 1.3: Voie materialisée avec le noyau EF"

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

EF Hierarchies Entity Framework PostgreSQL

Hiérarchies de données Partie 1.3: Voie materialisée avec le noyau EF

Saturday, 06 December 2025

Les chemins matérialisés contiennent l'ancestration complète en tant que chaîne délimitée - comme /1/3/7/ - rendant les ancêtres instantanément lisibles sans aucun raccordement . parfaite pour la génération de pâte à pain et l’humain

Qu’est-ce qu’un chemin matérialisé?

Le modèle de cheminement matérialisé ( est également appelé "Enumeration du cheminement" dans Joe Celko's Trees and Hierarchies) stocke l'ascendance complète de chaque node en tant que chaîne délimitée - comme un chemin de fichier ou une adresse postaleM SK2 Au lieu d'entreposer seulement SSK3 mon parent est le node 5", nous entreposons S"I am reached via nodes USK6 WSK7 \USK8 \WSK9 |USK10 |WSK11 | USK12 directement dans la ligne USK13

Pensez à cela comme à stocker l'URL complète au lieu de simplement le nom de la page. Le chemin /blog/posts/2024/my-article vous indique exactement où vous êtes dans la hiérarchie.

Perspectives clés: Nous're complexité des demandes de transaction pour la redundance d'entreposage . L'ancêtre est dénormalisé dans chaque rangée

Le concept visualisé

flowchart TD
    subgraph "Comment Tree"
        C1["Comment 1<br/>Path: /1/"]
        C2["Comment 2<br/>Path: /1/2/"]
        C3["Comment 3<br/>Path: /1/3/"]
        C4["Comment 4<br/>Path: /1/3/4/"]
    end

    C1 --> C2
    C1 --> C3
    C3 --> C4

    subgraph "What the paths tell us"
        P1["Comment 4's path /1/3/4/ means:<br/>• Ancestors are 1, 3 (parse the path)<br/>• Depth is 3 (count separators - 1)<br/>• Root is 1 (first element)"]
    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

Le chemin est auto-descrivant:

  • Lire les ancêtres: Tracer /1/3/4/ → Les ancêtres sont [1, 3, 4]
  • Trouver des descendants: Demande de renseignements WHERE path LIKE '/1/3/%' → reçoit tout sous un node 3
  • Calcul de la profondeur: Comptez les séparateurs moins un
  • Trouver des frères et sœurs: Demande de renseignements WHERE path LIKE '/1/3/_/' (enfants immédiats de 3)

Définition de l'entité

L'entité ajoute une seule colonne du chemin:

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

    // ========== MATERIALISED PATH ==========

    // The complete path from root to this node
    // Format: /ancestor1/ancestor2/.../thisNode/
    // Examples:
    //   Root comment: "/1/"
    //   Child of 1: "/1/5/"
    //   Grandchild: "/1/5/12/"
    //
    // The leading and trailing slashes make pattern matching easier:
    // - LIKE '/1/%' finds all descendants of 1 (includes /1/ itself)
    // - LIKE '/1/5/%' finds all descendants of 5 under 1
    public string Path { get; set; } = string.Empty;

    // We still keep ParentCommentId for:
    // 1. Quick "who is my parent" without parsing
    // 2. EF Core navigation properties
    // 3. Data integrity (can validate path matches parent relationship)
    public int? ParentCommentId { get; set; }
    public Comment? ParentComment { get; set; }
    public ICollection<Comment> Children { get; set; } = new List<Comment>();

    // ========== COMPUTED HELPERS ==========

    // Parse ancestors from path - not stored, computed on demand
    public IEnumerable<int> GetAncestorIds()
    {
        if (string.IsNullOrEmpty(Path)) yield break;

        // Split "/1/3/4/" into ["", "1", "3", "4", ""]
        var parts = Path.Split('/', StringSplitOptions.RemoveEmptyEntries);

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

    // Calculate depth from path
    public int GetDepth()
    {
        if (string.IsNullOrEmpty(Path)) return 0;
        // Count segments: "/1/3/4/" has 3 segments, depth is 2 (0-indexed from root)
        return Path.Split('/', StringSplitOptions.RemoveEmptyEntries).Length - 1;
    }
}

Configuration de l'EF Core

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 ==========
        // Set a reasonable max length - this limits your tree depth
        // /1/12345/12346/12347/...
        // Each segment is up to ~7 chars (ID + slash), so 1000 chars ≈ 140 levels
        builder.Property(c => c.Path)
            .IsRequired()
            .HasMaxLength(1000);

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

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

        // ========== INDEXES ==========

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

        // PATH INDEX - Critical for performance!
        // This makes LIKE 'prefix%' queries efficient
        // PostgreSQL can use a B-tree index for prefix LIKE patterns
        // (but NOT for '%suffix' or '%contains%' patterns)
        builder.HasIndex(c => c.Path);

        // For PostgreSQL, a text_pattern_ops index is even better for LIKE:
        // CREATE INDEX ix_comments_path ON comments (path text_pattern_ops);
        // You may want to add this via a raw migration
    }
}

Système de base de données

erDiagram
    COMMENT {
        int id PK
        string content
        string author
        datetime created_at
        int post_id FK
        int parent_comment_id FK "optional"
        string path "e.g. /1/3/7/"
    }

    BLOG_POST {
        int id PK
        string title
        string content
    }

    BLOG_POST ||--o{ COMMENT : "has"
    COMMENT ||--o{ COMMENT : "parent-child"

Opérations

Insérer un nouveau commentaire

Inserting requires building the path from the parent's path:

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 to extend it
        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");
        }

        // We need the ID first, so we'll update the path after saving
        // (Chicken-and-egg: path contains our ID, but we don't have ID until saved)

        var comment = new Comment
        {
            PostId = postId,
            ParentCommentId = parentId,
            Author = author,
            Content = content,
            CreatedAt = DateTime.UtcNow,
            Path = string.Empty  // Temporary - will update after save
        };

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

        // Now we have the ID - build the real path
        // Parent path "/1/3/" + our ID "7" = "/1/3/7/"
        comment.Path = $"{parentPath}{comment.Id}/";
        await context.SaveChangesAsync(ct);

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

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

        comment.Path = $"/{comment.Id}/";
        await context.SaveChangesAsync(ct);

        logger.LogInformation("Added root comment {CommentId} with path {Path}", comment.Id, comment.Path);
        return comment;
    }
}

Obtenir des enfants immédiats

Utilisation du parent- relation avec l’enfant M SK1 nous avons gardé le parentCommentId pour convenience):

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

    // Option 2: Use path pattern (demonstrates path power)
    // var parentPath = await context.Comments
    //     .Where(c => c.Id == commentId)
    //     .Select(c => c.Path)
    //     .FirstOrDefaultAsync(ct);
    //
    // if (parentPath == null) return new List<Comment>();
    //
    // // Find paths that extend parent by exactly one segment
    // // Parent: /1/3/  Children: /1/3/X/ where X is one number
    // var childPathPattern = $"{parentPath}%";
    //
    // return await context.Comments
    //     .AsNoTracking()
    //     .Where(c => EF.Functions.Like(c.Path, childPathPattern)
    //              && c.Path != parentPath
    //              && c.ParentCommentId == commentId)  // Ensures immediate children only
    //     .ToListAsync(ct);
}

Obtenir tous les ancêtres

C'est là où les chemins matérialisés brillent - analyser le chemin, aucune recherche de base de données n'est requiseM SK2

public async Task<List<Comment>> GetAncestorsAsync(int commentId, CancellationToken ct = default)
{
    // Step 1: Get the path (single query)
    var path = await context.Comments
        .Where(c => c.Id == commentId)
        .Select(c => c.Path)
        .FirstOrDefaultAsync(ct);

    if (string.IsNullOrEmpty(path))
        return new List<Comment>();

    // Step 2: Parse ancestor IDs from path
    // Path "/1/3/7/" -> split -> ["1", "3", "7"] -> take all but last -> [1, 3]
    var ancestorIds = path
        .Split('/', StringSplitOptions.RemoveEmptyEntries)
        .SkipLast(1)  // Exclude self
        .Select(int.Parse)
        .ToList();

    if (!ancestorIds.Any())
        return new List<Comment>();

    // Step 3: Fetch ancestors (single query, uses primary key index)
    var ancestors = await context.Comments
        .AsNoTracking()
        .Where(c => ancestorIds.Contains(c.Id))
        .ToListAsync(ct);

    // Step 4: Order by position in path (root first)
    return ancestorIds
        .Select(id => ancestors.First(a => a.Id == id))
        .ToList();
}

Obtenir tous les descendants

Utiliser LIKE avec le préfixe path:

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

    if (string.IsNullOrEmpty(path))
        return new List<Comment>();

    // LIKE 'path%' finds all paths that START with this path
    // Path "/1/3/" matches "/1/3/", "/1/3/5/", "/1/3/5/9/", etc.
    // Using EF.Functions.Like for proper SQL generation
    return await context.Comments
        .AsNoTracking()
        .Where(c => EF.Functions.Like(c.Path, $"{path}%") && c.Id != commentId)
        .OrderBy(c => c.Path)  // Gives us depth-first order!
        .ToListAsync(ct);
}

Obtenir des descendants avec une profondeur

Nous pouvons calculer la profondeur à partir du chemin:

public async Task<List<CommentWithDepth>> GetDescendantsWithDepthAsync(
    int commentId,
    int? maxDepth = null,
    CancellationToken ct = default)
{
    var comment = await context.Comments
        .AsNoTracking()
        .FirstOrDefaultAsync(c => c.Id == commentId, ct);

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

    var basePath = comment.Path;
    var baseDepth = basePath.Split('/', StringSplitOptions.RemoveEmptyEntries).Length;

    // Get all descendants
    var query = context.Comments
        .AsNoTracking()
        .Where(c => EF.Functions.Like(c.Path, $"{basePath}%") && c.Id != commentId);

    var descendants = await query.ToListAsync(ct);

    // Calculate relative depth and filter if needed
    var result = descendants
        .Select(d =>
        {
            var absoluteDepth = d.Path.Split('/', StringSplitOptions.RemoveEmptyEntries).Length;
            var relativeDepth = absoluteDepth - baseDepth;
            return new CommentWithDepth
            {
                Id = d.Id,
                Content = d.Content,
                Author = d.Author,
                CreatedAt = d.CreatedAt,
                PostId = d.PostId,
                ParentCommentId = d.ParentCommentId,
                Path = d.Path,
                Depth = relativeDepth
            };
        })
        .Where(d => !maxDepth.HasValue || d.Depth <= maxDepth.Value)
        .OrderBy(d => d.Path)
        .ToList();

    return result;
}

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

Supprimer un sous-arbre

Simple avec la correspondance de chemins:

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 (string.IsNullOrEmpty(path))
    {
        throw new InvalidOperationException($"Comment {commentId} not found");
    }

    // Delete all comments whose path starts with this path
    // This includes the comment itself and ALL descendants
    var deleted = await context.Comments
        .Where(c => EF.Functions.Like(c.Path, $"{path}%"))
        .ExecuteDeleteAsync(ct);

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

Déplacer un sous-arbre

Il s’agit de l’opération coûteuse pour les voies matérialisées - nous devons mettre à jour TOUS les voiles descendantes :

public async Task MoveSubtreeAsync(
    int commentId,
    int newParentId,
    CancellationToken ct = default)
{
    await using var transaction = await context.Database.BeginTransactionAsync(ct);

    try
    {
        // Get the node being moved
        var comment = await context.Comments
            .FirstOrDefaultAsync(c => c.Id == commentId, ct);

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

        // Get the new parent
        var newParent = await context.Comments
            .FirstOrDefaultAsync(c => c.Id == newParentId, ct);

        if (newParent == null)
            throw new InvalidOperationException($"New parent {newParentId} not found");

        // Prevent cycles: can't move under own descendant
        if (newParent.Path.StartsWith(comment.Path))
        {
            throw new InvalidOperationException("Cannot move a node under its own descendant");
        }

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

        // Get all descendants (including the node itself)
        var descendants = await context.Comments
            .Where(c => EF.Functions.Like(c.Path, $"{oldPath}%"))
            .ToListAsync(ct);

        // Update all paths by replacing the old prefix with the new one
        foreach (var descendant in descendants)
        {
            // Replace old path prefix with new one
            // Old: /1/3/7/  Node 7 moving under /2/
            // Node 7: /1/3/7/ -> /2/7/
            // Node 9 (child of 7): /1/3/7/9/ -> /2/7/9/
            descendant.Path = newPath + descendant.Path.Substring(oldPath.Length);
        }

        // Update the direct parent reference
        comment.ParentCommentId = newParentId;

        await context.SaveChangesAsync(ct);
        await transaction.CommitAsync(ct);

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

Visualisation du flux de demandes

sequenceDiagram
    participant App as Application
    participant EF as EF Core
    participant DB as PostgreSQL

    Note over App,DB: Getting Ancestors (Path parsing)
    App->>EF: GetAncestorsAsync(commentId)
    EF->>DB: SELECT path FROM comments WHERE id = @id
    DB-->>EF: Path "/1/3/7/"
    Note over App: Parse path → [1, 3]
    EF->>DB: SELECT * FROM comments WHERE id IN (1, 3)
    DB-->>EF: Ancestor comments
    EF-->>App: List<Comment>

    Note over App,DB: Getting Descendants (LIKE query)
    App->>EF: GetDescendantsAsync(commentId)
    EF->>DB: SELECT path FROM comments WHERE id = @id
    DB-->>EF: Path "/1/3/"
    EF->>DB: SELECT * FROM comments WHERE path LIKE '/1/3/%'
    DB-->>EF: All descendants
    EF-->>App: List<Comment>

Caractéristiques du rendement

Exploitation Complexité Demandes de base de données Notes SMK4
Insérer
Obtenir des enfants O(1) 4 5 Utiliser l'index ParentCommentId 6
Obtenir les ancêtres OM SK2d \2
Obtenir des descendants OM SK2*
Déplacer l'arbre de sous-treivre OM SK2s MSC4 5 6 Mise à jour des voies descendantes s
Supprimer l'arbre de sous-tree OM SK2*

*Avec un index approprié sur la colonne du chemin

Considérations relatives à l'index

L’indice de chemin est critique. Pour PostgreSQL, envisagez d’utiliser text_pattern_ops, qui permet d'effectuer des recherches de préfixe LIKE efficaces dans les localités non -C:

-- Standard B-tree index (works for LIKE 'prefix%')
CREATE INDEX ix_comments_path ON comments (path);

-- Better for pattern matching in PostgreSQL
CREATE INDEX ix_comments_path_pattern ON comments (path text_pattern_ops);

Ajouter ce message via une migration:

protected override void Up(MigrationBuilder migrationBuilder)
{
    migrationBuilder.Sql(
        "CREATE INDEX ix_comments_path_pattern ON comments (path text_pattern_ops)");
}

Considérations relatives au format de la voie

Différents délimiteurs ont des échanges-offs :

Format Exemple MSC2 Avantages MSC3 Cons SMC4
/1/3/7/ Cet article
1.3.7 Style de l'arbre PostgreSQL Compact
1,3,7 CommaM SK1 séparés simples Les commas dans les données peuvent causer des problèmes
001.003.007 FixeM SK1 largeur Sortable, cohérente

L'article 5 de la Loi sur l'immigration et le statut des réfugiés /id/ Il est recommandé de recourir à un format comportant des plis avant et arrière, car:

  1. Les modèles LIKE fonctionnent correctement (/1/% Les matches /1/ mais pas /10/)
  2. Facile à diviser et à analyser
  3. Human-readable for debugging

Pros et Cons

Faits positifs Cons
Ancêtres disponibles en analysant (pas de demandeM SK2 SSK3 Le déplacement des sous-arbres nécessite la mise à jour de tous les descendants
Descendants à l'aide d'une simple demande LIKE Longueur du chemin limite la profondeur de l'arbre
Dépth calculable à partir du chemin La manipulation des chaînes est superposée
Homme-readable for debugging Les demandes LIKE peuvent être lentes sans index approprié
Good for breadcrumb generation Path must be kept in sync with ParentCommentId
Ajout d'une seule colonne Peut' ne pas utiliser la norme BM SK3arbre pour le suffix correspondant

Quand utiliser le chemin matérialisé

Choisissez le chemin matérialisé lorsque:

  • Les crustacés sont une exigence courante
  • Les ancêtres sont recherchés plus souvent que les descendants
  • La profondeur de l’arbre est limitée (vous gagnezM SK1il n’y a pas d’arbres de niveau 100+
  • Le déplacement des sous-arbres est rare
  • Vous voulez des données hiérarchiques lisibles humaines- pour le débugging

Évitez la voie matérielle lorsque:

  • Vous déplacez fréquemment des sous-arbres (la mise à jour de tous les chemins est coûteuse)
  • Les arbres peuvent être très profonds.
  • Vous avez besoin d'une combinaison efficace des suffixes (détermination de tous les arbres se terminant dans un modèle)
  • Vous'êtes plus à l'aise avec ltree (PostgreSQL-spécifique mais plus optimiséeM SK3

Comparaison avec ltree

Si vous êtes sur PostgreSQL', envisagez Partie 1.5: ltree plutôt. ltree est essentiellement une base de donnéesM SK1native, avec un chemin materialisé optimisé MSC3

  • Soutien de l'indice GiST pour les demandes efficaces
  • Composés -inopérateurs (@>, <@, ~, etcM SK1
  • Fonctions de manipulation des voies
  • Modèle correspondant aux cartes vives

Le trade-off est PostgreSQL lock-inM SK2 Notez que le Le fournisseur de Npgsql appuie maintenant les traductions LINQ pour ltree par le biais du LTree type, bien que les CTE récursives aient encore besoin d’une SQL brute

logo

© 2026 Scott Galloway — Unlicense — All content and source code on this site is free to use, copy, modify, and sell.