How to structure a model to properly and efficiently represent tree-like data on relational databases?

Question

Based on Traversing tree-like data in a relational database using SQL question, I would like to know how the way regularly used to describe tree-like data on relational databases considering physical implications?

I'm assuming that the RDBMS has not special features to handling that other than regular SQL ANSI or common available features.

In doubt I'm always interested on MySQL and PostgreSQL and eventually SQLite.

Answer 1

I believe he is going for something like a binary tree. I would just include three keys that are tied to the unique id of the same table, one for the left, one for the right child, and one for the parent.

i.e.- (very much pseudocode)

TABLE tree
int         id                  autoinc
varchar(16) data_you_care_about
int         parent_id
int         left_child_id
int         right_child_id

FOREIGN KEY parent_id = tree.id
FOREIGN KEY left_child_id = tree.id
FOREIGN KEY right_child_id = tree.id

Answer 2

If each node is truly the same data entity, then the paradigm would still signify one table per entity, and a linking column for the tree traversal where each node is only linked once.

For entities that are linked at multiple points in the tree, a separate linking table or a multiple distinct value column would be used.