Nested Sets trees

An implementation of Nested Sets trees for Django, as described by Joe Celko in Trees and Hierarchies in SQL for Smarties.

Nested sets have very efficient reads at the cost of high maintenance on write/delete operations.

Warning

As with all tree implementations, please be aware of the Known Caveats.

class treebeard.ns_tree.NS_Node(*args, **kwargs)

Bases: Node

Abstract model to create your own Nested Sets Trees.

Warning

If you need to define your own Manager class, you’ll need to subclass NS_NodeManager.

Also, if in your manager you need to change the default queryset handler, you’ll need to subclass NS_NodeQuerySet.

node_order_by

Attribute: a list of model fields that will be used for node ordering. When enabled, all tree operations will assume this ordering.

Example:

node_order_by = ['field1', 'field2', 'field3']

Warning

node_order_by values are used to determine correct node ordering before an object is inserted/moved. This means any fields that are auto-populated at a database level, e.g., AutoField(), or DateTimeField(auto_now=True) will be ignored for the purpose of ordering if a value isn’t provided manually.

depth

PositiveIntegerField, depth of a node in the tree. A root node has a depth of 1.

lft

PositiveIntegerField

rgt

PositiveIntegerField

tree_id

PositiveIntegerField

classmethod get_tree(parent=None)

Returns:

A queryset of nodes ordered as DFS, including the parent. If no parent is given, all trees are returned.

See: treebeard.models.Node.get_tree()

Note

This method returns a queryset.

classmethod find_problems(parent=None)

Checks for inconsistencies in the tree structure.

Parameters:

parent – If provided, limits the check to the descendants of this node. If not provided, the entire tree will be checked.

Returns:

A tuple of four lists:

1. a list of ids of nodes where rgt is not strictly greater than lft

2. a list of ids of nodes where the lft and rgt values partially overlap with another node (i.e. they are not properly nested)

3. a list of ids of root-level nodes that have the same tree_id as another root-level node

4. a list of ids of nodes with the wrong depth value for their nesting level as defined by lft and rgt

Note

A node won’t appear in more than one list, even when it exhibits more than one problem. This method stops checking a node when it finds a problem and continues to the next node.

Note

These problems can’t be solved automatically.

Example:

MyNodeModel.find_problems()

class treebeard.ns_tree.NS_NodeManager(*args, **kwargs)

Bases: Manager

Custom manager for nodes in a Nested Sets tree.

class treebeard.ns_tree.NS_NodeQuerySet(model=None, query=None, using=None, hints=None)

Bases: QuerySet

Custom queryset for the tree node manager.

Needed only for the customized delete method.

Signals

The treebeard.ns_tree module defines several signals that are sent when bulk updates are made to the tree. Along with the standard Django post_save and post_delete signals that track changes to individual node instances, these can be used to keep external data stores such as search indexes in sync with the tree.

treebeard.ns_tree.gap_altered

Sent after a bulk update has been performed to expand or shrink a gap in the lft/rgt sequence, with the following arguments:

sender

The model class where the update occurred.

tree_id

The tree ID of the tree that was updated.

start_index

The starting index of the update. All lft and rgt values greater than or equal to this index, within the tree identified by tree_id, were incremented or decremented by offset.

offset

The amount by which the gap was expanded (positive) or shrunk (negative).

using

The database alias being used.

treebeard.ns_tree.tree_ids_incremented

Sent after a bulk update has been performed to increment tree IDs to allow a new root-level node to be inserted, with the following arguments:

sender

The model class where the update occurred.

min_tree_id

The starting tree ID of the update. All tree IDs greater than or equal to this value were incremented by 1.

using

The database alias being used.

treebeard.ns_tree.subtree_moved

Sent after a bulk update has been performed to move a subtree, with the following arguments:

sender

The model class where the update occurred.

tree_id

The tree ID of the tree that the subtree was moved from.

lft

The initial left value of the topmost node that was moved.

rgt

The initial right value of the topmost node that was moved. The update operation applies to all nodes in the tree tree_id with left values greater than or equal to lft and right values less than or equal to rgt.

target_tree_id

The tree ID of the target tree where the subtree was moved to.

index_offset

The amount by which the left and right values of the moved nodes were incremented (positive) or decremented (negative) during the move.

depth_offset

The amount by which the depth of the moved nodes was changed during the move.

using

The database alias being used.

treebeard.ns_tree.nodes_deleted

Sent after one or more nodes are deleted, with the following arguments:

sender

The model class where the deletion occurred.

removed_ranges

A list of tuples, each containing the tree ID, left value, and right value of a contiguous range of nodes that were deleted.

using

The database alias being used.