The problem of sorting the trees in the Materialized Path: how best to implement?

0 like 0 dislike
30 views
Hello!


Began to study the algorithm for constructing tree structures from Tropashko called Materialized Path and carried away. If you read the Habr, it is possible in principle to understand why this algorithm attracts developers: the sample rate of the subtree.


But I faced a problem: if the DBMS (in the specific case, mysql) to ask to sort a table like:

pathname
.1.Garden
.1.1.Fruits
.1.1.1.Bananas
.1.1.2.Apples
.1.1.3.Oranges
.1.2.Flowers
.1.2.1.Orchids
.1.2.2.Roses
...
.1.2.11.Pions



Now suppose we need to choose a tree to decompose it into the browser

SELECT * FROM our_table ORDER BY path


And we discover that Roses will go after Pions.


Of course, you can resort to recursion... But how to do without it? Comes to mind the idea of adding zeros to the numbers. For example, the path from pions will be something like this: .0001.0002.0011. but it comes out the other side: the DBMS to manipulate the transfer of the branches will be much harder.


And since ready-made libraries for working with trees of Materialized Path I found (I write in PHP), I came with a question here. What would you recommend?
by | 30 views

4 Answers

0 like 0 dislike
To be honest, MySQL I'm not that well know (especially in terms of data types), so I'll try to advise based on experience with PostgreSQL
\r
1) Change the data type of the path. Now, if I understand correctly, is a string — try something binary (similar to PostgreSQL bytea) or Nicodemou (that is, if, for example, by changing the numbers on signs, the code which corresponds to the figure to choose the correct separator, and the entire base while hanging in Unicode all will be sorted correctly). True, it can get some problems using nekrasivyh or illegal characters (in PostgreSQL get out) or with character encoding (Cyrillic can make some confusion and have to use shift).
2) to See if it will work to implement something like type stored PostgreSQL LTree (don't know, does it happen in MySQL)
3) Write your own sorting function (better on C) (don't know, does it happen in MySQL)
by
0 like 0 dislike
What about the fact that it was the field "order"?
\r
ps. github.com/Leemo/kohana-materialized-path
by
0 like 0 dislike
by
0 like 0 dislike
image
by

Related questions

0 like 0 dislike
3 answers
asked Apr 1, 2019 by nepster-web
0 like 0 dislike
3 answers
asked Apr 1, 2019 by nepster-web
0 like 0 dislike
2 answers
asked Mar 26, 2019 by sindrom
110,608 questions
257,186 answers
0 comments
28,757 users