MySQL: как найти листья в конкретном узле

Я знаю, что подобные вопросы были размещены здесь много раз, например: Способ Java

У меня огромное количество данных (150k +) в стандартном шаблоне дерева (id, parent_id, some_data)

Вопрос: Как получить листья для данного 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


mysql sql sql-optimization
person WBAR    schedule 09.10.2012    source источник
comment
обратитесь к этому: stackoverflow.com/questions/169817/   -  person AnandPhadke    schedule 09.10.2012
comment
Я хочу снова открыть этот вопрос, потому что хочу присудить guru_florida 50 баллов за усилия! это решение действительно помогло мне и РАБОТАЕТ!   -  person WBAR    schedule 21.10.2012

Ответы (1)


arrow_upward
7
arrow_downward

Невозможно сделать это одним запросом. Даже если бы это было, вероятно, было бы очень неэффективно.

Мы можем сделать это с помощью хранимой процедуры и цикла. С добавленными вами индексами это тоже должно быть довольно быстрым. При этом используются две таблицы, выбирающие узлы из входной таблицы (A) и вставляющие узел и их дочерние элементы в (B). Затем он меняет местами B на A и повторяется до тех пор, пока в A не перестанут существовать нелистовые узлы. Приятно то, что итераций цикла будет столько, сколько их уровней между входным узлом и последним листовым узлом, что в большинстве случаев равно наверное, не так уж и глубоко. Эта хранимая процедура будет быстрее, чем выполнение ее извне в коде.

К вашему сведению, у меня возникли проблемы с моей установкой, обрабатывающей временные таблицы, если вы получите «ошибку 2», удалите временное ключевое слово.

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);

Для тестирования я использовал следующий набор образцов:

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);
person guru_florida    schedule 09.10.2012