Добро пожаловать в форум, Guest  >>   Войти | Регистрация | Поиск | Правила | В избранное | Подписаться
Все форумы / Microsoft SQL Server Новый топик    Ответить
 В дереве избавиться от пустых узлов  [new]
mezzanine
Member

Откуда:
Сообщений: 157
Добрый вечер.

Есть таблица со столбцами "item_id" и "parent_item_id" нужно выбрать записи, но узлы должны иметь листья. Сложность в том что может пустой узел содержать не лист а только пустой узел и так в глубь на неслолько уровней (узел с листьями/пустой узел/пустой узел/...). Написал CTE в котором строю дерево вместе с чем-то в роде XPath и потом анализирюя этот путь выкидываю пустые узлы. Работает трагически медленно, около 20 сек на 2 тыс. записей. Ничего хорошего в голову не идет :(
6 май 17, 22:57    [20463155]     Ответить | Цитировать Сообщить модератору
 Re: В дереве избавиться от пустых узлов  [new]
mezzanine
Member

Откуда:
Сообщений: 157
Еще добавлю что могут быть ситуации:
1. "узел с листьями/пустой узел/пустой узел"
2. "узел с листьями/пустой узел/пустой узел/узел с листьями/пустой узел/пустой узел"
удалять пустые узлы когда в глубину уже нет ни одного узла с листьми. во 2 случае удаляются только 2 последних.
6 май 17, 23:29    [20463184]     Ответить | Цитировать Сообщить модератору
 Re: В дереве избавиться от пустых узлов  [new]
Rankatan
Member

Откуда:
Сообщений: 250
Чем узел с листьями отличается от пустого листа?

Пару примеров бы не помешало.
6 май 17, 23:31    [20463188]     Ответить | Цитировать Сообщить модератору
 Re: В дереве избавиться от пустых узлов  [new]
alexeyvg
Member

Откуда: Moscow
Сообщений: 30741
mezzanine
Написал CTE в котором строю дерево вместе с чем-то в роде XPath и потом анализирюя этот путь выкидываю пустые узлы. Работает трагически медленно, около 20 сек на 2 тыс. записей. Ничего хорошего в голову не идет :(
Выложили бы для начала свой вариант...
7 май 17, 01:36    [20463369]     Ответить | Цитировать Сообщить модератору
 Re: В дереве избавиться от пустых узлов  [new]
alexeyvg
Member

Откуда: Moscow
Сообщений: 30741
mezzanine
строю дерево вместе с чем-то в роде XPath
Для этой задачи разумнее в CTE проталкивать наверх признак наличия листьев.
7 май 17, 01:38    [20463370]     Ответить | Цитировать Сообщить модератору
 Re: В дереве избавиться от пустых узлов  [new]
mezzanine
Member

Откуда:
Сообщений: 157
DECLARE @menu_item_table TABLE (
  menu_menu_item_id INT NOT NULL,
  menu_item_parent_id INT NULL,
  is_category BIT, -- Узел
  name NVARCHAR(100)
);

INSERT INTO @menu_item_table
  SELECT 1, NULL, 1, N'Node 1'
  UNION
  SELECT 2, 1, 0, N'Leaf 1.1'
  UNION
  SELECT 3, 1, 1, N'Node 2'
  UNION
  SELECT 4, 3, 0, N'Leaf 2.1'
  UNION
  SELECT 5, 4, 1, N'Node 3'
  UNION
  SELECT 6, 5, 1, N'Node 4';

WITH menu_tree
AS
(SELECT s.*,
        N'/' + CAST(s.menu_menu_item_id AS VARCHAR(MAX)) AS path,
        1 AS level
  FROM @menu_item_table s
  WHERE s.menu_item_parent_id IS NULL
UNION ALL
SELECT c.*,
       mt.path + N'/' + IIF(c.is_category = 1, CAST(c.menu_menu_item_id AS VARCHAR(MAX)), N'item') AS path,
       mt.level + 1 AS level
  FROM @menu_item_table c
  INNER JOIN menu_tree mt
    ON c.menu_item_parent_id = mt.menu_menu_item_id
    AND c.menu_menu_item_id <> c.menu_item_parent_id)
--
SELECT mit.*, 
       mt.path
  FROM menu_tree mt
  INNER JOIN @menu_item_table mit
    ON mt.menu_menu_item_id = mit.menu_menu_item_id
  OUTER APPLY (SELECT CAST(COUNT(1) AS BIT) is_have_child_item
    FROM menu_tree mtp
    WHERE CHARINDEX(N'/' + CAST(mt.menu_menu_item_id AS NVARCHAR(MAX)) + N'/', mtp.path) > 0
      AND CHARINDEX(N'/item', mtp.path, CHARINDEX(N'/' + CAST(mt.menu_menu_item_id AS NVARCHAR(MAX)) + N'/', mtp.path)) > 0) vmtp
  WHERE mt.is_category = 0 OR (mt.is_category = 1 AND vmtp.is_have_child_item = 1);


Если закоментировать последний WHERE то будут выбираться 2 последних пустых узла без листьев.
7 май 17, 11:37    [20463644]     Ответить | Цитировать Сообщить модератору
 Re: В дереве избавиться от пустых узлов  [new]
Guf
Member

Откуда: Новосибирск
Сообщений: 641
mezzanine,
Как правильно сказал alexeyvg, лучше начинать снизу
WITH [menu_tree]
AS (SELECT [m].*
        FROM @menu_item_table [m]
        WHERE [m].[is_category] = 0
    UNION ALL
    SELECT [m].*
        FROM [menu_tree] [tree]
             INNER JOIN @menu_item_table [m] ON [m].[menu_menu_item_id] = [tree].[menu_item_parent_id]
   )
SELECT DISTINCT *
    FROM [menu_tree] 
11 май 17, 12:36    [20472189]     Ответить | Цитировать Сообщить модератору
Все форумы / Microsoft SQL Server Ответить