Datenhierarchien Teil 1.5: PostgreSQL ltree mit EF Core
Mit der ltree-Erweiterung von PostgreSQL erhalten Sie materialisierte Wege mit datenbanknativen Superkräften: GiST-Indizes, spezialisierte Operatoren wie @> und <@, und leistungsstarke Muster-Matching. Wenn Sie sich für PostgreSQL und wollen die beste Hierarchie Abfrage Leistung, ltree ist schwer zu schlagen.
Gute Nachrichten: Das Npgsql EF Core-Anbieter unterstützt LINQ-Übersetzungen für ltree-Operationen über die LTree type. Sie können Methoden wie IsAncestorOf(), IsDescendantOf(), und MatchesLQuery() direkt in LINQ-Abfragen. EF Core unterstützt jedoch noch keine rekursiven CTEs, so dass Sie Roh-SQL für Operationen benötigen, die sie benötigen (wie das Erstellen kompletter Subtree-Ergebnisse mit berechneten Tiefen).
Dank Shay Rojansky für den Hinweis auf die LINQ Übersetzungsunterstützung!
Reihennavigation
- Teil 1: Überblick - Einführung und Vergleich
- Teil 1.1: Adjazenzliste
- Teil 1.2: Schließungstabelle
- Teil 1.3: Materialisierter Pfad
- Teil 1.4: Verschachtelte Sets
- Teil 1.5: Baum (dieser Artikel)
Was ist Itree?
ltree ist eine PostgreSQL-Erweiterung, die einen nativen Datentyp für hierarchische Etikettenpfade bietet. Materialisierter Pfad mit Superpowers - die Datenbank versteht die Struktur und bietet optimierte Operatoren, Funktionen und GiST-Index-Unterstützung.
Anstatt den Pfad als dumme Zeichenkette zu behandeln und LIKE-Abfragen zu verwenden, kann PostgreSQL:
- Einsatz von spezialisierten Betreibern (
@>für "Vorfahre von",<@für "ist Nachkommen von") - GiST-Indizes für effiziente Hierarchieabfragen anwenden
- Spielmuster mit Wildcards (
Top.*.Europe) - Set-Operationen auf Pfaden durchführen
Wichtige Erkenntnisse: ltree ist das Beste aus beiden Welten - die Einfachheit materialisierter Pfade mit datenbanknativer Optimierung. Das Trade-off ist PostgreSQL Lock-in, und während viele ltree Operationen über LINQ funktionieren, benötigen rekursive CTEs immer noch rohes SQL.
Baumpfad-Format
Pfade in ltree verwenden Perioden als Separatoren und alphanumerische Etiketten:
Top.Countries.Europe.UK
Top.Countries.Asia.Japan.Tokyo
Top.Products.Electronics.Computers.Laptops
Regeln:
- Etiketten können Buchstaben, Ziffern und Unterstriche enthalten
- Etiketten sind fallsensibel
- Maximale Etikettenlänge ist 256 Zeichen
- Maximale Länge des Pfades ist 65535 Etiketten
Für Kommentarsysteme verwenden wir IDs als Labels: 1.3.7 Bedeutung "Kommentar 7 unter Kommentar 3 unter Kommentar 1".
Einrichten von ltree
Aktivieren Sie zunächst die Erweiterung (erfordert Datenbank-Superuser-Rechte):
CREATE EXTENSION IF NOT EXISTS ltree;
Oder über EF-Core-Migration:
protected override void Up(MigrationBuilder migrationBuilder)
{
migrationBuilder.Sql("CREATE EXTENSION IF NOT EXISTS ltree");
}
Definition des Rechtsträgers
Der Npgsql-Anbieter umfasst eine LTree Typ, der direkt auf PostgreSQL's ltree abbildet und LINQ-übersetzbare Methoden zur Verfügung stellt:
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;
}
}
}
EF-Kernkonfiguration
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);
}
}
Fügen Sie den GiST-Index über Migration hinzu:
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)");
}
Baumbewirtschafter
ltree bietet leistungsstarke Bediener. Der Npgsql EF Core-Anbieter übersetzt LTree Methoden für diese Betreiber:
Operator-Beispiel: LINQ-Methode: SQL-Beispiel: LINQ-Methode: LINQ-Methode: LINQ-Methode: LINQ-Methode: LINQ-Methode: LINQ-Methode: LINQ-Methode: LINQ-Methode: LINQ-Methode: LINQ-Methode: LINQ-Methode: LINQ-Methode: LINQ-Methode: LINQ-Methode: LINQ-Methode: LINQ-Methode: LINQ-Methode: SQL-Beispiel: LINQ-Methode: LINQ-Methode: LINQ-Methode: LINQ-Methode: LINQ-Methode: LINQ-Methode: LINQ-Methode:
|----------|---------|-------------|-------------|
| @> Vorfahre von (enthält) ltree1.IsAncestorOf(ltree2) | '1.3'::ltree @> '1.3.7'::ltree → wahr
| <@ Ist Nachkommen von (enthalten durch) ltree1.IsDescendantOf(ltree2) | '1.3.7'::ltree <@ '1.3'::ltree → wahr
| ~ Entspricht dem Muster der Fragestellung. ltree.MatchesLQuery(pattern) | '1.3.7'::ltree ~ '1.*'::lquery → wahr
| @ Passt zu ltxtquery ltree.MatchesLTxtQuery(query) | '1.3.7'::ltree @ '3 & 7'::ltxtquery → wahr
| || Konkatenate Pfade (Verkettung der Zeichenkette) '1.3'::ltree || '7'::ltree → '1.3.7' |
| <, >, <=, >= Vergleichen Standard-Operatoren Zum Sortieren
Zusätzliche LINQ-übersetzbare Eigenschaften und Methoden:
ltree.NLevel→nlevel(ltree)- Anzahl der Etiketten im Pfadltree.Subtree(start, end)→subltree(ltree, start, end)- Reihe von Etiketten extrahierenltree.Subpath(offset)→subpath(ltree, offset)- Suffix aus Offsetltree.Subpath(offset, len)→subpath(ltree, offset, len)- Substringltree.Index(subpath)→index(ltree, subpath)- Subpath-Position findenLTree.LongestCommonAncestor(ltree1, ltree2)→lca(ltree1, ltree2)- niedrigster gemeinsamer Vorfahre
Vorhaben
Neuen Kommentar einfügen
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;
}
}
Sofortige Kinder bekommen
Verwenden von ParentCommentId (einfach) oder ltree pattern matching:
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);
}
Holen Sie sich alle Vorfahren
Verwendung von LINQ mit dem IsAncestorOf Verfahren (übersetzt auf @> Betreiber:
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);
}
Holen Sie sich alle Nachkommen
Verwendung von LINQ mit dem IsDescendantOf Verfahren (übersetzt auf <@ Betreiber:
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);
}
Erhalten Sie Nachkommen bis zur maximalen Tiefe
Verwendung von LINQ mit NLevel für die Tiefenbegrenzung:
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);
}
Muster passend zu Abfragen
ltree unterstützt leistungsstarke Lquery-Muster. 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);
}
Einen Unterbaum löschen
Sie können LINQ verwenden, um den Unterbaum auszuwählen und dann zu löschen:
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);
}
Einen Unterbaum verschieben
ltree bietet Funktionen, um bei der Pfadmanipulation zu helfen:
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;
}
}
ltree-Funktionen Referenz
PostgreSQL bietet viele nützliche ltree-Funktionen:
• Funktion • Beschreibung • Beispiel •
|----------|-------------|---------|
| nlevel(ltree) Anzahl der Etiketten nlevel('1.3.7') → 3 |
| subpath(ltree, offset) Suffix aus dem Offset subpath('1.3.7', 1) → '3.7' |
| subpath(ltree, offset, len) Substring subpath('1.3.7', 1, 1) → '3' |
| subltree(ltree, start, end) Bereich der Etiketten subltree('1.3.7', 0, 2) → '1.3' |
| lca(ltree, ltree) Niedrigster gemeinsamer Vorfahre lca('1.3.7', '1.3.9') → '1.3' |
| text2ltree(text) Text in ltree umrechnen text2ltree('1.3.7') |
| ltree2text(ltree) ltree nach Text umrechnen ltree2text('1.3.7'::ltree) |
Abfragestrom-Visualisierung
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>
Leistungsmerkmale
Anmerkungen zur Bedienung |-----------|------------|-------| Geben Sie einfach den Pfad-String ein Holen Sie sich Kinder O(1)-Muster-Match mit GiST-Index Erhalten Sie Ahnen O(1). @> Operator mit GiST-Index. <@operator mit GiST-Index Muster-Matching-Index unterstützt Iquery-Index für O(log n) Subtree verschieben [O(s)] Aktualisieren der nachwachsenden Pfade Subtree O(1) löschen <@operator für die Auswahl
Bei GiST-Indizes sind ltree-Abfragen extrem effizient - typischerweise O(log n) unabhängig von der Baumtiefe.
Vor- und Nachteile
Pros. Cons.
|------|------|
• Datenbank-native Optimierung • PostgreSQL-only
GiST-Index für alle Hierarchie-Abfragen, Erweiterungsabhängigkeit,
• Leistungsstarkes Muster, das auf alphanumerisch beschränkt ist
· Eingebaute Pfadmanipulationsfunktionen · Rekursive CTEs erfordern rohe SQL-Funktionen ·
O(1) Vorfahre/Abhängige Abfragen weniger tragbar als reine EF-Core-Lösungen
Kompakte Lagerung
LINQ-Unterstützung über Npgsql LTree Art
Wann wird ltree verwendet?
Wählen Sie ltree, wenn:
- Du bist der PostgreSQL verpflichtet.
- Leistung ist für Hierarchieabfragen von entscheidender Bedeutung
- Sie benötigen Muster-Matching (finden Sie alle X.*.Y-Wege)
- Sie wollen das Beste aus materialisierten Pfaden
- Sie wollen LINQ-Unterstützung für die meisten Hierarchieoperationen
Vermeiden Sie ltree, wenn:
- Sie benötigen Datenbankübertragbarkeit (SQL Server, MySQL, etc.)
- Ihr Team ist mit PostgreSQL-Erweiterungen nicht vertraut
- Etiketten benötigen nicht-alphanumerische Zeichen
- Sie benötigen rekursive CTEs und möchten jede rohe SQL vermeiden
Vergleich mit dem materialisierten Pfad
Aspekt materialisierter Pfad ltree
|--------|-------------------|-------|
Indextyp B-Baum (nur Präfix)
Muster, das nur mit 'Prefix%' übereinstimmt. Volle Wildcards.
Operatoren: String-Vergleich, Native @>, <@, ~-
Nur PostgreSQL-Datenbanken
EF-Core-Unterstützung Vollständiges LINQ-LINQ über LTree Typ (CTEs benötigen rohen SQL)
Gut mit Index ausgezeichnet mit GiST
Keine Funktionen (manuelles Parsing) Ausreichende Funktionsbibliothek
Beispiel: Vollständige Kommentarbaum-Abfrage
Alles zusammenstellen - einen ganzen Kommentarbaum mit Tiefe für einen Blog-Post bekommen:
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; }
}
Reihennavigation
- Teil 1: Überblick
- Teil 1.1: Adjazenzliste
- Teil 1.2: Schließungstabelle
- Teil 1.3: Materialisierter Pfad
- Teil 1.4: Verschachtelte Sets
- Teil 1.5: Baum (dieser Artikel)
Was kommt als Nächstes?
Diese Serie hat fünf Ansätze für hierarchische Daten mit EF Core behandelt. Teil 2 wird mit Roh-SQL und Dapper für noch mehr Kontrolle über Hierarchie-Abfragen zu erforschen - in Kürze!