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

• REW: A consideration for a doubly linked item is that any changes in tree position under this schema would result in no less than 3 updates instead of one. As you state, this is also a big assumption that a forward/reverse binary tree is what was requested.
• Patrick: very true, in my experiences I prefer the update-tax of a doubly-linked list to a single-linked list as I often have to traverse up a tree. but in many instances this would not be necessary
• jcolebrand: It definitely depends on the underlying model. I think that the answer given by Patrick is sufficient if that's the right model.

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.