Path Enumeration

One weakness of an Adjacency List is that it’s expensive to retrieve the ancestors of a given node in the tree. In Path Enumeration, this is solved by storing the string of ancestors as an attribute of each node.

Path Enumeration in directory hierarchies

We can see a form of Path Enumeration in directory hierarchies. A UNIX path like /usr/local/lib/ is a Path Enumeration of the filesystem, where usr is the parent of local, which in turn is the parent of lib.

Creating Comments table with a path column

To employ the Path Enumeration solution, we can define a column called path as a long VARCHAR, instead of the parent_id column, in the Comments table. The string stored in this column is the sequence of ancestors of the current row, from the top of the tree down, just like a UNIX path. We can even choose / as a separator character.