Introduction
A common technique to manage hierarchical data in a relational database is to use an Adjacency List model, where you have both an ID column and a Parent ID column in a table. This is easy to understand and maintain but can be difficult or inefficient when you want to retrieve hierarchies of records. The Nested Set model provides an alternative technique for managing this kind of data and is more efficient at reading a hierarchy but requires more work for inserts, updates, deletes and moves. NSTree is a library of ColdFusion code that you may like to use to help manage your hierarchical data using the nested set model.
The current version of the library is 1.0. Please leave any comments on this version here: http://stannard.net.au/blog/index.cfm/2009/6/6/Nested-Set-Trees-in-ColdFusion-v10.
Or you can jump straight to working with the Nested Set Tree objects.
Is this library for you?
The nested set model is extremely efficient when reading the tree, but as the size of the tree grows there is more effort when inserting, deleting and modifying the tree.
This particular implementation is very generic, non-database specific, and with a particular focus on data consistency (there is extensive use of locking to ensure all data changes are atomic and the structure of the hierarchy is maintained). Each of these has a trade off in performance.
So this library is for you if:
- You have a light load for inserts and changes (such as a typical content management system), but might have a heavy load when reading the hierarchy data.
You might have better luck with other techniques if:
- Your database supports hierarchical data structures. For example, if you you use MSSQL 2008 then you can make use of its built in hierarchical data capabilities.
- You are expecting a heavy load on inserts or changes (such as a busy forum application).
- You are expecting the tree to grow to a very large number of nodes (tens of thousands). Reads will continue to be efficient, but inserts and updates will probably be affected
Prerequisites
Before using the library you will need to have a good understanding of the Nested Set data model. See the references below for some good links that describe the Nested Set model in more detail, or just try a search in Google.
About the Code
The functions provided and underlying algorithms are based on a PHP/MySQL implementation by Rolf Brugger (thanks Rolf!) and the Nested Set theory was developed by Joe Celko. This code is also based around creating an additional "partner" table that is used with an existing data table. The library should work in ColdFusion 6.1 and above and any common database but I have only tested in MS SQL Server.
Download the Code
You can download this code from RIAForge
This download file contains the three main Nested Set Tree files in the /nstree/com/nstree directory:
- NestedSetTreeTable.cfc - Represents a database table used for storing nested set tree data.
- NestedSetTree.cfc - Library of functions to manipulate a nested set tree.
- Node.cfc - Represents a node in the tree that also has functions to manipulate the tree.
These are the only files you need when using the library in your own application.
Installing the demo
The following steps should get the demo working for you:
- Download the NSTree code from http://nstree.riaforge.org
- Unzip the file and place the nstree directory somethere in your web path (the demo will run in a subdirectory or in a root directory)
- Create a new database that you can use for this demo (or you can use an existing database)
- Create a ColdFusion datasource that points to your database. The demo uses a default datasource named nstree.
- Run the nstree.mssql.sql or nstree.mysql.sql script (from the root of the demo nstree folder) on your database. This will create two tables named category and categoryNST.
- Open your web browser and browse to the nstree directory.
I only have a MSSQL and MySQL version of the script available at the moment, but see the following section for details of the tables that need to be created.
Understanding the Nested Set Tree tables
This library is based around the concept of having a primary data table and a partner Nested Set Tree (NST) table. To better understand this let's describe the demo category tables:
Primary table: category
| Column Name | Column Type | Description |
|---|---|---|
| categoryId | int, PK | Unique primary key |
| parentCategoryId | int | Reference to parent category record |
| categoryName | varchar(50) | Category name |
Note that the parentCategoryId column is not required to use the NST library, but can be useful to maintain.
For each record in the primary category table you will need to maintain a partner record in a NST table.
Partner table: categoryNST
| Column Name | Column Type | Description |
|---|---|---|
| treeId | int, PK | Unique id for a complete nested set tree. Part of compound primary key. |
| id | int, PK | Unique id of a node within a nested set tree. Part of compound primary key. This column is the foreign key to the primary category table. |
| lft | int | Left index |
| rgt | int | Right index |
Notice that we are using a compound primary key on the treeId and id columns.
The demo script also creates an index on the treeId, id and lft columns. This will significantly improve the performance of most reads to the NST table.
About Locking and Exceptions
The library is designed to be multi-user safe but you will still need to consider locking in your own code that manages the primary data table. The examples that follow will show how you might implement this.
The library has a focus on robustness over performance and additional queries are performed to ensure that operations are valid at the time they are run, such as checking a parent node exists before attempting to append children to it. Exceptions will be thrown if these preconditions are not met.
The library provides four lock related functions that you may use:
| setLockName(name) | Sets the name of the lock. |
| getLockName() | Returns the name of the lock. |
| setLockTimeout(seconds) | Sets the lock timeout. |
| getLockTimeout() | Returns the current lock timeout. |
Functions that read data use a READONLY lock. Functions that change data use an EXCLUSIVE lock.
In your code, you can use locking as follows.
name="#variables.nst.getLockName()#"
timeout="#variables.nst.getLockTimeout()#"
type="exclusive">
<!--- Your code plus calls to the library here --->
</cflock>
The default lock name is "NESTEDSETTREE-NSTTableName-NSTTreeId".
About Transactions
No transactions are implemented within the library. You should implement transactions in the code that uses the library.
Nested Set Tree Node Orientation
The node orientation within the tree uses the following terminology. The directions are from the perspective of 'Node':
Reindex Utility
The demo application also comes with a simple utility for reindexing a table.
Browse to the demo site and click on the Reindex Existing Table link. Here you will see a form where you can specify datasource details, nested set tree table details and source data table details.
Continue to Working with the Nested Set Tree Objects.
