0
# Tree Implementation Models
1
2
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.
3
4
## Capabilities
5
6
### Base Node Class
7
8
The abstract base class that defines the common interface for all tree implementations.
9
10
```python { .api }
11
class Node(models.Model):
12
"""
13
Abstract base class for all tree implementations.
14
15
Provides common interface methods but no actual storage fields.
16
Subclasses must implement specific tree algorithm fields.
17
"""
18
19
class Meta:
20
abstract = True
21
22
# Database connection attribute
23
_db_connection = None
24
```
25
26
### Adjacency List Implementation
27
28
Traditional parent-child relationship model, storing direct parent references for each node.
29
30
```python { .api }
31
class AL_Node(Node):
32
"""
33
Adjacency List tree implementation.
34
35
Stores parent-child relationships using foreign keys.
36
Best for small trees with frequent write operations.
37
"""
38
39
# Required fields (must be defined in your model):
40
# parent = models.ForeignKey('self', null=True, blank=True, on_delete=models.CASCADE)
41
# sib_order = models.PositiveIntegerField()
42
43
# Configuration
44
node_order_by = None # List of field names for ordering
45
objects = AL_NodeManager()
46
47
class Meta:
48
abstract = True
49
```
50
51
#### Required Model Fields
52
53
When using AL_Node, you must define these fields in your model:
54
55
```python { .api }
56
class YourModel(AL_Node):
57
parent = models.ForeignKey(
58
'self',
59
null=True,
60
blank=True,
61
on_delete=models.CASCADE,
62
related_name='children'
63
)
64
sib_order = models.PositiveIntegerField()
65
66
# Your additional fields here
67
name = models.CharField(max_length=255)
68
```
69
70
#### AL_NodeManager
71
72
Custom manager that provides ordered querysets based on sibling order.
73
74
```python { .api }
75
class AL_NodeManager(models.Manager):
76
"""
77
Custom manager for Adjacency List trees.
78
79
Automatically orders nodes by sib_order field.
80
"""
81
82
def get_queryset(self):
83
"""
84
Returns queryset ordered by sib_order.
85
86
Returns:
87
QuerySet: Ordered queryset of nodes
88
"""
89
```
90
91
### Materialized Path Implementation
92
93
Path-based tree storage using encoded paths to represent node positions in the hierarchy.
94
95
```python { .api }
96
class MP_Node(Node):
97
"""
98
Materialized Path tree implementation.
99
100
Stores node position as encoded path strings.
101
Excellent for read-heavy workloads and large trees.
102
"""
103
104
# Built-in fields
105
path = models.CharField(max_length=255, unique=True)
106
depth = models.PositiveIntegerField()
107
numchild = models.PositiveIntegerField()
108
109
# Configuration attributes
110
steplen = 4 # Length of each path step
111
alphabet = '0123456789ABCDEFGHIJKLMNOPQRSTUVWXYZ' # Encoding alphabet
112
node_order_by = [] # List of field names for ordering
113
gap = 1 # Gap between path values for insertions
114
115
objects = MP_NodeManager()
116
117
class Meta:
118
abstract = True
119
```
120
121
#### MP_Node Configuration
122
123
Customize the path encoding and behavior:
124
125
```python { .api }
126
class Category(MP_Node):
127
name = models.CharField(max_length=50)
128
129
# Path configuration
130
steplen = 6 # Longer steps = deeper trees possible
131
alphabet = '0123456789ABCDEF' # Hex alphabet for compact paths
132
gap = 10 # Larger gaps = more insertion space
133
node_order_by = ['name'] # Automatic ordering by name
134
```
135
136
#### Path Format
137
138
The `path` field encodes the node's position using the configured alphabet:
139
140
- Root nodes: `0001`, `0002`, `0003`, etc.
141
- Children: `00010001`, `00010002` (parent_path + child_step)
142
- Path length determines maximum tree depth: `max_depth = 255 / steplen`
143
144
#### MP_NodeManager and MP_NodeQuerySet
145
146
Enhanced manager and queryset with optimized deletion handling.
147
148
```python { .api }
149
class MP_NodeManager(models.Manager):
150
"""Custom manager for Materialized Path trees."""
151
152
def get_queryset(self):
153
"""Returns MP_NodeQuerySet instance."""
154
155
class MP_NodeQuerySet(models.QuerySet):
156
"""
157
Custom queryset with enhanced delete method.
158
159
Handles descendant deletion efficiently for MP trees.
160
"""
161
162
def delete(self):
163
"""
164
Enhanced delete that properly handles MP tree structure.
165
166
Automatically deletes all descendants and updates tree.
167
"""
168
```
169
170
### Nested Sets Implementation
171
172
Left/right boundary model using numerical boundaries to represent tree structure.
173
174
```python { .api }
175
class NS_Node(Node):
176
"""
177
Nested Sets tree implementation.
178
179
Uses left/right boundaries to represent tree structure.
180
Optimal for complex tree queries and read operations.
181
"""
182
183
# Built-in fields
184
lft = models.PositiveIntegerField(db_index=True)
185
rgt = models.PositiveIntegerField(db_index=True)
186
tree_id = models.PositiveIntegerField(db_index=True)
187
depth = models.PositiveIntegerField(db_index=True)
188
189
# Configuration
190
node_order_by = [] # List of field names for ordering
191
192
objects = NS_NodeManager()
193
194
class Meta:
195
abstract = True
196
```
197
198
#### Nested Sets Logic
199
200
Nodes are represented by left (lft) and right (rgt) boundaries:
201
202
- Parent nodes: `lft < child_lft < child_rgt < rgt`
203
- Siblings: Non-overlapping boundaries within same parent
204
- Descendants: All nodes with boundaries between parent's boundaries
205
- Ancestors: All nodes whose boundaries contain current node's boundaries
206
207
#### NS_NodeManager and NS_NodeQuerySet
208
209
Enhanced manager and queryset optimized for nested sets operations.
210
211
```python { .api }
212
class NS_NodeManager(models.Manager):
213
"""Custom manager for Nested Sets trees."""
214
215
def get_queryset(self):
216
"""Returns NS_NodeQuerySet instance."""
217
218
class NS_NodeQuerySet(models.QuerySet):
219
"""
220
Custom queryset with enhanced delete method.
221
222
Handles gap closing after node deletion in nested sets.
223
"""
224
225
def delete(self, removed_ranges=None, deleted_counter=None):
226
"""
227
Enhanced delete with gap closing for nested sets.
228
229
Parameters:
230
removed_ranges (list, optional): List of removed boundary ranges
231
deleted_counter (dict, optional): Counter for deleted nodes
232
233
Automatically updates lft/rgt values after deletion.
234
"""
235
```
236
237
## Implementation Selection Guide
238
239
### Choose AL_Node When:
240
- Small to medium trees (< 1000 nodes)
241
- Frequent write operations (insertions, moves, deletions)
242
- Simple parent-child queries are primary use case
243
- Memory usage is a concern
244
- Straightforward tree structure requirements
245
246
### Choose MP_Node When:
247
- Large trees (1000+ nodes)
248
- Read-heavy workloads
249
- Path-based queries are common
250
- Need efficient ancestor/descendant lookups
251
- Want readable path representation
252
- Bulk operations are frequent
253
254
### Choose NS_Node When:
255
- Complex tree queries (subtree statistics, range queries)
256
- Read-heavy workloads with minimal writes
257
- Need efficient "get all descendants" operations
258
- Advanced tree analytics requirements
259
- Database supports efficient range queries
260
261
## Common Usage Patterns
262
263
### Creating Tree Models
264
265
```python
266
# Adjacency List
267
class Category(AL_Node):
268
parent = models.ForeignKey('self', null=True, blank=True, on_delete=models.CASCADE)
269
sib_order = models.PositiveIntegerField()
270
name = models.CharField(max_length=100)
271
272
node_order_by = ['name']
273
274
# Materialized Path
275
class Department(MP_Node):
276
name = models.CharField(max_length=100)
277
code = models.CharField(max_length=20)
278
279
node_order_by = ['code', 'name']
280
steplen = 4
281
282
# Nested Sets
283
class MenuItem(NS_Node):
284
title = models.CharField(max_length=100)
285
url = models.URLField(blank=True)
286
287
node_order_by = ['title']
288
```
289
290
### Model Registration
291
292
```python
293
# In admin.py
294
from django.contrib import admin
295
from treebeard.admin import TreeAdmin
296
from .models import Category
297
298
@admin.register(Category)
299
class CategoryAdmin(TreeAdmin):
300
list_display = ['name', 'get_depth']
301
list_filter = ['depth']
302
```
303
304
## Database Considerations
305
306
### Indexing
307
- AL_Node: Index on `parent` and `sib_order` fields
308
- MP_Node: Index on `path` (unique), `depth`, and `numchild` fields
309
- NS_Node: Index on `lft`, `rgt`, `tree_id`, and `depth` fields (all included by default)
310
311
### Performance
312
- AL_Node: O(depth) for ancestor queries, O(1) for parent/children
313
- MP_Node: O(1) for most operations, efficient string prefix queries
314
- NS_Node: O(1) for subtree queries, but expensive for writes
315
316
### Storage
317
- AL_Node: Minimal storage overhead (2 integers per node)
318
- MP_Node: Path string storage (up to 255 characters)
319
- NS_Node: 4 integers per node, most storage overhead