0
# Django Treebeard
1

2
Django Treebeard provides efficient tree data structure implementations for Django models. It offers three different tree algorithms (Adjacency List, Materialized Path, and Nested Sets) with a unified API, enabling developers to store and manipulate hierarchical data with optimized database operations.
3

4
## Package Information
5

6
- **Package Name**: django-treebeard
7
- **Language**: Python
8
- **Installation**: `pip install django-treebeard`
9
- **Django Support**: Django 3.2, 4.1, 4.2, 5.0
10
- **Python Support**: Python 3.8 - 3.12
11
- **Database Support**: PostgreSQL, MySQL, SQLite, SQL Server
12

13
## Core Imports
14

15
```python
16
from treebeard.al_tree import AL_Node
17
from treebeard.mp_tree import MP_Node  
18
from treebeard.ns_tree import NS_Node
19
```
20

21
For admin integration:
22
```python
23
from treebeard.admin import TreeAdmin
24
```
25

26
For forms:
27
```python
28
from treebeard.forms import MoveNodeForm, movenodeform_factory
29
```
30

31
For exceptions:
32
```python
33
from treebeard.exceptions import (
34
    InvalidPosition, InvalidMoveToDescendant, 
35
    NodeAlreadySaved, MissingNodeOrderBy, PathOverflow
36
)
37
```
38

39
## Basic Usage
40

41
```python
42
from django.db import models
43
from treebeard.mp_tree import MP_Node
44

45
class Category(MP_Node):
46
    name = models.CharField(max_length=50)
47
    
48
    node_order_by = ['name']
49

50
# Create root nodes
51
root1 = Category.add_root(name='Electronics')
52
root2 = Category.add_root(name='Books')
53

54
# Add children
55
phones = root1.add_child(name='Phones')
56
laptops = root1.add_child(name='Laptops')
57

58
# Add grandchildren
59
smartphones = phones.add_child(name='Smartphones')
60
tablets = phones.add_child(name='Tablets')
61

62
# Navigate the tree
63
print(root1.get_children())           # [phones, laptops]
64
print(phones.get_parent())            # root1
65
print(root1.get_descendants())        # [phones, laptops, smartphones, tablets]
66
print(smartphones.get_ancestors())    # [root1, phones]
67

68
# Move nodes
69
smartphones.move(laptops, pos='first-child')
70

71
# Bulk operations
72
data = [
73
    {'name': 'Science'},
74
    {'name': 'Fiction', 'children': [
75
        {'name': 'Sci-Fi'},
76
        {'name': 'Fantasy'}
77
    ]}
78
]
79
Category.load_bulk(data, parent=root2)
80
```
81

82
## Architecture
83

84
Django Treebeard provides three tree implementations, each optimized for different use cases:
85

86
### Tree Implementations
87
- **Adjacency List (AL_Node)**: Traditional parent-child references, best for small trees with frequent writes
88
- **Materialized Path (MP_Node)**: Path-based storage, excellent for read-heavy workloads and large trees  
89
- **Nested Sets (NS_Node)**: Left/right boundary model, optimal for read operations and subtree queries
90

91
### Unified API
92
All implementations inherit from the abstract `Node` class, providing consistent methods for tree operations regardless of the underlying algorithm.
93

94
### Django Integration
95
- Model inheritance for easy setup
96
- Admin interface with drag-and-drop support
97
- Form classes for node manipulation
98
- Template tags for rendering trees
99

100
## Capabilities
101

102
### Tree Implementation Models
103

104
Base classes for creating tree models using different algorithms, each with specific performance characteristics and database storage patterns.
105

106
```python { .api }
107
class AL_Node(Node):
108
    """Adjacency List implementation"""
109
    # Requires: parent (ForeignKey), sib_order (PositiveIntegerField)
110

111
class MP_Node(Node):
112
    """Materialized Path implementation"""
113
    path = models.CharField(max_length=255, unique=True)
114
    depth = models.PositiveIntegerField()
115
    numchild = models.PositiveIntegerField()
116

117
class NS_Node(Node):
118
    """Nested Sets implementation"""
119
    lft = models.PositiveIntegerField(db_index=True)
120
    rgt = models.PositiveIntegerField(db_index=True)
121
    tree_id = models.PositiveIntegerField(db_index=True)
122
    depth = models.PositiveIntegerField(db_index=True)
123
```
124

125
[Tree Implementation Models](./tree-models.md)
126

127
### Tree Operations
128

129
Core methods for creating, reading, updating, and deleting tree nodes, including bulk operations and tree structure manipulation.
130

131
```python { .api }
132
# Class methods
133
@classmethod
134
def add_root(**kwargs): ...
135
@classmethod
136
def load_bulk(bulk_data, parent=None, keep_ids=False): ...
137
@classmethod
138
def get_root_nodes(): ...
139

140
# Instance methods  
141
def add_child(**kwargs): ...
142
def add_sibling(pos=None, **kwargs): ...
143
def move(target, pos=None): ...
144
def delete(): ...
145
```
146

147
[Tree Operations](./tree-operations.md)
148

149
### Tree Navigation
150

151
Methods for traversing tree structures, getting related nodes, and querying tree relationships.
152

153
```python { .api }
154
def get_parent(update=False): ...
155
def get_children(): ...
156
def get_siblings(): ...
157
def get_ancestors(): ...
158
def get_descendants(): ...
159
def get_root(): ...
160
def is_child_of(node): ...
161
def is_descendant_of(node): ...
162
```
163

164
[Tree Navigation](./tree-navigation.md)
165

166
### Django Admin Integration
167

168
Admin classes and utilities for managing tree structures through Django's admin interface with drag-and-drop functionality.
169

170
```python { .api }
171
class TreeAdmin(admin.ModelAdmin):
172
    def changelist_view(request, extra_context=None): ...
173
    def move_node(request): ...
174

175
def admin_factory(form_class): ...
176
```
177

178
[Admin Integration](./admin-integration.md)
179

180
### Forms and UI
181

182
Form classes for tree manipulation in Django applications, including move operations and tree rendering.
183

184
```python { .api }
185
class MoveNodeForm(forms.ModelForm):
186
    def save(commit=True): ...
187
    def mk_dropdown_tree(model, for_node=None): ...
188

189
def movenodeform_factory(model, form=MoveNodeForm, **kwargs): ...
190
```
191

192
[Forms and UI](./forms-ui.md)
193

194
### Utility Functions
195

196
Helper functions for number base conversion, tree validation, and database-specific operations.
197

198
```python { .api }
199
# Number conversion for MP trees
200
def int2str(num, radix=10, alphabet=BASE85): ...
201
def str2int(num, radix=10, alphabet=BASE85): ...
202

203
# Tree validation
204
@classmethod  
205
def find_problems(): ...
206
@classmethod
207
def fix_tree(): ...
208
```
209

210
[Utility Functions](./utilities.md)
211

212
## Exception Handling
213

214
Django Treebeard defines specific exceptions for tree operations:
215

216
```python { .api }
217
class InvalidPosition(Exception):
218
    """Raised when passing an invalid pos value"""
219

220
class InvalidMoveToDescendant(Exception):
221
    """Raised when attempting to move a node to one of its descendants"""
222
    
223
class NodeAlreadySaved(Exception):
224
    """Raised when attempting to add a node which is already saved"""
225
    
226
class MissingNodeOrderBy(Exception):
227
    """Raised when node_order_by attribute is missing but required"""
228
    
229
class PathOverflow(Exception):
230
    """Raised when no more space available in MP tree path"""
231
```
232

233
## Configuration
234

235
### Node Ordering
236
Set `node_order_by` on your model class to enable automatic node ordering:
237

238
```python
239
class Category(MP_Node):
240
    name = models.CharField(max_length=50)
241
    created_date = models.DateTimeField(auto_now_add=True)
242
    
243
    node_order_by = ['name', 'created_date']
244
```
245

246
### MP_Node Configuration
247
Materialized Path nodes support additional configuration:
248

249
```python
250
class Category(MP_Node):
251
    name = models.CharField(max_length=50)
252
    
253
    steplen = 4  # Path step length
254
    alphabet = '0123456789ABCDEFGHIJKLMNOPQRSTUVWXYZ'  # Path encoding alphabet
255
    gap = 10     # Gap between path values for insertions
256
```
257

258
## Performance Considerations
259

260
- **AL_Node**: Best for small trees, frequent writes, simple parent-child queries
261
- **MP_Node**: Excellent for large trees, read-heavy workloads, path-based queries
262
- **NS_Node**: Optimal for complex tree queries, subtree operations, minimal writes
263

264
Choose the implementation based on your specific use case and performance requirements.