Choose from a table that uses a materialized path to encode a tree ordered by depth (no recursive / liters)

Question

I have a table in a relational database in which I encode a tree using a technique known as a materialized path (also known as a Lineage column). That is, for each node in my tree, I have a row in the table, and for each row I have a row column called ancestry , where I store the path from the root of the node to node represented by this row.

Is it possible, and if so, how, select the rows in the orderd table by pre-order , that is, they should appear in the result set in the order that will be received by visiting the depth-first tree. I use MySQL - so there are no recursive queries and does not have the ltree extension .

For example, the tree, its table, and the selected ones are ordered in order:

  1 SELECT * FROM nodes SELECT * FROM nodes ORDER BY ?depth_first_visit_order? | \ id | ancestry id | ancestry 2 3 ------------- ------------- | | \ 1 | NULL 1 | NULL NOTE: I don't care about the 4 5 6 2 | 1 2 | 1 order of siblings! | 3 | 1 4 | 1/2 7 4 | 1/2 3 | 1 5 | 1/3 5 | 1/3 6 | 1/3 7 | 1/3/5 7 | 1/3/5 6 | 1/3 

Note. I am clearly interested in doing this on a materialized path encoding!
Related: What are the options for storing hierarchical data in a relational database?

Answer 1

I believe you want an alphabetical sort.

 SELECT id, ancestry, ancestry + '/' + CAST(id as nvarchar(10)) AS PathEnumeration FROM nodes ORDER BY 3 ASC; 

I really don't remember how MySQL is concatenated, but I'm sure my meaning is clear.

 1 1/2 1/2/4 1/3 1/3/5 1/3/5/7 1/3/6 

Please note that this is an alphabetical view, so 11 will be displayed before 2. But you said that you do not care about the order of brothers and sisters. Of course, I would rewrite it as a nested set;)

Answer 2

this will order the last number of your "pedigree"

 select *, Substring(ancestry,LEN(ancestry) - Charindex('/',Reverse(ancestry))+2, LEN(ancestry)) as END_CHAR from nodes order by END_CHAR desc 

I have not tried with numbers greater than 9, you may have to impose on int