Storing Recursive structures in databases

A couple of weeks ago, me and a few friends were discussing the best way of storing a tree or any recursive structure in a database (no no, we aren't perpetual geeks :) we were discussing some possible interview questions that we might fact at job application interviews).

The solution we decided on was a simple on, that we'll have one table to house all the nodes, with a Parent_Node_FK attribute, which will specify the parent of each node. The root node will ofcoarse have a null entry. Traversing/Retrieving the tree from the database in this case would require recursive calls to a function that will get one node at a time, which is obviously not scalable for extremely large trees.

So I sat online to find a more elegant solution. I found a nice one in the article Storing Hierarchical Data in a Database by Gijs Van Tulder, which uses a modified preorder traversal of the tree and stores numbers in the database allocated to each node during the preorder traversal. This reduces the retrieval of the tree from the database to just a single query, which gets all the nodes in one go. You just have to do simple postprocessing to get the actual structure of the tree.A much better approach imo.