Build a Nested Set Tree without Recursion
Trees in databases can be stored in three main methods: Adjacency List, Matherialized Path & Nested Set. When we want to move from AL to NS , this can be done using recursion (if the database is racially correct). But what to do in the case of MySQL?
In short, then:
For more details, see Comrade. Mikhus [ 1 ] . There is also another Closure Table method, as pointed out by Comrade. resurection , but we will not record it in the trend yet.
In the case of MySQL, we have recursion, but only at the level of stored procedures and even then up to 255 levels . We can also use recursion in a bunch of programming language + DB, but the number of requests here can be amazing. Better to do everything in the database.
')
Googling, we learn that any recursive problem can be solved without it dear [ 4 ] . By asking a similar question, we can try and ... we will succeed! Below we present to your attention the rebuild_nested_set_tree function, which fills in lft and rgt, knowing parent_id.
For simplicity, let's imagine that we have only one tree in the table and there are 8 elements in it. At the input function will receive nothing. Naturally, in the production version we will receive some id vertices of trees at the entrance, which we will take into account in logic. Below we provide only the body of the function to save space, and the full text and queries look at SQLFiddle (thanks to comrade grokru for opening this service).
In general, we find the leftmost top element with filled boundaries and unfilled children, calculate the length of a row of its children, update the boundaries of the elements to our right, and then update the boundaries of its children. All this is done without recursion in an infinite loop, until we run out of borderless elements.
A simple predashka will help us to visualize the process:
Overview of tree storage methods in the database
In short, then:
- AL - when we have a parent stored in a column of type parent_id: '' 1 ''
- MP - the full path to the item is stored in a path type column: '' 1.2.5 ''
- NS [ 2 , 3 ] - a pair of columns lft and rgt, storing the range of all nested elements, for example, the root of a tree of 9 elements will have the left value “1”, and the right one - “18”
For more details, see Comrade. Mikhus [ 1 ] . There is also another Closure Table method, as pointed out by Comrade. resurection , but we will not record it in the trend yet.
MySQL and recursion
In the case of MySQL, we have recursion, but only at the level of stored procedures and even then up to 255 levels . We can also use recursion in a bunch of programming language + DB, but the number of requests here can be amazing. Better to do everything in the database.
')
Googling, we learn that any recursive problem can be solved without it dear [ 4 ] . By asking a similar question, we can try and ... we will succeed! Below we present to your attention the rebuild_nested_set_tree function, which fills in lft and rgt, knowing parent_id.
The function of filling the tree without recursion
For simplicity, let's imagine that we have only one tree in the table and there are 8 elements in it. At the input function will receive nothing. Naturally, in the production version we will receive some id vertices of trees at the entrance, which we will take into account in logic. Below we provide only the body of the function to save space, and the full text and queries look at SQLFiddle (thanks to comrade grokru for opening this service).
Source body function rebuild_nested_set_tree
-- NULL UPDATE tree t SET lft = NULL, rgt = NULL; -- SET @i := 0; UPDATE tree t SET lft = (@i := @i + 1), rgt = (@i := @i + 1) WHERE t.parent_id IS NULL; forever: LOOP -- -- SET @parent_id := NULL; SELECT t.id, t.rgt FROM tree t, tree tc WHERE t.id = tc.parent_id AND tc.lft IS NULL AND t.rgt IS NOT NULL ORDER BY t.rgt LIMIT 1 INTO @parent_id, @parent_right; -- , IF @parent_id IS NULL THEN LEAVE forever; END IF; -- SET @current_left := @parent_right; -- SELECT @current_left + COUNT(*) * 2 FROM tree WHERE parent_id = @parent_id INTO @parent_right; -- SET @current_length := @parent_right - @current_left; -- , UPDATE tree t SET rgt = rgt + @current_length WHERE rgt >= @current_left ORDER BY rgt; -- , UPDATE tree t SET lft = lft + @current_length WHERE lft > @current_left ORDER BY lft; -- SET @i := (@current_left - 1); UPDATE tree t SET lft = (@i := @i + 1), rgt = (@i := @i + 1) WHERE parent_id = @parent_id ORDER BY id; END LOOP; -- RETURN (SELECT MAX(rgt) FROM tree t); What are we doing here?
In general, we find the leftmost top element with filled boundaries and unfilled children, calculate the length of a row of its children, update the boundaries of the elements to our right, and then update the boundaries of its children. All this is done without recursion in an infinite loop, until we run out of borderless elements.
A simple predashka will help us to visualize the process:
Links
- Hierarchical data structures and Doctrine by Mikhus , on Habré, December 10, 2008 - the devices of each of the main methods are well described
- Trees in SQL by Joe Celko, at Intelligent Enterprise, October 20, 2000 (english) - what is Nested Set, compared to the Adjacency List and how to convert from second to first (Joe Celko - nested Set dad)
- Database by Gijs Van Tulder, at sitepoint.com, April 30, 2003 (english) - pictures to describe the distribution logic of the “left” and “right” indices, as well as the specifics of working with different approaches
- Any recursive algorithm can be rewritten as an iterative algorithm ... by community wiki, Kristopher Johnson, at stackoverflow.com, December 11, 2009 (english) - any recursive algorithm can be converted to iterative with a stack
- Source codes for rebuild_nested_set_tree by garex , at sqlfiddle.com, November 25, 2012 - creating a table with a tree, filling in test data and creating a function for moving
- Nested set without recursion: visualization by garex , at slideshare.net, November 25, 2012 - visualization of the algorithm in one of the cycles
Changelog
- Added mention of another method - Closure Table
- In the original data, a typo corrected ("Flush" d. B. Under "Trousers")
- The perversion with having min was removed from the function body and replaced with an adequate order by with limit 1 (but the function still worked correctly, because it moved all the right elements - I was surprised later)
Source: https://habr.com/ru/post/153861/
All Articles