I need to store the tree in the database, so that the operations of reading its branches, along with all the branches nested in it, would be performed as quickly as possible, and the execution time of the remaining operations: insert, delete, etc. not fundamentally; most importantly, that they were, in principle, realizable. Tell me how it is better to implement?

I understand that in such a situation the best results can be achieved using Closure Table or nested sets , what do you think is better, or another?

MySQL database, but it is desirable to use only standard SQL syntax, without frills, not supported, in other databases.

  • There are bases that can perform recursive cte queries. The whole tree is pulled out in one request. Of the free ones, this is postgres. Well, all well-known commercial can do it. You can also extract the entire tree, gradually removing the child node. Or to make stored procedure for tree retrieval. Maybe nothing panic point about speed. What are such huge tall and branchy trees? - Sergey
  • And there is nothing bad. As long as you yourself do not feel that you are badly crying, no one will convince. - Sergey
  • MySQL database. It is advisable not to use frills not supported in other databases. Reformulated the question. - Vladimir Vladimir
  • Rather, MySQL is a bells and whistles (more precisely, nedonavorot), not supporting SQL standards, even of the last century. So they turned everything upside down :) - Sergey
  • In general, there are several ways to implement hierarchies in a database. For example, this article describes 4. - Alexander Petrov

1 answer 1

If you have most of the operations associated with the read operation, then it is better to use the Nested Set design pattern. In this pattern, you have two fields in each node: the left and right border (lft and rth). Moreover, when inserting and updating, so recalculate the boundaries of tree nodes so that the lft: rth segment of the child in the tree always enters the root node.

post_id | lft | rth 1 | 1 | 14 2 | 2 | 11 3 | 3 | 6 6 | 4 | 5 4 | 7 | 8 7 | 9 | 10 5 | 12 | 13 1 1 <-------------------------------------------> 14 2 2 <----------------------------> 11 3 3 <-----> 6 6 4 <-> 5 4 7 <-> 8 7 9 <-> 10 5 12 <-> 13

In this case, to retrieve all the records of a tree or some node of the tree, it suffices to perform a one-table query.

 SELECT * FROM tbl WHERE lft >= 1 AND rth <= 14

You can use the Closure Table by writing all the links in a separate table, but in this case you will have a two-table query, which is often slower than a query on a single table (as in nested sets).