The parent_left and parent_right fields are the implementations of the Nested Set Model. It can apply anywhere a parent_id field is used to refer to another record in the same object. parent_left and parent_right are NOT directly related to parent_id or id. You cannot infer id from the parent_left/right, or vice-versa!
The goal is to create an O(1) efficiency algorithm for finding all of the children of a record. Without parent_left/parent_right, you'd have to find every record with a parent_id of your starting record, then every record with a parent_id of all of those records, and so on indefinitely until you stop finding results. With a large enough hierarchy, the number of queries this requires can quickly explode.
Instead, search for any record with a parent_left greater than your current parent_left, and a parent_right less than your current parent_right. If parent_right - parent_left is 1, you instantly know it has no children even without doing an additional query. Using product.category as an example with this data:
id | parent_left | parent_right | name | parent_id --------------------------------------------------------------- 1 | 1 | 8 | All Products | 2 | 2 | 5 | Saleable | 1 3 | 3 | 4 | Discontinued | 2 4 | 6 | 7 | Components | 1 5 | 9 | 12 | Raw Materials | 6 | 10 | 11 | Misc. Consumables | 5
How do you find all children and sub-children categories for All Products? Using parent_left and parent_right from All Products, the single query would be:
SELECT id, name FROM product_category WHERE parent_left > 1 AND parent_right < 8;
The result is Saleable, Discontinued, and Components. Saleable and Components are both children of All Products directly, and Discontinued is a child of Saleable, making it also a child of All Products.
The parent_left/parent_right computation is still inefficient, because it needs to traverse the entire table through numerous nested calls. They also need to be recomputed every time you add or remove a category, but since product categories tend to stay pretty rigid once they're in place and there aren't that many, it's a worthwhile tradeoff.
Please try to give a substantial answer. If you wanted to comment on the question or answer, just use the commenting tool. Please remember that you can always revise your answers - no need to answer the same question twice. Also, please don't forget to vote - it really helps to select the best questions and answers!
About This Community
|Asked: 9/3/13, 7:48 AM|
|Seen: 2599 times|
|Last updated: 3/16/15, 8:10 AM|