Non-recursive fetch of the entire Adjacency List tree
In general, what I don't like about the Adjacency List is recursion, especially when you need to select a tree, without any restrictions, for example:
Perl code (1)
original
- The entire comment tree;
- Map of site;
- Navigation menu;
- etc.;
Task
Make one query to the database and in one pass collect a single-level list in the desired order.Decision
I still have no idea how to solve such a problem at the database level, but at the application level it’s easy. The main difficulty is that for a certain node we may not yet get its parent and children. Therefore, we will use temporary lists and we will stick them together as needed. I suggest the algorithm in Perl.Perl code (1)
#! / usr / bin / perl use warnings; use strict; # Data is sampled as ORDER BY pid DESC, [ORDER] ASC # Now I won’t use the database for this, but I’ll take the selected list my @select = ( # ID PID ORDER OTHER DATA ... {id => 14, pid => 1, ord => 1, data => 'other data'}, {id => 15, pid => 4, ord => 1, data => 'other data'}, {id => 24, pid => 4, ord => 2, data => 'other data'}, {id => 23, pid => 7, ord => 1, data => 'other data'}, {id => 27, pid => 7, ord => 2, data => 'other data'}, {id => 25, pid => 7, ord => 3, data => 'other data'}, {id => 17, pid => 7, ord => 4, data => 'other data'}, {id => 28, pid => 11, ord => 1, data => 'other data'}, {id => 21, pid => 11, ord => 2, data => 'other data'}, {id => 5, pid => 12, ord => 1, data => 'other data'}, {id => 11, pid => 12, ord => 2, data => 'other data'}, {id => 13, pid => 12, ord => 3, data => 'other data'}, {id => 10, pid => 12, ord => 4, data => 'other data'}, {id => 22, pid => 12, ord => 5, data => 'other data'}, {id => 2, pid => 13, ord => 1, data => 'other data'}, {id => 6, pid => 15, ord => 1, data => 'other data'}, {id => 20, pid => 15, ord => 2, data => 'other data'}, {id => 9, pid => 15, ord => 3, data => 'other data'}, {id => 7, pid => 16, ord => 1, data => 'other data'}, {id => 1, pid => 20, ord => 1, data => 'other data'}, {id => 26, pid => 20, ord => 2, data => 'other data'}, {id => 8, pid => 25, ord => 1, data => 'other data'}, # The most important thing is that root nodes are at the very end {id => 12, pid => 0, ord => 1, data => 'other data'}, {id => 4, pid => 0, ord => 2, data => 'other data'}, {id => 3, pid => 0, ord => 3, data => 'other data'}, {id => 18, pid => 0, ord => 4, data => 'other data'}, {id => 16, pid => 0, ord => 5, data => 'other data'}, {id => 19, pid => 0, ord => 6, data => 'other data'}, ); my% indexes = (); # In this hash, we will store the coordinates of the nodes, (the key of the list, and the order in the list) my% lists = (); # Lists of nodes initially by PID my $ tpid = undef; # Current list PID foreach my $ row (@select) { # It is not known what pid the root nodes may undef, or maybe 0 $ row -> {pid} || = 'root'; # If the current ID of the parent node is not defined, then substitute it $ tpid || = $ row -> {pid}; # Set the node level initially 1 $ row -> {level} = 1; # Insert our node into the PID list push @ {$ lists {$ row -> {pid}}}, $ row; # Put down the coordinate for the node $ indexes {$ row -> {id}} = [$ row -> {pid}, $ # {$ lists {$ row -> {pid}}}]; # If there is already a generated list for the current node ID if ($ lists {$ row -> {id}}) { # For this list, put down the new coordinates, that it will join the current list, # order in the new list, and increase the level by 1 map { $ indexes {$ _-> {id}} -> [0] = $ row -> {pid}; $ indexes {$ _-> {id}} -> [1] + = scalar @ {$ lists {$ row -> {pid}}}; $ _-> {level} ++ } @ {$ lists {$ row -> {id}}}; # Attach a subordinate list to the current push @ {$ lists {$ row -> {pid}}}, @ {$ lists {$ row -> {id}}}; # Delete it as unnecessary delete $ lists {$ row -> {id}}; } # If our current PID does not match the PID of the node, then the list with the current PID is formed to the end if ($ tpid ne $ row -> {pid}) { # Have we had a parent node up to this point, if not, then he will pick up this list # when it comes to him if ($ indexes {$ tpid}) { # Increase the order of nodes in the parent list from the parent node to the end by the number # injected list nodes map { $ indexes {$ _} -> [1] + = scalar @ {$ lists {$ tpid}} } @ {$ lists {$ indexes {$ tpid} -> [0]}} [$ indexes {$ tpid} -> [1] + 1 .. $ # {$ lists {$ indexes {$ tpid} -> [ 0]}}]; # put down new coordinates for nodes of the implemented list, # and level relative to the parent node map { $ indexes {$ _-> {id}} -> [0] = $ indexes {$ tpid} -> [0]; $ indexes {$ _-> {id}} -> [1] + = $ indexes {$ tpid} -> [1] + 1; $ _-> {level} + = $ lists {$ indexes {$ tpid} -> [0]} -> [$ indexes {$ tpid} -> [1]] -> {level}; } @ {$ lists {$ tpid}}; # Implement a list relative to the coordinates of the parent node splice @ {$ lists {$ indexes {$ tpid} -> [0]}}, $ indexes {$ tpid} -> [1] + 1, 0, @ {$ lists {$ tpid}}; # Delete the list as unnecessary delete $ lists {$ tpid}; } # Putting a new PID $ tpid = $ row -> {pid}; } } # We will have a ready-made list under the key that we specified for the root nodes. my @result = @ {$ lists {root}}; # Let's see for verification foreach my $ row (@result) { print $ row -> {id}, "\ t", $ row -> {pid}, "\ t", $ row -> {ord}, "\ t", $ row -> {level}, "\ t ", $ row -> {data}," \ n " } 1;
Explanations
Initial sorting is required only for PID (in reverse order) only because you don’t need to stick the list of root nodes anywhere. Otherwise I would have after the completion of the cycle "dokleit" last spisok.Takzhe I implemented the algorithm has calculated the level of nodes, as in the algorithm Adjacency List of fields for no opredeleniyu.Kstati, in the hash % lists except root will list lists artifacts, nor which are not attached.original