How Can I Efficiently Query Descendants and Ancestors in a MySQL Tree Structure?

Single-Query Tree Structure Querying in MySQL

In SQL, tree structures are often stored in tables with columns for ID, data, and parent ID. Retrieving all descendants or ancestors of a specific row can be challenging, especially considering their potentially unknown depth.

Query for Descendants

To retrieve all descendants of a specific row, we can use a technique called Modified Preorder Tree Traversal. As described by Joe Celko in "Trees and Hierarchies in SQL for Smarties," this approach involves creating a recursive common table expression (CTE) with the following structure:

WITH RECURSIVE Descendants AS (
  SELECT id, data, parent_id
  FROM tree_table
  WHERE id = <starting_row_id>
  UNION ALL
  SELECT t.id, t.data, t.parent_id
  FROM Descendants AS T
  JOIN tree_table t ON t.parent_id = T.id
)
SELECT * FROM Descendants;

This CTE recursively identifies all child rows for the given starting row, then continues through the hierarchy until it reaches the leaf nodes.

Query for Ancestors

To retrieve all ancestors of a specific row, we can use a similar approach with a slight modification:

WITH RECURSIVE Ancestors AS (
  SELECT id, data, parent_id
  FROM tree_table
  WHERE id = <starting_row_id>
  UNION ALL
  SELECT t.id, t.data, t.parent_id
  FROM Ancestors AS T
  JOIN tree_table t ON t.id = T.parent_id
)
SELECT * FROM Ancestors;

This CTE recursively identifies all parent rows for the given starting row, then continues upwards through the hierarchy until it reaches the root node.

Example Implementation

A working example of these queries in PHP can be found at: http://www.sitepoint.com/article/hierarchical-data-database/2/

The above is the detailed content of How Can I Efficiently Query Descendants and Ancestors in a MySQL Tree Structure?. For more information, please follow other related articles on the PHP Chinese website!