Implementing a hierarchy — combining the Adjacency List and Materialized Path through one-to-many
The storage of hierarchy in MySQL is quite a messy topic, having burned Habr repeatedly, I nevertheless did not find for myself an optimal structure combining ease of support and ease of use. The bicycle was invented by itself ...
Adjacency List (AL) is convenient:
But the main disadvantages arise when sampling:
They do not present any difficulties in solving, but they force us to either hardcode the number of levels or resort to recursion. By and large, you can accept, write a couple of functions with ugly code and forget about it all. But!
Peeping into the Materialized Path idea of storing a full path, I didn’t quite understand, but what prevents you from storing it in an external table with a one-to-many connection? Someone will say that they say " already was ", but there is one significant difference: parent_id !
So. Table pages:
Pages_paths table:
Register dependencies:
Thus, it is possible to “hang” this method on an already existing table with AL and not interfere with the already running application logic.
Inserts and tree changes are performed as with ordinary AL. When deleting the main branch element, the foreign key drags the entire branch and dependencies in the table with paths.
The only intervention is required at the stage of adding new elements and transferring elements between branches. You can hang a trigger, but for greater compatibility with popular hosting, I decided to restrict myself to simple PHP and pull the update from the script.
I tested everything on a table with 1000 entries and 5 levels of nesting. In order not to suffer with his hands, he wrote a simple table scoring:
To get started, you need to initialize the paths for the existing table:
Processing this table on a developer machine took ~ 10 seconds. After that, from the table of paths, you can simply pull up the path to the element by simple queries:
Collect all children (or count their number without JOIN`a):
If we add an item, we just need to update the paths, if we move, we first crash the old branch of the paths (item_id =: id OR parent_id =: id) and update the path in the new one:
Updates within a branch in 100-200 elements fit up to 1 second, which is quite acceptable for my tasks - only the admin will see the delay.
Take a look at PHP Class and Basic SQL .
In conclusion, examples of use ( or the whole ):
')
I would be glad if someone can suggest how to optimize the execution time of a general indexing, the implementation in the form of a MySQL procedure or other smart thoughts.
Adjacency List (AL) is convenient:
- self-sustaining data integrity (ON DELETE CASCADE)
- ease of insertion / transfer of branches (the update affects one parent_id field of one element)
- Ease of getting kids on level 1
But the main disadvantages arise when sampling:
- getting all the children of the branch (for a menu with a limit on the level of nesting)
- getting the total number of children (information in the catalog)
- find the full path to the item (bread crumbs, URL creation).
They do not present any difficulties in solving, but they force us to either hardcode the number of levels or resort to recursion. By and large, you can accept, write a couple of functions with ugly code and forget about it all. But!
Peeping into the Materialized Path idea of storing a full path, I didn’t quite understand, but what prevents you from storing it in an external table with a one-to-many connection? Someone will say that they say " already was ", but there is one significant difference: parent_id !
So. Table pages:
`id` int(10) unsigned NOT NULL AUTO_INCREMENT, `parent_id` int(10) unsigned DEFAULT NULL, `title` varchar(250) DEFAULT NULL, Pages_paths table:
`item_id` int(10) unsigned DEFAULT NULL, `parent_id` int(10) unsigned DEFAULT NULL, `level` tinyint(3) unsigned DEFAULT '0', `order` tinyint(3) unsigned DEFAULT '0', Register dependencies:
ALTER TABLE `pages` ADD CONSTRAINT `pages_ibfk_1` FOREIGN KEY (`parent_id`) REFERENCES `pages` (`id`) ON DELETE CASCADE; ALTER TABLE `pages_paths` ADD CONSTRAINT `pages_paths_ibfk_2` FOREIGN KEY (`parent_id`) REFERENCES `pages` (`id`) ON DELETE CASCADE, ADD CONSTRAINT `pages_paths_ibfk_1` FOREIGN KEY (`item_id`) REFERENCES `pages` (`id`) ON DELETE CASCADE; Thus, it is possible to “hang” this method on an already existing table with AL and not interfere with the already running application logic.
Inserts and tree changes are performed as with ordinary AL. When deleting the main branch element, the foreign key drags the entire branch and dependencies in the table with paths.
The only intervention is required at the stage of adding new elements and transferring elements between branches. You can hang a trigger, but for greater compatibility with popular hosting, I decided to restrict myself to simple PHP and pull the update from the script.
I tested everything on a table with 1000 entries and 5 levels of nesting. In order not to suffer with his hands, he wrote a simple table scoring:
Tree::Fixture( 'pages', 1000, 5 ); To get started, you need to initialize the paths for the existing table:
Tree::GeneratePaths('pages'); Processing this table on a developer machine took ~ 10 seconds. After that, from the table of paths, you can simply pull up the path to the element by simple queries:
SELECT * FROM `pages_paths` pp JOIN `pages` p ON p.`id`=pp.`parent_id` WHERE item_id=:id ORDER BY `order` Collect all children (or count their number without JOIN`a):
SELECT * FROM `pages_paths` pp JOIN `pages` p ON p.`id`=pp.`item_id` WHERE pp.`parent_id`=:id ORDER BY pp.`level`, pp.`order` If we add an item, we just need to update the paths, if we move, we first crash the old branch of the paths (item_id =: id OR parent_id =: id) and update the path in the new one:
Tree::GeneratePaths( 'pages', $id ); Updates within a branch in 100-200 elements fit up to 1 second, which is quite acceptable for my tasks - only the admin will see the delay.
Take a look at PHP Class and Basic SQL .
In conclusion, examples of use ( or the whole ):
// $arr = Tree::GetPath( 'pages', $id ); // $arr = Tree::GetChildren( 'pages', $id ); // $num = Tree::GetChildrenCount( 'pages', $id ); ')
I would be glad if someone can suggest how to optimize the execution time of a general indexing, the implementation in the form of a MySQL procedure or other smart thoughts.
Source: https://habr.com/ru/post/138947/
All Articles