PostgreSQL Ltree trees (experimental)

This is an efficient tree implementation using PostgreSQL’s ltree module. It requires a PostgreSQL database.

This is currently an experimental implementation, open for testing and feedback from the community.

Treebeard uses a simple alphabet to generate path hierarchies for objects in the database. In order to ensure efficient ordering, it uses an approach similar to the Materialized Path implementation to use path values that match the desired order of nodes in the database.

To use the ltree module, you need to create the extension in your database:

CREATE EXTENSION IF NOT EXISTS ltree;

Warning

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

class treebeard.ltree.LT_Node(*args, **kwargs)

Bases: Node

Abstract model to create your own Postgres LTree trees.

Warning

Do not change the values of path directly. Use one of the included methods instead. Consider these values read-only.

Warning

Do not change the values of node_order_by after saving your first object. Doing so will result in objects being ordered incorrectly.

Warning

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

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

Example:

class SortedNode(LT_Node):
   node_order_by = ['numval', 'strval']

   numval = models.IntegerField()
   strval = models.CharField(max_length=255)

Read the API reference of treebeard.models.Node for info on methods available in this class, or read the following section for methods with particular arguments or exceptions.

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. This takes precedence over drag and drop ordering in the Django admin.

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.

path

ltree field, stores an ltree hierarchy for the node. The values are auto-generated by Treebeard from a simple alphabet.

classmethod add_root(**kwargs)

See: treebeard.models.Node.add_root()

move(target, pos=None)

See: treebeard.models.Node.move()

classmethod get_tree(*args, treebeard_method='get_tree', **kwargs)

Backward compatibility for class methods that have moved to the model manager.

Logs a warning, and calls the manager method.

This backward-compatibility will be removed in Treebeard 7.

See: treebeard.models.Node.get_tree()

class treebeard.ltree.LT_NodeManager(*args, **kwargs)

Bases: NodeManager

Custom manager for nodes in a Materialized Path tree.

add_child(**kwargs)

Adds a child to the node. The new node will be the new rightmost child. If you want to insert a node at a specific position, use the add_sibling() method of an already existing child node instead.

Parameters:

• create_kwargs – dictionary of values to set on the model object.

• instance – Instead of passing object creation data, you can pass an already-constructed (but not yet saved) model instance to be inserted into the tree.

Returns:

The created node object. It will be save()d by this method.

Raises:

NodeAlreadySaved – when the passed instance already exists in the database

See: treebeard.models.NodeManager.add_child()

add_sibling(**kwargs)

Adds a new node as a sibling to the current node object.

Parameters:

• pos –

  The position, relative to the current node object, where the new node will be inserted, can be one of:

  • first-sibling: the new node will be the new leftmost sibling

  • left: the new node will take the node’s place, which will be moved to the right 1 position

  • right: the new node will be inserted at the right of the node

  • last-sibling: the new node will be the new rightmost sibling

  • sorted-sibling: the new node will be at the right position according to the value of node_order_by

• create_kwargs – dictionary of values to set on the model object.

• instance – Instead of passing object creation data, you can pass an already-constructed (but not yet saved) model instance to be inserted into the tree.

Returns:

The created node object. It will be saved by this method.

Raises:

• InvalidPosition – when passing an invalid pos parm

• InvalidPosition – when node_order_by is enabled and the pos parm wasn’t sorted-sibling

• MissingNodeOrderBy – when passing sorted-sibling as pos and the node_order_by attribute is missing

• NodeAlreadySaved – when the passed instance already exists in the database

See: treebeard.models.NodeManager.add_sibling()

class treebeard.ltree.LT_NodeQuerySet(model=None, query=None, using=None, hints=None)

Bases: QuerySet

Custom queryset for the tree node manager.

Needed only for the custom delete method.

Signals

The treebeard.ltree 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.ltree.subtree_moved_right

Sent after a bulk update has been performed to increment existing path values to allow inserting a sibling node, with the following arguments:

sender

The model class where the update occurred.

path

A treebeard.ltree.PathValue indicating the first path updated. The update operation applies to the node with this path, siblings after it (i.e. nodes where all path elements are equal except the last, which is greater), and all their descendants. For the targeted node and its siblings, the update operation appends an ‘A’ to the last element of the path; for example, the path A.C.B becomes A.C.BA. For their descendants, the path elements following the incremented one are unchanged; for example, the path A.C.B.D becomes A.C.BA.D.

using

The database alias being used.

treebeard.ltree.subtree_moved

Sent after a bulk update has been performed to update the paths of a node and its descendants, with the following arguments:

sender

The model class where the update occurred.

old_path

A treebeard.ltree.PathValue indicating the old path of the topmost node before the update. The update operation applies to all nodes with this path as a prefix.

new_path

A treebeard.ltree.PathValue indicating the new path of the topmost node after the update. For all nodes in the update, the prefix old_path is replaced with new_path.

using

The database alias being used.

treebeard.ltree.nodes_deleted

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

sender

The model class where the deletion occurred.

paths_to_remove

A list of treebeard.ltree.PathValue instances indicating the paths of the nodes that were deleted (along with their descendants). All nodes that have any of these paths as a prefix were deleted.

using

The database alias being used.