Combination of Adjacency List and Closure Table
Application for supporting tree (hierarchical) data structure in Django projects
- fast: the fastest of the two methods is used to process requests, combining the advantages of an Adjacency Table and a Closure Table,
- even faster: the main resource-intensive operations are cached; bulk operations are used for inserts and changes,
- synchronized: model instances in memory are automatically updated,
- compatibility: you can easily add a tree node to existing projects using TreeNode without changing the code,
- no dependencies,
- easy setup: just extend the abstract model/model-admin,
- admin integration: visualization options (accordion, breadcrumbs or padding),
- widget: Built-in Select2-to-Tree extends Select2 to support arbitrary nesting levels.
This is a modification of the reusable django-treenode application developed by Fabio Caccamo. The original application has significant advantages over other analogues, and indeed, is one of the best implementations of support for hierarchical structures for Django.
Fabio's idea was to use the Adjacency List method to store the data tree. The most probable and time-consuming requests are calculated in advance and stored in the database. Also, most requests are cached. As a result, query processing is carried out in one call to the database or without it at all.
However, this application has a number of undeniable shortcomings:
- the selected pre-calculations scheme entails high costs for adding a new element;
- inserting new elements uses signals, which leads to failures when using bulk-operations;
- the problem of ordering elements by priority inside the parent node has not been resolved.
My idea was to solve these problems by combining the adjacency list with the Closure Table. Main advantages:
- the Closure Model is generated automatically;
- maintained compatibility with the original package at the level of documented functions;
- most requests are satisfied in one call to the database;
- inserting a new element takes two calls to the database without signals usage;
- bulk-operations are supported;
- the cost of creating a new dependency is reduced many times;
- useful functionality added for some methods (e.g. the
include_self=Falseanddepthparameters has been added to functions that return lists/querysets); - additionally, the package includes a tree view widget for the
tn_parentfield in the change form.
Of course, at large levels of nesting, the use of the Closure Table leads to an increase in resource costs. But at the same time, the combined scheme still generally outperforms the original application in terms of performance.
You can get a basic understanding of what is a Closure Table from:
- presentation by Bill Karwin;
- article by blogger Dirt Simple;
- article by Andriy Zabavskyy.
You can easily find additional information on your own on the Internet.
- Run
pip install django-fast-treenode - Add
treenodetosettings.INSTALLED_APPS - Make your model inherit from
treenode.models.TreeNodeModel(described below) - Make your model-admin inherit from
treenode.admin.TreeNodeModelAdmin(described below) - Run python manage.py makemigrations and
python manage.py migrate
When updating an existing project, simply call cls.update_tree() function once.
It will automatically build a new and complete Closure Table for your tree.
Make your model class inherit from treenode.models.TreeNodeModel:
from django.db import models
from treenode.models import TreeNodeModel
class Category(TreeNodeModel):
# the field used to display the model instance
# default value 'pk'
treenode_display_field = "name"
name = models.CharField(max_length=50)
class Meta(TreeNodeModel.Meta):
verbose_name = "Category"
verbose_name_plural = "Categories"The TreeNodeModel abstract class adds many fields (prefixed with tn_ to prevent direct access) and public methods to your models.
Make your model-admin class inherit from treenode.admin.TreeNodeModelAdmin.
from django.contrib import admin
from treenode.admin import TreeNodeModelAdmin
from treenode.forms import TreeNodeForm
from .models import Category
class CategoryAdmin(TreeNodeModelAdmin):
# set the changelist display mode: 'accordion', 'breadcrumbs' or 'indentation' (default)
# when changelist results are filtered by a querystring,
# 'breadcrumbs' mode will be used (to preserve data display integrity)
treenode_display_mode = TreeNodeModelAdmin.TREENODE_DISPLAY_MODE_ACCORDION
# treenode_display_mode = TreeNodeModelAdmin.TREENODE_DISPLAY_MODE_BREADCRUMBS
# treenode_display_mode = TreeNodeModelAdmin.TREENODE_DISPLAY_MODE_INDENTATION
# use TreeNodeForm to automatically exclude invalid parent choices
form = TreeNodeForm
admin.site.register(Category, CategoryAdmin)You can use a custom cache backend by adding a treenode entry to settings.CACHES, otherwise the default cache backend will be used.
CACHES = {
"default": {
"BACKEND": "django.core.cache.backends.filebased.FileBasedCache",
"LOCATION": "...",
},
"treenode": {
"BACKEND": "django.core.cache.backends.locmem.LocMemCache",
},
}class YoursForm(TreeNodeForm):
class Meta:
widgets = {
'tn_parent': TreeWidget(attrs={'style': 'min-width:400px'}),
}
deletedelete_treeget_ancestorsget_ancestors_countget_ancestors_pksget_ancestors_querysetget_breadcrumbsget_childrenget_children_countget_children_pksget_children_querysetget_depthget_descendantsget_descendants_countget_descendants_pksget_descendants_querysetget_descendants_treeget_descendants_tree_displayget_first_childget_indexget_last_childget_levelget_orderget_parentget_parent_pkset_parentget_pathget_priorityset_priorityget_rootget_root_pkget_rootsget_roots_querysetget_siblingsget_siblings_countget_siblings_pksget_siblings_querysetget_treeget_tree_displayis_ancestor_ofis_child_ofis_descendant_ofis_first_childis_last_childis_leafis_parent_ofis_rootis_root_ofis_sibling_ofupdate_tree
Delete a node if cascade=True (default behaviour), children and descendants will be deleted too,
otherwise children's parent will be set to None (then children become roots):
obj.delete(cascade=True)Delete the whole tree for the current node class:
cls.delete_tree()Get a list with all ancestors (ordered from root to parent):
obj.get_ancestors(include_self=True, depth=None)
# or
obj.ancestorsGet the ancestors count:
obj.get_ancestors_count(include_self=True, depth=None)
# or
obj.ancestors_countGet the ancestors pks list:
obj.get_ancestors_pks(include_self=True, depth=None)
# or
obj.ancestors_pksGet the ancestors queryset (ordered from parent to root):
obj.get_ancestors_queryset(include_self=True, depth=None)Get the breadcrumbs to current node (included):
obj.get_breadcrumbs(attr=None)
# or
obj.breadcrumbsGet a list containing all children:
obj.get_children()
# or
obj.childrenGet the children count:
obj.get_children_count()
# or
obj.children_countGet the children pks list:
obj.get_children_pks()
# or
obj.children_pksGet the children queryset:
obj.get_children_queryset()Get the node depth (how many levels of descendants):
obj.get_depth()
# or
obj.depthGet a list containing all descendants:
obj.get_descendants(include_self=False, depth=None)
# or
obj.descendantsGet the descendants count:
obj.get_descendants_count(include_self=False, depth=None)
# or
obj.descendants_countGet the descendants pks list:
obj.get_descendants_pks(include_self=False, depth=None)
# or
obj.descendants_pksGet the descendants queryset:
obj.get_descendants_queryset(include_self=False, depth=None)Get a n-dimensional dict representing the model tree:
obj.get_descendants_tree()
# or
obj.descendants_treeGet a multiline string representing the model tree:
obj.get_descendants_tree_display(include_self=False, depth=None)
# or
obj.descendants_tree_displayGet the first child node:
obj.get_first_child()
# or
obj.first_childGet the node index (index in node.parent.children list):
obj.get_index()
# or
obj.indexGet the last child node:
obj.get_last_child()
# or
obj.last_childGet the node level (starting from 1):
obj.get_level()
# or
obj.levelGet the order value used for ordering:
obj.get_order()
# or
obj.orderGet the parent node:
obj.get_parent()
# or
obj.parentGet the parent node pk:
obj.get_parent_pk()
# or
obj.parent_pkSet the parent node:
obj.set_parent(parent_obj)Get the node priority:
obj.get_priority()
# or
obj.priorityAdded the function of decorating a materialized path. The path is formed according to the value of the tn_priority field.
cls.get_path(prefix='', suffix='', delimiter='.', format_str='')Set the node priority:
obj.set_priority(100)Get the root node for the current node:
obj.get_root()
# or
obj.rootGet the root node pk for the current node:
obj.get_root_pk()
# or
obj.root_pkGet a list with all root nodes:
cls.get_roots()
# or
cls.rootsGet root nodes queryset:
cls.get_roots_queryset()Get a list with all the siblings:
obj.get_siblings()
# or
obj.siblingsGet the siblings count:
obj.get_siblings_count()
# or
obj.siblings_countGet the siblings pks list:
obj.get_siblings_pks()
# or
obj.siblings_pksGet the siblings queryset:
obj.get_siblings_queryset()Returns an n-dimensional dictionary representing the model tree. Each node contains a "children"=[] key with a list of nested dictionaries of child nodes.:
cls.get_tree(instance=None)
# or
cls.treeGet a multiline string representing the model tree:
cls.get_tree_display()
# or
cls.tree_displayReturn True if the current node is ancestor of target_obj:
obj.is_ancestor_of(target_obj)Return True if the current node is child of target_obj:
obj.is_child_of(target_obj)Return True if the current node is descendant of target_obj:
obj.is_descendant_of(target_obj)Return True if the current node is the first child:
obj.is_first_child()Return True if the current node is the last child:
obj.is_last_child()Return True if the current node is leaf (it has not children):
obj.is_leaf()Return True if the current node is parent of target_obj:
obj.is_parent_of(target_obj)Return True if the current node is root:
obj.is_root()Return True if the current node is root of target_obj:
obj.is_root_of(target_obj)Return True if the current node is sibling of target_obj:
obj.is_sibling_of(target_obj)Update tree manually, useful after bulk updates:
cls.update_tree()Caching is implemented to optimize the performance of database query results. However, it's important to note that current caching mechanism generates cache keys that do not account for changes in method parameters. This can lead to outdated or incorrect data being served from the cache if the parameters affecting the output of the method change.
For example, method get_descendants_queryset has a parameter include_self. Changing this parameter does not change the cache key. Changing include_self from True to False or vice versa will not invalidate the cache, leading to potential inconsistencies.
To ensure data consistency, it is crucial to manually clear the cache when such parameter changes are made. You can do this by calling the cache clearing method before invoking the method with different parameters:
...
# First call the method
result = instance.get_descendants_queryset(include_self=False)
...
# Manually clear the cache
treenode_cache.clear()
# Now call the method with the updated parameter
result = instance.get_descendants_queryset(include_self=True)
...While automatic cache invalidation mechanisms are planned for future updates, currently, manual cache clearing is necessary to prevent data inconsistencies. Implementing such practices will safeguard against serving outdated or incorrect information from the cache.
Released under MIT License.
The provided code is already being used in production projects, even though I have only done general testing. That is why the risk of using the code lies entirely with you.
Warning: don't access the tree node fields directly! Most of them have been removed as unnecessary. In the future, only tn_parent and tn_priority will be kept. Use the functions described in the documentation above or the documentation for the original application.
This software contains, uses, including in a modified form:
- django-treenode by Fabio Caccamo;
- Select2-to-Tree Select2 extension by clivezhg
Special thanks to Mathieu Leplatre for the advice used in writing this application
Future plans:
- may be will add the ability to determine the priority of the parent by any field, for example, by creation date or alphabetical order;
- drug-and-drop support;
- to be happy, to don't worry, until die.
Your wishes, objections, comments are welcome.