Оптимизированный SQL для древовидных структур

import java.util.*;
StringTokenizer st;
int ans;

public class check { 
   String str="7 + 5";
   StringTokenizer st=new StringTokenizer(str);

   int v1=Integer.parseInt(st.nextToken());
   String op=st.nextToken();
   int v2=Integer.parseInt(st.nextToken());

   if(op.equals("+")) { ans= v1 + v2; }
   if(op.equals("-")) { ans= v1 - v2; }
   //.........
}
35
задан Cade Roux 26 November 2008 в 11:46
поделиться

11 ответов

изучите вложенные наборы модель иерархии. это довольно прохладно и полезно.

13
ответ дан Mladen Prajdic 27 August 2019 в 15:53
поделиться

Это действительно зависит от того, как Вы собираетесь получить доступ к дереву.

Одна умная техника должна дать каждому узлу идентификатор строки, где идентификатор родителя является предсказуемой подстрокой ребенка. Например, родитель мог быть '01', и дети будут '0100', '0101', '0102', и т.д. Таким образом, можно выбрать все поддерево из базы данных сразу с:

SELECT * FROM treedata WHERE id LIKE '0101%';

, поскольку критерий является первоначальной подстрокой, индекс на столбце ID ускорил бы запрос.

16
ответ дан Ned Batchelder 27 August 2019 в 15:53
поделиться

Из всех способов сохранить дерево в RDMS наиболее распространенными являются списки смежности и вложенные наборы. Вложенные наборы оптимизированы для чтений и могут получить все дерево в едином запросе. Списки смежности оптимизированы для записей, и может добавленный к с в простом запросе.

Со смежностью перечисляет каждый узел, имеет столбец, который относится к родительскому узлу, или дочерний узел (другие ссылки возможны). Используя это можно создать иерархию на основе отношений отцов и детей. К сожалению, если Вы не ограничиваете глубину своего дерева, Вы не можете вытянуть все это в одном запросе, и чтение его обычно медленнее, чем обновление его.

С вложенным набором моделируют, инверсия верна, чтение быстро и легко, но обновления становятся сложными, потому что необходимо обслужить систему нумерации. Вложенная модель набора кодирует и происхождение и порядок сортировки путем перечисления всех узлов с помощью основанной на предварительном порядке системы нумерации.

я использовал вложенную модель набора и в то время как это сложно для чтения, оптимизируя большую иерархию, это стоит того. После того как Вы делаете несколько упражнений в вытягивании дерева и нумерации узлов, необходимо приобрести навык его.

Мое исследование в области этого метода, запущенного в этой статье: Руководящие Иерархические Данные в MySQL .

15
ответ дан Paŭlo Ebermann 27 August 2019 в 15:53
поделиться

В продукте я продолжаю работать, мы имеем некоторые древовидные структуры, сохраненные в SQL Server, и используем технику, упомянутую выше для хранения иерархии узла в записи. т.е.

tblTreeNode
TreeID = 1
TreeNodeID = 100
ParentTreeNodeID = 99
Hierarchy = ".33.59.99.100."
[...] (actual data payload for node)

Поддержание иерархия является хитрым битом, конечно, и использует триггеры. Но генерация его на вставлении/удалении/перемещении никогда не является рекурсивной, потому что родитель или иерархия ребенка имеют всю информацию, в которой Вы нуждаетесь.

можно получить всех потомков узла таким образом:

SELECT * FROM tblNode WHERE Hierarchy LIKE '%.100.%'

Вот триггер вставки:

--Setup the top level if there is any
UPDATE T 
SET T.TreeNodeHierarchy = '.' + CONVERT(nvarchar(10), T.TreeNodeID) + '.'
FROM tblTreeNode AS T
    INNER JOIN inserted i ON T.TreeNodeID = i.TreeNodeID
WHERE (i.ParentTreeNodeID IS NULL) AND (i.TreeNodeHierarchy IS NULL)

WHILE EXISTS (SELECT * FROM tblTreeNode WHERE TreeNodeHierarchy IS NULL)
    BEGIN
        --Update those items that we have enough information to update - parent has text in Hierarchy
        UPDATE CHILD 
        SET CHILD.TreeNodeHierarchy = PARENT.TreeNodeHierarchy + CONVERT(nvarchar(10),CHILD.TreeNodeID) + '.'
        FROM tblTreeNode AS CHILD 
            INNER JOIN tblTreeNode AS PARENT ON CHILD.ParentTreeNodeID = PARENT.TreeNodeID
        WHERE (CHILD.TreeNodeHierarchy IS NULL) AND (PARENT.TreeNodeHierarchy IS NOT NULL)
    END

и вот триггер обновления:

--Only want to do something if Parent IDs were changed
IF UPDATE(ParentTreeNodeID)
    BEGIN
        --Update the changed items to reflect their new parents
        UPDATE CHILD
        SET CHILD.TreeNodeHierarchy = CASE WHEN PARENT.TreeNodeID IS NULL THEN '.' + CONVERT(nvarchar,CHILD.TreeNodeID) + '.' ELSE PARENT.TreeNodeHierarchy + CONVERT(nvarchar, CHILD.TreeNodeID) + '.' END
        FROM tblTreeNode AS CHILD 
            INNER JOIN inserted AS I ON CHILD.TreeNodeID = I.TreeNodeID
            LEFT JOIN tblTreeNode AS PARENT ON CHILD.ParentTreeNodeID = PARENT.TreeNodeID

        --Now update any sub items of the changed rows if any exist
        IF EXISTS (
                SELECT * 
                FROM tblTreeNode 
                    INNER JOIN deleted ON tblTreeNode.ParentTreeNodeID = deleted.TreeNodeID
            )
            UPDATE CHILD 
            SET CHILD.TreeNodeHierarchy = NEWPARENT.TreeNodeHierarchy + RIGHT(CHILD.TreeNodeHierarchy, LEN(CHILD.TreeNodeHierarchy) - LEN(OLDPARENT.TreeNodeHierarchy))
            FROM tblTreeNode AS CHILD 
                INNER JOIN deleted AS OLDPARENT ON CHILD.TreeNodeHierarchy LIKE (OLDPARENT.TreeNodeHierarchy + '%')
                INNER JOIN tblTreeNode AS NEWPARENT ON OLDPARENT.TreeNodeID = NEWPARENT.TreeNodeID

    END

еще один бит, проверочное ограничение для предотвращения циклической ссылки в древовидных узлах:

ALTER TABLE [dbo].[tblTreeNode]  WITH NOCHECK ADD  CONSTRAINT [CK_tblTreeNode_TreeNodeHierarchy] CHECK  
((charindex(('.' + convert(nvarchar(10),[TreeNodeID]) + '.'),[TreeNodeHierarchy],(charindex(('.' + convert(nvarchar(10),[TreeNodeID]) + '.'),[TreeNodeHierarchy]) + 1)) = 0))

я также рекомендовал бы триггерам предотвратить больше чем один корневой узел (пустой родитель) на дерево и помешать связанным узлам принадлежать различному TreeIDs (но те немного более тривиальны, чем вышеупомянутое.)

Вы захотите проверить на свой особый случай, чтобы видеть, работает ли это решение приемлемо. Надежда это помогает!

7
ответ дан 27 August 2019 в 15:53
поделиться

Если бы у Вас есть много деревьев в базе данных, и Вы будете только когда-либо выводить целое дерево, я сохранил бы древовидный идентификатор (или идентификатор корневого узла) и родительский идентификатор узла для каждого узла в базе данных, получил бы все узлы для конкретного древовидного идентификатора и процесс в памяти.

Однако при выводе поддеревьев можно только получить поддерево конкретного родительского идентификатора узла, таким образом, или необходимо сохранить все родительские узлы каждого узла, чтобы использовать вышеупомянутый метод или выполнить несколько SQL-запросов, поскольку Вы убываете в дерево (надежда в Вашем дереве нет никаких циклов!), хотя можно снова использовать тот же Подготовленный Оператор (предполагающий то, что узлы имеют тот же тип и все хранятся в единственной таблице) для предотвращения перекомпиляцию SQL, таким образом, это не могло бы быть медленнее, действительно с оптимизациями базы данных, относилось к запросу, это могло быть предпочтительно. Мог бы хотеть запустить некоторые тесты для обнаружения.

, Если Вы только храните одно дерево, Ваш вопрос становится одними из запросов поддеревьев только и второго примененного ответа.

1
ответ дан JeeBee 27 August 2019 в 15:53
поделиться

Существует несколько общих видов запросов против иерархии. Большинство других видов запросов является изменениями на них.

  1. От родителя, найдите всех детей.

    a. На определенную глубину. Например, учитывая моего непосредственного родителя, все дети на глубину 1 будут моими одноуровневыми элементами.

    b. К нижней части дерева.

  2. От ребенка, найдите всех родителей.

    a. На определенную глубину. Например, мой непосредственный родитель является родителями на глубину 1.

    b. На неограниченную глубину.

(a) случаи (определенная глубина) легче в SQL. Особый случай (depth=1) тривиален в SQL. Ненулевая глубина более тверда. Конечная, но ненулевая глубина, может быть сделан через конечное число соединений. (b) случаи, с неопределенной глубиной (к вершине, к нижней части), действительно тверды.

, Если Вы дерево ОГРОМНЫ (миллионы узлов) тогда, Вы находитесь в мире вреда, неважно, что Вы пытаетесь сделать.

, Если Ваше дерево находится под миллионом узлов, просто выберите все это в память и работу над нею там. Жизнь намного более проста в мире OO. Просто выберите строки и создайте дерево, когда строки возвращаются.

, Если Вы имеете Огромный дерево, у Вас есть два варианта.

  • Рекурсивные курсоры для обработки неограниченной выборки. Это означает, что обслуживание структуры является O (1) - просто обновляют несколько узлов, и Вы сделаны. Однако выборка является O (n*log (n)), потому что необходимо открыть курсор для каждого узла с детьми.

  • Умная ""куча", нумерующая" алгоритмы, может закодировать происхождение каждого узла. Как только каждый узел правильно пронумерован, тривиальный ВЫБОР SQL может использоваться для всех четырех типов запросов. Изменения в древовидной структуре, однако, требуют изменения нумерации узлов, делая стоимость изменения довольно высоко по сравнению со стоимостью извлечения.

2
ответ дан S.Lott 27 August 2019 в 15:53
поделиться

Google для "осуществленного пути" или "генетических деревьев"...

1
ответ дан Thomas Hansen 27 August 2019 в 15:53
поделиться

Я - поклонник простого метода хранения идентификатора, связанного с его порожденным:

ID     ParentID
1      null
2      null
3      1
4      2
...    ...

легко поддержать, и очень масштабируемый.

1
ответ дан Galwegian 27 August 2019 в 15:53
поделиться

В Oracle существует ВЫБОР... Оператор BY ПОДКЛЮЧЕНИЯ для получения деревьев.

1
ответ дан Dmitry Khalatov 27 August 2019 в 15:53
поделиться

Эта статья интересна, поскольку она показывает некоторые методы поиска, а также способ сохранить происхождение как полученный столбец. Происхождение предоставляет метод ярлыка для получения иерархии без слишком многих соединений.

0
ответ дан Turnkey 27 August 2019 в 15:53
поделиться
Другие вопросы по тегам:

Похожие вопросы: