Skip to main content
This is a pre-production deployment of Warehouse. Changes made here affect the production instance of PyPI (
Help us improve Python packaging - Donate today!

Nested Sets SQL Tree for Python

Project Description


Nested Sets aka Modified Pre-order Tree Traversal (MPTT) SQL tree implemented in Python for MySQL and SQLite. Uses both traversal markup (left, right) and adjacency list parentId for more ad-hoc query flexibility.

Provides tree structure validation and “memorisation” via SQLite :memory: for quick reads.


We want to achieve the following tree. Node is represented by name id → parentId (l, r). To output a tree this way fangorn.test.visualize function can be used.

R 1 → None (1, 18)
└─A1 2 → 1 (2, 5)
  └─B1 3 → 2 (3, 4)
└─A2 4 → 1 (6, 13)
  └─B2 5 → 4 (7, 8)
  └─B3 6 → 4 (9, 12)
    └─C1 7 → 6 (10, 11)
└─A3 8 → 1 (14, 17)
  └─B4 9 → 8 (15, 16)

First we need a table to represent the tree. And we want a tree node to have a name.

import MySQLdb as mysql
conn = mysql.connect(user = 'guest', db = 'test')
  CREATE TABLE `node` (
    `node_id` int(10) unsigned NOT NULL AUTO_INCREMENT,
    `parent_id` int(10) unsigned DEFAULT NULL,
    `l` int(10) unsigned NOT NULL,
    `r` int(10) unsigned NOT NULL,
    `name` varchar(8) NOT NULL,
    PRIMARY KEY (`node_id`),
    KEY `l` (`l`),
    KEY `r` (`r`),
    KEY `parent_id` (`parent_id`),
    CONSTRAINT `node_has_node` FOREIGN KEY (`parent_id`)
      REFERENCES `node` (`node_id`)
  ) ENGINE=InnoDB;

Now we can create tree instance. Note that DAO that the tree relies on is expected to support named DB-API paramstyle (i.e. WHERE node_id = :nodeId). Also transaction control methods are recommended to implement nested transaction support. However test suite requires nested transactions to run. For MySQLdb and sqlite3 there’re compatibility wrappers under fangorn.compat.

import fangorn
from fangorn.compat.mysqldb import Mysqldb as MysqldbWrapper
tree = fangorn.NestedSetsTree(MysqldbWrapper(conn), 'node', ('name',))

rId  = tree.add(dict(name = 'R'))
a1Id = tree.add(dict(name = 'A1'), parentId = rId)
tree.add(dict(name = 'B1'), parentId = a1Id)
a2Id = tree.add(dict(name = 'A2'), parentId = rId)
b2Id = tree.add(dict(name = 'B2'), parentId = a2Id)
b3Id = tree.add(dict(name = 'B3'), prevId = b2Id)
tree.add(dict(name = 'C1'), parentId = b3Id)
a3Id = tree.add(dict(name = 'A3'), parentId = rId)
tree.add(dict(name = 'B4'), parentId = a3Id)

tree.move(a1Id, rId)
tree.move(a3Id, prevId = a2Id)

Now we can play with the tree.

print(tree.isDescendantOf(a2Id, 4)) # False
print(tree.isDescendantOf(a2Id, 6)) # True
print(tree.isDescendantOf(a2Id, 7)) # True
print(tree.isDescendantOf(a2Id, 9)) # False

print([n['name'] for n in tree.getChildren(a2Id)])    # ['B2', 'B3']
print([n['name'] for n in tree.getDescendants(a2Id)]) # ['B2', 'B3', 'C1']
print([n['name'] for n in tree.getPath(7)])           # ['R', 'A2', 'B3', 'C1']

print(tree.getNode(8))   # {'left': 14L, 'right': 17L, 'nodeId': 8L, 'name': 'A3', 'parentId': 1L}
print(tree.getParent(8)) # {'left': 1L, 'right': 18L, 'nodeId': 1L, 'name': 'R', 'parentId': None}
print(tree.getRoot())    # {'left': 1L, 'right': 18L, 'nodeId': 1L, 'name': 'R', 'parentId': None}

tree.edit(1, dict(name = 'RR'))
print(tree.getRoot()) # {'left': 1L, 'right': 18L, 'nodeId': 1L, 'name': 'RR', 'parentId': None}

print([n['name'] for n in tree.getDescendants(a2Id)] # ['B2', 'B3', 'C1'])
print([n['name'] for n in tree.getDescendants(a2Id)] # ['B2'])

For more usage examples look at project’s test suite.

Release History

This version
History Node


History Node


History Node


History Node


Download Files

Download the file for your platform. If you're not sure which to choose, learn more about installing packages.

Filename, Size & Hash SHA256 Hash Help File Type Python Version Upload Date
(52.6 kB) Copy SHA256 Hash SHA256
Source None Feb 19, 2017

Supported By

Elastic Elastic Search Pingdom Pingdom Monitoring Dyn Dyn DNS Sentry Sentry Error Logging CloudAMQP CloudAMQP RabbitMQ Heroku Heroku PaaS Kabu Creative Kabu Creative UX & Design Fastly Fastly CDN DigiCert DigiCert EV Certificate Google Google Cloud Servers