MySQL:如何在特定节点中查找叶子 [英] MySQL: How to find leaves in specific node

问题描述

我知道这类问题已经多次发布在这里，例如:

I know this kind questions has been posted here many times, for exmaple: Java way

我在标准树形模式(id，parent_id，some_data)中有大量数据(150k +)

I have huge amount of data (150k+) in standard tree pattern (id, parent_id, some_data)

问题:如何获取给定node_id的叶子?

Question: How to get leaves for given node_id?

表结构:

CREATE TABLE `DATA_TREE` (
  `ID` int(11) NOT NULL,
  `PARENT_ID` int(11) NOT NULL,
  `DATA` varchar(45) DEFAULT NULL,
  PRIMARY KEY (`ID`),
  UNIQUE KEY `ID_UNIQUE` (`ID`),
  KEY `fk_DATA_TREE_1_idx` (`PARENT_ID`),
  CONSTRAINT `fk_DATA_TREE_1` FOREIGN KEY (`PARENT_ID`) REFERENCES `DATA_TREE` (`ID`) ON DELETE NO ACTION ON UPDATE NO ACTION
) ENGINE=InnoDB DEFAULT CHARSET=utf

数据库:MySQL 5.1.61

推荐答案

无法在单个查询中执行此操作.即使有，效率也可能很低.

There is no way to do this in a single query. Even if there was it would probably be very inefficient.

我们可以使用存储过程和循环来做到这一点.使用添加的索引，它也应该很快.这使用两个表从输入表(A)中选择节点，并将该节点及其子级插入(B).然后，它将B交换为A，并重复执行直到直到A中不再存在非叶节点为止.可喜的是，循环迭代的次数将与输入节点和最后一个叶节点之间的级别相同，在大多数情况下，循环迭代次数为可能没有那么深.此存储过程比在代码中外部进行存储要快.

We can do it with a stored procedure and a loop. With the indexes you added it should be pretty quick too. This uses two tables selecting the nodes from the input table (A) and inserting the node and their children into (B). It then swaps B for A, and repeats until no more non-leaf nodes exist in A. The nice thing is loop iterations would only be as many as their are levels between the input node and the last leaf node, which under most cases is probably not that deep. This stored procedure would be faster than doing it externally in code.

仅供参考，我在安装临时表时遇到了困难，如果遇到错误2"，请删除临时关键字.

FYI I had difficulty with my installation handling temporary tables, if you get a 'error 2' then remove the temporary keyword.

delimiter $$
drop procedure if exists GetLeafNodes $$
create procedure GetLeafNodes(nodeid int)
begin
declare N int default 1;

-- create two working sets of IDs, we'll go back and forth between these two sets
drop temporary table if exists A;
drop temporary table if exists B;
create temporary table A(node int, child int);
create temporary table B(node int, child int);

-- insert our single input node into the working set
insert into A values (null, nodeid);

while (N>0) do
  -- keep selecting child nodes for each node we are now tracking
  -- leaf nodes will end up with the child set to null
  insert into B
  select ifnull(A.child,A.node), tree.ID
    from A
    left outer join DATA_TREE as tree on A.child=tree.parent_id;

  -- now swap A and B
  rename table A to temp, B to A, temp to B;

  -- remove non-leaf nodes from table B
  delete from B;

  -- exit when there are no longer any non-leaf nodes in A
  set N=(select count(*) from A where child is not null);
end while;

-- now output our list of leaf nodes
select node from A;

drop temporary table A;
drop temporary table B;
end $$
DELIMITER ;
call GetLeafNodes(4);

我使用了以下样本集进行测试:

I used the following sample set for testing:

CREATE TABLE `DATA_TREE` (
  `ID` int(11) NOT NULL,
  `PARENT_ID` int(11) NOT NULL,
  PRIMARY KEY (`ID`),
  UNIQUE KEY `ID_UNIQUE` (`ID`),
  KEY `fk_DATA_TREE_1_idx` (`PARENT_ID`)
) ENGINE=InnoDB
;

insert into DATA_TREE values
(1,0),(2,1),(3,1),(4,1),(5,3),(6,3),(7,4),(8,4),(9,4),(10,6),(11,6),(12,7),(13,9),(14,9),(15,12),(16,12),(17,12),(18,14);

这篇关于MySQL:如何在特定节点中查找叶子的文章就介绍到这了，希望我们推荐的答案对大家有所帮助，也希望大家多多支持IT屋！