tessl/pypi-django-treebeard

Efficient tree implementations for Django models providing three different tree algorithms with unified API

—

Pending

Overview

Eval results

Files

Tree Implementation Models

Name: tessl/pypi-django-treebeard
Author: tessl

Django Treebeard provides three different tree implementations, each optimized for specific use cases and performance characteristics. All implementations inherit from the abstract Node base class, providing a unified API while using different database storage strategies.

Capabilities

Base Node Class

The abstract base class that defines the common interface for all tree implementations.

class Node(models.Model):
    """
    Abstract base class for all tree implementations.
    
    Provides common interface methods but no actual storage fields.
    Subclasses must implement specific tree algorithm fields.
    """
    
    class Meta:
        abstract = True
    
    # Database connection attribute
    _db_connection = None

Adjacency List Implementation

Traditional parent-child relationship model, storing direct parent references for each node.

class AL_Node(Node):
    """
    Adjacency List tree implementation.
    
    Stores parent-child relationships using foreign keys.
    Best for small trees with frequent write operations.
    """
    
    # Required fields (must be defined in your model):
    # parent = models.ForeignKey('self', null=True, blank=True, on_delete=models.CASCADE)
    # sib_order = models.PositiveIntegerField()
    
    # Configuration
    node_order_by = None  # List of field names for ordering
    objects = AL_NodeManager()
    
    class Meta:
        abstract = True

Required Model Fields

When using AL_Node, you must define these fields in your model:

class YourModel(AL_Node):
    parent = models.ForeignKey(
        'self', 
        null=True, 
        blank=True, 
        on_delete=models.CASCADE,
        related_name='children'
    )
    sib_order = models.PositiveIntegerField()
    
    # Your additional fields here
    name = models.CharField(max_length=255)

AL_NodeManager

Custom manager that provides ordered querysets based on sibling order.

class AL_NodeManager(models.Manager):
    """
    Custom manager for Adjacency List trees.
    
    Automatically orders nodes by sib_order field.
    """
    
    def get_queryset(self):
        """
        Returns queryset ordered by sib_order.
        
        Returns:
            QuerySet: Ordered queryset of nodes
        """

Materialized Path Implementation

Path-based tree storage using encoded paths to represent node positions in the hierarchy.

class MP_Node(Node):
    """
    Materialized Path tree implementation.
    
    Stores node position as encoded path strings.
    Excellent for read-heavy workloads and large trees.
    """
    
    # Built-in fields
    path = models.CharField(max_length=255, unique=True)
    depth = models.PositiveIntegerField()
    numchild = models.PositiveIntegerField()
    
    # Configuration attributes
    steplen = 4  # Length of each path step
    alphabet = '0123456789ABCDEFGHIJKLMNOPQRSTUVWXYZ'  # Encoding alphabet
    node_order_by = []  # List of field names for ordering
    gap = 1  # Gap between path values for insertions
    
    objects = MP_NodeManager()
    
    class Meta:
        abstract = True

MP_Node Configuration

Customize the path encoding and behavior:

class Category(MP_Node):
    name = models.CharField(max_length=50)
    
    # Path configuration
    steplen = 6          # Longer steps = deeper trees possible
    alphabet = '0123456789ABCDEF'  # Hex alphabet for compact paths  
    gap = 10             # Larger gaps = more insertion space
    node_order_by = ['name']  # Automatic ordering by name

Path Format

The path field encodes the node's position using the configured alphabet:

Root nodes: 0001, 0002, 0003, etc.
Children: 00010001, 00010002 (parent_path + child_step)
Path length determines maximum tree depth: max_depth = 255 / steplen

MP_NodeManager and MP_NodeQuerySet

Enhanced manager and queryset with optimized deletion handling.

class MP_NodeManager(models.Manager):
    """Custom manager for Materialized Path trees."""
    
    def get_queryset(self):
        """Returns MP_NodeQuerySet instance."""

class MP_NodeQuerySet(models.QuerySet):
    """
    Custom queryset with enhanced delete method.
    
    Handles descendant deletion efficiently for MP trees.
    """
    
    def delete(self):
        """
        Enhanced delete that properly handles MP tree structure.
        
        Automatically deletes all descendants and updates tree.
        """

Nested Sets Implementation

Left/right boundary model using numerical boundaries to represent tree structure.

class NS_Node(Node):
    """
    Nested Sets tree implementation.
    
    Uses left/right boundaries to represent tree structure.
    Optimal for complex tree queries and read operations.
    """
    
    # Built-in fields
    lft = models.PositiveIntegerField(db_index=True)
    rgt = models.PositiveIntegerField(db_index=True) 
    tree_id = models.PositiveIntegerField(db_index=True)
    depth = models.PositiveIntegerField(db_index=True)
    
    # Configuration
    node_order_by = []  # List of field names for ordering
    
    objects = NS_NodeManager()
    
    class Meta:
        abstract = True

Nested Sets Logic

Nodes are represented by left (lft) and right (rgt) boundaries:

Parent nodes: lft < child_lft < child_rgt < rgt
Siblings: Non-overlapping boundaries within same parent
Descendants: All nodes with boundaries between parent's boundaries
Ancestors: All nodes whose boundaries contain current node's boundaries

NS_NodeManager and NS_NodeQuerySet

Enhanced manager and queryset optimized for nested sets operations.

class NS_NodeManager(models.Manager):
    """Custom manager for Nested Sets trees."""
    
    def get_queryset(self):
        """Returns NS_NodeQuerySet instance."""

class NS_NodeQuerySet(models.QuerySet):
    """
    Custom queryset with enhanced delete method.
    
    Handles gap closing after node deletion in nested sets.
    """
    
    def delete(self, removed_ranges=None, deleted_counter=None):
        """
        Enhanced delete with gap closing for nested sets.
        
        Parameters:
            removed_ranges (list, optional): List of removed boundary ranges
            deleted_counter (dict, optional): Counter for deleted nodes
            
        Automatically updates lft/rgt values after deletion.
        """

Implementation Selection Guide

Choose AL_Node When:

Small to medium trees (< 1000 nodes)
Frequent write operations (insertions, moves, deletions)
Simple parent-child queries are primary use case
Memory usage is a concern
Straightforward tree structure requirements

Choose MP_Node When:

Large trees (1000+ nodes)
Read-heavy workloads
Path-based queries are common
Need efficient ancestor/descendant lookups
Want readable path representation
Bulk operations are frequent

Choose NS_Node When:

Complex tree queries (subtree statistics, range queries)
Read-heavy workloads with minimal writes
Need efficient "get all descendants" operations
Advanced tree analytics requirements
Database supports efficient range queries

Common Usage Patterns

Creating Tree Models

# Adjacency List
class Category(AL_Node):
    parent = models.ForeignKey('self', null=True, blank=True, on_delete=models.CASCADE)
    sib_order = models.PositiveIntegerField()
    name = models.CharField(max_length=100)
    
    node_order_by = ['name']

# Materialized Path  
class Department(MP_Node):
    name = models.CharField(max_length=100)
    code = models.CharField(max_length=20)
    
    node_order_by = ['code', 'name']
    steplen = 4

# Nested Sets
class MenuItem(NS_Node):
    title = models.CharField(max_length=100)
    url = models.URLField(blank=True)
    
    node_order_by = ['title']

Model Registration

# In admin.py
from django.contrib import admin
from treebeard.admin import TreeAdmin
from .models import Category

@admin.register(Category)
class CategoryAdmin(TreeAdmin):
    list_display = ['name', 'get_depth']
    list_filter = ['depth']

Database Considerations

Indexing

AL_Node: Index on parent and sib_order fields
MP_Node: Index on path (unique), depth, and numchild fields
NS_Node: Index on lft, rgt, tree_id, and depth fields (all included by default)

Performance

AL_Node: O(depth) for ancestor queries, O(1) for parent/children
MP_Node: O(1) for most operations, efficient string prefix queries
NS_Node: O(1) for subtree queries, but expensive for writes

Storage

AL_Node: Minimal storage overhead (2 integers per node)
MP_Node: Path string storage (up to 255 characters)
NS_Node: 4 integers per node, most storage overhead

Install with Tessl CLI

npx tessl i tessl/pypi-django-treebeard

docs