Querying SQLite Tree structure

Question

I have a a database of tables like this:

tree{id,name,parent} content{id,content,parent}

The tree table contains a tree-like structure where if parent is 0 it's the top level element and if it's different, it's the id of the parent from the same table.

The content table has a parentcolumn which is an id from tree table.

What I want is to get is the whole chain of parent-children elements when given an ID for content.

I don't think this is the best structure for the tables and I think I can change this.

What's your take on this, please?

Answer 1

First of all, I'd recommend using parent = NULL rather than zero to indicate a root node, that would allow tree to have a foreign key on parent which references id; referential integrity is useful.

Then you could include a materialized path from the root node to the current node in each row. The materialized path would be a string column that represents the path from a root node to the current node; for your purposes you'd want to use a fixed-width format for each node in the path, then you could ASCIIbetically sort on the paths to pull records out in tree-order (as in this answer).

Suppose you thought 99999 would be enough to cover all your nodes. Then you might have a string path like this:

'00001000110002300042'

That would represent the ID sequence [1, 11, 23, 42] so the node's parent would be 42, the grandparent 23, and so on up to the root of 1. To get the whole branch from a node to the root: grab the path, split it into pieces to get the IDs, and pull out all the nodes at once while sorting on the materialized path to get them out in the right order.

This approach also makes it easy to extract whole subtrees at once: just build the path prefix that matches your desired subtree and do a path LIKE 'pfx%' ORDER BY path, id to pull out the whole subtree with one pass. Also, most databases will use an index for a LIKE expression that is rooted at the beginning (i.e. LIKE 'X%' for some X) so these sorts of queries can be pretty quick. You can also compute the depth of a node with a simple string length and division computation.

You need to do a little bit of extra work to build the materialized paths but not much and they make a lot of tree operations nice and simple while maintaining the advantages of a natural representation of a tree.