Well, it is always preferable to use a DBMS that handles data on tree in a natural way, even better when it is specially designed for such purpose, as for example, the Neo4j.
But there are some ways to work on relational DBMS, I will list 4 of them:
1. Adjacent List
Most commonly used solution, each input (record) knows only its top node, see an example of commonly used structure:
Example: Comments on a Blog
In this example, there is a table that stores comments from a blog, there are the main comments, which has no top nodes (they are the "root"), and there are the comments that are responses to another comment, and so on, in a DBMS table, we would have the following situation:
Table: comentarios
id parent_id usuario_id comentario
----------------------------------------------------------------
1 NULL 33 Gostei do seu...
2 1 34 seu comentario foi exc...
3 1 99 Gostei Também...
4 3 34 Que bom que gostou...
5 NULL 80 Que Post Bacana ...
Rendering, we would have something like:
Usuario 33 Comentou: Gostei do seu ...
Usuário 34 Comentou: Seu comentario foi exc...
Usuario 99 Comentou: Gostei Também...
Usuário 34 Comentou: Que bom que gostou...
Usuario 80 Comentou: Que Post Bacana ...
Comments have the same data structure, however they are nested in this way, it is necessary to recursively traverse all data from a certain ID.
POSITIVE POINTS: Easy to implement
NEGATIVES: Difficult to handle in arvores
deep, works well when there are few levels
2. Path Enumerated
Basically the same structure as the example above, but the table contains the path from the root node to itself, see the example:
Table comentarios
id path_to_comment usuario_id comentario
----------------------------------------------------------------
1 / 33 Gostei do seu...
2 /1/2 34 seu comentario foi exc...
3 /1/3 99 Gostei Também...
4 /1/3/4 34 Que bom que gostou...
5 / 80 Que Post Bacana ...
this way we could take the comments below the comment of ID 3
doing something like
SELECT * from comentarios WHERE path_to_comment LIKE '/1/3/%';
POSITIVE POINTS: Easy to implement, faster and more efficient consultation than the Lista Adjacente
NEGATIVES: It is relatively difficult to retrace the path when relocating an element
3. Nested sets
It’s a slightly more complex method, I’m going to give you an overview, because a full answer would greatly prolong a response that is an overview of the methods, so let’s go:
They consist of storing with each node, two numbers (one to the left and one to the right): the one to the left stores a smaller number than the smaller ID of their descendants, and the number to the right stores a larger number than the larger ID of their descendants; then, when making a query, we would have a search scope that in terms of performance would be much more efficient than the other methods, see an image that illustrates this:
POSITIVE POINTS: Much higher performance, ease of atravessar
.
NEGATIVES: Much harder to implement than other methods; performance is not so much higher in SGDB that it does not support recursive queries (example: Mysql)
I recommend you ask a question here at Stackoverflow about this technique, so I or another user can demonstrate you improve such technique
4. Table of Relationship
Basically a "Many-to-many" table that stores all the links of a node with its descendants, similar to the technique of the enumerated path, but a little more flexible and with more performance than such.
P.S. I will improve this answer as soon as possible by citing more examples, but this is a giant subject, and each of the techniques would yield at least one question here in the OS
The nested sets I like very much to navigate all items with "next" and "previous", just sort by the value L to have all items in "read order".
– Bacco
The "Table of Relationship" (closure table) is particularly interesting because it allows you to go hereafter of a tree-like structure - allowing to represent any Directed acyclic graph (DAG).
– mgibsonbr
@mgibsonbr I will improve this answer to include more examples, even being an extensive response, this is a really interesting theme
– hernandev
Sorry for the lack of modesty :) but I’m looking for interesting questions. I’m glad there are people giving interesting and surprisingly good answers. I’ll just disagree with the first sentence. We have numerous reasons to use the RDBMS for this. Examples: Most systems do not need this and having 2 systems increases complexity; trying an unknown but more suitable non-relational DB would probably result in something worse; another DB is not available (Binding for language or possibility of use in deployment); does not perform well other necessary tasks.
– Maniero
@bigown is not necessarily disagreeing with the answer, I share his thought, in a system it is strangely costly to maintain more than one bank, but what he said was that to treat data in tree, it is best to use something specific, but it is not always advisable
– hernandev
I ended up posting a separate answer. The techniques described are the same (after all your answer is quite complete, at first I was not going to put mine), but I organized in a different way. I hope it’s of some use...
– mgibsonbr
@hernandev , waiting for you to finish your answer
– Jefferson Quesado