3

I hope this particular issue was not asked before (could not find any similar question). If so, please, gently link me to the page.

I am working with a tree structure in DB (MySQL - InnoDB) and I have two tables - nodes and node_index. The first table (nodes) keeps actual data, while node_index keeps track of the hierarchical structure. The node_index table (the important part of it) looks like this:

+-------------+-------------+--------+----------+
| node_id     | path        | depth  | order    |
+-------------+-------------+--------+----------+
| 0           | 0           | 1      | 1        |
| 1           | 0.1         | 2      | 1        |
| 2           | 0.2         | 2      | 2        |
| 3           | 0.2.3       | 3      | 1        |
| 4           | 0.2.4       | 3      | 2        |
| 5           | 0.5         | 2      | 3        |
+-------------+-------------+--------+----------+

Node_id is a foreign key to the id in the node table. It is not important what the structure of node table is for the context of this question.

Now, while generating the complete tree, I can simply select everything from node_index ordered by path and I get a correct structure at only one query. The problem is, this does not respect the order setting, because for every parent + level combination, this will order the nodes by their IDs, which I need to change and let the nodes be ordered by the order column. For example, if I swap order values of nodes number 3 and 4, I want them to display on the same place (under their parental node 2), but node 4 will be displayed first. I can not use "ORDER BY path, order", because the path is unique and always overrides the order column. I tried to add one more column, called parent_path, that keeps only the path to the parent and order it by "ORDER BY parent_path, order", but this proved to be wrong, as it groups the levels (first I get all first-level nodes, then all second-level nodes etc.).

So my goal is to get the tree structure correctly (children are under their parents, and then are also sorted by order column, not their IDs) in one query. I could of course use recursion and get the structure in many queries, but if it can be done using one query without the order column, I suppose there could be a way to do this in one query even with the ordering. I am sure someone more skilled in databases may find a way (some sort of selfjoin maybe?).

I have been looking into this for quite some time, googling and searching, but nobody seems to have that problem. Everybody solves it by using many queries recursively, but I expect the DB to get very big, with many levels of depth and I need to generate the tree quite often. I see recursion as an unnecessary burden to the DB.

Sorry if this has been already answered or if I am missing some basic and obvious solution.

Thank you, Jakub

Jakub
  • 35
  • 3
  • See my answer here: [sorting-tree-with-a-materialized-path](http://stackoverflow.com/a/2797724/39430) – D'Arcy Rittich Feb 05 '12 at 23:02
  • @RedFilter I have seen your answer, but I am not sure I understand. Apparently my fault as your solution worked there, but could you please shortly explain how would I use it in my case? Thanks a lot. – Jakub Feb 05 '12 at 23:14

1 Answers1

1

What you can do is create a SortPath column. Normally this would be on something like name, but in your case you want to use the Order column. It's similar to your path column, but the node_id numbers are replaced with your Order numbers.

I have given an example of how to do it in this answer: https://stackoverflow.com/a/2797724/39430.

Community
  • 1
  • 1
D'Arcy Rittich
  • 167,292
  • 40
  • 290
  • 283
  • Sortpath from only the order field may not be a good idea as the id is not required to be unique in the node set, but it inspired me to something different - I created a sortpath by taking the fullpath and repalcing the .nodeId. by .order-nodeId., which works fine - respects both order and parents. The only disadvantage is that when the parent node oreder setting is changed, all the nodes under it in its tree have to be recounted recursively. But yes, thanks, that was the right way to think about it. I accept the answer, thank you. – Jakub Feb 06 '12 at 23:04
  • @Jakub You're right of course, I hadn't thought your case through fully. – D'Arcy Rittich Feb 07 '12 at 12:59