Деревья в sql


Как представить дерево данных в SQL?

Я пишу структуру древовидной структуры данных, которая объединена из дерева и TreeNode. Дерево будет содержать действия root и верхнего уровня данных. Я использую библиотеку пользовательского интерфейса, чтобы представить дерево в форме окна, где я могу привязать дерево к TreeView.

Мне нужно будет сохранить это дерево и узлы в БД. Каким будет лучший способ сохранить дерево и получить следующие функции:

  • Интуитивная реализация.
  • Легкая привязка. Будет легко перемещаться из дерева в структуру БД и обратно (если есть)

У меня было 2 идеи. Во-первых, это сериализация данных в один лайнер в таблице. Второй — сохранить в таблицах, но затем, когда вы перейдете к объектам данных, я потеряю состояния строк в таблице на измененных узлах.

Простейшая реализация — это структура смежности:

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

Другая модель — вложенные наборы:

где lft и rgt — произвольные значения, определяющие иерархию (любой дочерний lft , rgt должен находиться внутри любого родителя lft , rgt )

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

Однако в MySQL это можно улучшить, используя SPATIAL abitilies.

Смотрите эти статьи в своем блоге:

для более подробных объяснений.

Я добавил в закладки этот sl >

Рекомендация от использования таблицы закрытия (она поясняется в слайдах).

Вот сводка (слайд 77):

Я удивлен, что никто не упомянул о решении материализованного пути, которое, вероятно, является самым быстрым способом работы с деревьями в стандартном SQL.

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

Посмотрите на таблицу примеров node:

Чтобы получить дочерние элементы node x, вы можете написать следующий запрос:

Имейте в виду, что путь столбца должен быть проиндексирован, чтобы быстро выполнять предложение LIKE.

Если вы используете PostgreSQL, вы можете использовать ltree , пакет в расширении contrib (по умолчанию), который реализует структуру данных дерева.

Вы можете делать такие запросы, как:

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

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

Если вы только когда-либо обращаетесь ко всему дереву, модель списка смежности затрудняет извлечение всех узлов под корнем без использования рекурсивного запроса. Если вы добавите дополнительный столбец, который ссылается на голову, вы можете сделать SELECT * WHERE head_ > и получить все дерево в одном нерекурсивном запросе, но оно денормализует базу данных.

В некоторых базах данных есть пользовательские расширения, которые упрощают хранение и извлечение иерархических данных, например, Oracle CONNECT BY.

Что-то вроде табличных «узлов», где каждая строка node содержит родительский идентификатор (в дополнение к обычным node данным). Для root родитель имеет значение NULL.

Конечно, это делает поиск детей более трудоемким, но таким образом фактическая база данных будет довольно простой.

Лучший способ, я думаю, действительно состоит в том, чтобы дать каждому node id и parent_id, где родительский id является идентификатором родительского node. Это имеет несколько преимуществ

  • Если вы хотите обновить node, вам нужно только переписать данные этого node.
  • Если вы хотите запросить только определенный node, вы можете получить именно нужную информацию, тем самым имея меньше накладных расходов на подключение к базе данных
  • Многие языки программирования имеют функциональные возможности для преобразования данных mysql в XML или json, что упростит открытие приложения с помощью api.

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

В этом случае, какой лучший способ?

Так как это лучший ответ на вопрос «sql trees» в поиске Google, я постараюсь обновить его с точки зрения сегодняшнего дня (декабрь 2020 года).

Большинство ответов подразумевают, что использование списка смежности является простым и медленным, и поэтому рекомендуют другие методы.

Начиная с версии 8 (опубликовано в апреле 2020 г.) MySQL поддерживает рекурсивные общие табличные выражения (CTE). MySQL немного опоздал на шоу, но это открывает новую опцию.

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

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

В блоге здесь приведены некоторые измерения (которые как предвзятое и Postgres вместо MySQL), но тем не менее, это показывает, что списки смежности не должны быть медленными.

Итак, мой вывод сегодня:

  • Простой список смежности может быть достаточно быстрым, если ядро базы данных поддерживает рекурсию.
  • Сделайте тест с вашими собственными данными и вашим собственным движком.
  • Не доверяйте устаревшим рекомендациям, указывающим на «лучший» метод.

Деревья в sql

статья в процессе доработки

Про деревья в SQL написано достаточно много статей, достаточно набрать это сочетание в любой поисковой системе. Казалось бы, зачем писать еще одну?

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

Как же выглядит древовидная таблица в нашем случае?

CREATE TABLE CATEGORY (
NUM INTEGER NOT NULL,
NAME VARCHAR(40) NOT NULL,
PARENT INTEGER DEFAULT 0 NOT NULL ,
PATH VARCHAR(252) DEFAULT » ,
DEEP SMALLINT DEFAULT 0 NOT NULL ,
CHILDS INTEGER DEFAULT 0 NOT NULL ,
CATVIEWID INTEGER NOT NULL default 0 ,
SORTABC INTEGER );

Деревья в БД

Иерархические структуры данных не просто хранить в реляционных Базах Данных (БД).

Плоская модель таблиц не позволяет гибко работать с вложенными сущностями.

Изыскания на этот счёт давно идут. Ищется способ совместить реляционные свойства и NoSQL, например, сохранив декларативность запросов. Ищется способ хранить гетерогенные структуры в таблицах БД.

Я выложу тут обзор возможных решений известных мне.

Полезное

Начну с полезной ссылки … вдруг вы сами хотите разобраться глубоко в этом вопросе

про хранение деревьев в реляционных БД.

Тут есть почти все, что надо знать для начала работы с этой проблемой.

собаковды рекомендуют; главные идеи

Чаще всего такую тему начинают с одной презентации, известной «всем».

Презентация по моделям данных для хранения «деревяшек» от чувака из Percona — непререкаемых лидеров в вопросах sql движков… и что же они (он) рекомендуют?:

чтобы уловить суть смотрите сразу на слайд № 69. — там сравнение описанных ранее способов.

Есть четыре главных способа:

  • Adjacency List
  • Path Enumeration
  • Nested Sets
  • Closure Table

по сложности операций с данными они имеют разный вес и приходится платить за это разную цену… в этом собственно и дилема — все же лучше прочитать презентацию подробно (для тех кто сразу перелистнул на слайд 69).

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

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

чтобы делать это быстро структура данных должна способствовать, а ведь мы же в БД….реляционной… вот и суть проблемы. пошли дальше.

ClosureTable выглядит наиболее серьёзно — делает все необходимые операции быстро, но ! ClosureTable требует чтобы был специальный индекс, объём данных в котором

N*N, т.е. не линеен (сильно растёт с ростом глубины дерева). Это плата за скорость — иногда ограничивает до полной неприемлемости всего метода.

ClosureTable (CT)

метод с примером описан тут

Итак, метод кажется привлекательным, но не все пользуются, например тут http://stackoverflow.com/questions/7497812/hierarchical-data-in-a-database-recursive-query-vs-closure-tables-vs-graph-da читают его избыточным в устройстве и рекомендуют использовать для решения задачи рекурсивные запросы.

вот еще пример запросов к CT

опять рекомендуют иерархические запросы

рекурсивные запросы — крутая фича БД которая отсутствует в большинстве движков. Она дорого стоит при обработке, хотя меньше чем хранимая процедура с циклами. На ExecutionPlan рекурсивного запроса сложно влиять в процессе оптимизации запроса.

по Mysql есть хорошая книжка «Managing Hierarchical Data in MySQL»

и ClosureTable там нет — «геморно».

ORM = Object Relation Mapper (ing)

Это подмножество решений позволяет отображать наш объектный мир ПО на плоскую реляционную БД. и работать с разными БД в качестве бекендов.

Хранение иерархий может решать на уровне ORM. Так то же имеется ?

PHP

в PHP есть такая шняга штука Doctrine 2. Вот пример кода для ClosureTable

и как бы я не ругал PHP — для него есть не плохие либы…

хорошо, что не php единым — Python

прекрасный язык, прекрасные либы, все самое вкусное… не без магии, но красиво: Peewee http://docs.peewee-orm.com/en/latest/ — мой любимый.

для него есть коллекция расширений, например шикарное расширения для sqlite бекенда:

Парни, именно так надо делать расширения, удобно и понятно. таких расширений надо больше, выше и сильнее ��

TODO пример кода SQL и для peewee

Решения на уровне самой БД

сначала напишу, что сам пользовал.

Transact SQL(MS)

hierarchyid — системный тип базы данных в Transact-SQL

коменты к статье на хабре — не хуже самой статьи отражают проблематику.

PostgresSQL

ltree

в PG из коробки есть хорошая основа для метода «Path Enumeration» за счёт работы с GIST индексами и полем ltree.

метод хорош (не плох), но без либы специальной юзать это не удобно — нужна либа. я не нашёл, круто было бы если бы pqlib сам бы умел… ээх, мечты.

Илон Маск рекомендует:  Вывод линий, алгоритм брезенкема, алгоритм цда

Рекурсивные запросы PG

в PG есть рекурсивные запросы, а значит можно хоть на ушах ходить обходить в глубину, ширину свои структуры с простыми полями parent… это расхолаживает и радует.

Вы скажете: «хорошо, PG умеет это. а я хочу работать в tornado с БД асинхронно, можно это удобно сделать ?». ответ: ДА.

давненько для себя я сделал один вывод: если ты выбрал PG — у тебя все будет. мегаплатформа, он будет расти в твоих глазах вместе с тобой (только не лезь в код, я пробовал… расстроишься).

TODO привести пример рекурсивного запроса по иерархии в PG

Потом напишу что сам НЕ пользовал, но видел глазами:

MySql

Посмотрите тут примеры

Oracle

Послесловие

Как вам матричная форма адресации ? Nested Intervals ?

Исследования в этой области еще имеют потенциал, возможно именно Вы придумаете ещё один самый лучший способ быстро работать с деревом в БД, придумаете свой способ, на базе …. ну не знаю, например на базе математического аппарата теории суперструн ��

PS

хорошая либа для питона

В мои планы входит «сравнить производительность метода recursive select для PG и метода AList из библиотеки tree для Python и метода на ltree поставки PG», но не хватет времени. Тема дляДиплома студенту ?

Библиотека доступа к иерархическим страктурам, хранимым в реляционных БД.

Он утрверждает, по реальным тестам , что масштабируемость до миллиона узлов характерна для SELECT, вставка естественно замедляется при росте дерева «в глубину».

11 Comments on “ Деревья в БД ”

Роман

А чем графовые БД не устраивают? Например, TitanDB. Позволяет эффективно хранить структуры произвольной связности. Лично я использую язык запросов Gremlin (под эгидой TinkerPop), но есть ещё SPARQL, который очень похож на SQL. В последней версии Gremlin тоже поддерживает нечто похожее на sparql. 6e+6 вершин и >18e+6 рёбер на одной машине с 16 гб памяти вполне держит. К вершинам можно присандаливать свойства (которые могут иметь сложную структуру). Есть ORM. Правда, лично для меня он не подошел и пришлось сделать порт Gremlin для Python (https://github.com/windj007/python-gremlin-rest).

Михаил Павлов

Ром, привет.
1) TitanDB в первый раз вижу, спасибо. я как-то графовые бд вот не затронл пока. с него начну.
2) если не в реляционной бд хранить, то уже много решений, тут согласен. Можно привести много примеров. а статья про то, как оставаясь в рамках классической реляционной БД, работать эффективно хотябы с дервьями.
статья обзорно описывает со ссылками известные способы предствления дерева в реляционном виде и показывает, как можно средствами rdbms (возможно уникальными средствами для конкретной БД) решать задачи выбора узлов.

3) мы как-то написали свою хранилку древьев с планаризатором (инкрементальная планаризация по мере изменения дерева делалась, без полного обхода, сохраняли дерево планаризованным)
об этом я написал тут
а тут я попробовал его сконвертировать с питона на JS и для этого даже транслятор пришлось доработать
НО! это оказалось фиговой идеей по сравнению с обычной БД.
в продакшене кроме этой штуки нужно:
* бекапы делать консистентные
* масштабировать как-то так, чтобы не учить никого а дать тупо туториал
* у нас в системе хочется иметь связанные данные хранимые в обычной БД бе выкрутасов
* есть представления, оказывается (внезапно), для которых планаризация это не главное
* чтобы делать рапределенную версию , то это иная стоимостьрешения, а мы уже так делать её не хотим.

получается, что в нашем случае проще всё таки посмотреть в сторону типовой RDBMS.

а графы для нас пока экзотика. по графам у меня вопрос: «а на сколько эффективно вних вообще строятся индексы для сложных запросов типа join join join ? «. я плохо их знаю и хочу занть, есть ли инструменты которые помогают делать аналитику по таким наборам данных ? расскажи плиз, что знаешь.

Роман
Роман

Судя по тому, что ты написал, складывается впечатление, что наоборот, РСУБД вам вообще не подходят. РСУБД проще всех остальных только тем, что там есть ОРМ и привычные термины/подход к проектированию. В свою очередь, ОРМ даёт серьёзный выигрыш только в случае более-менее сложных моделей, когда больше 20 таблиц (зависит от квалификации разработчиков). Подход к проектированию в графовой бд хоть и отличается, но вполне усваивается за считанные дни.

joinjoinjoinjoin*join делается суперэффективно и время исполнения таких запросов не зависит от объёма данных (зависит только от количества инциндентных рёбер того же типа). Это достигается за счёт хранения локальных индексов (в графовой бд в каждой вершине есть свой набор индексов, позволяющий эффективно отбирать соседей). Вот тут приведено исследование авторов TitanDB на эту тему и то, как они в своей БД её решают http://thinkaurelius.com/2012/10/25/a-solution-to-the-supernode-problem/

А какая аналитика тебя интересует?

Михаил Павлов

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

возможно открою для себя после этого целый новый пласт алгоритмов?!

> какая аналитика интересует?
не могу сказать. я бы хотел сделать на основе этой штуки основу и решить на ней свои задачи, создав систему «СУП», мы так её называем. далее я открываю API к системе для внешних сервисов. им понадибится возможно данные в разных формах, не обязательно как я дам.
я бы хотел гибкость здесь.
внешние сервисы будут клепать новые представления и конечно хочется чтобы не они придумывали как сделать индекс и по нему строить. а использовать максимально наш функционал для получения данных.

Роман

Мало что сделанное слишком общим, хорошо работает на всех задачах. Наверное, имеет смысл либо использовать sql-решение, поддерживающее запуск на нескольких узлах (а вообще, каков объём данных предполагается на один сервис в среднем? может быть проще предложить несколько вариантов хранилища, как это делает amazon?), либо предложить разработчикам сервисов конструктор, который будет строить схему БД за них.

Кстати, для кассандры есть ещё какой-то ORM: https://cqlengine.readthedocs.org/en/latest/
Про ничего не могу сказать, я использую официальный драйвер с cql

Михаил Павлов

мне этот «ORM» Серега Алексеев показывал. там промитивно внутри все. не знаю пока я не склонен юзать его. а уж как он — это его дело.
мы тожеифициальный драйвер используем. смотри кстати последний мой пост от вчера/позавчера. про стыковку CQL + Thrift.

Кстати в G+ я постил про выход нового бешеного крутого релиза PG.
который опять не подвел ожидания.

Роман

В том посте про cql+thrift не сказано самое главное: зачем это нужно? Если для интроспекции, то гораздо лучше организовать дополнительное хранилище метаинформации, пусть в той же кассандре. Других идей по поводу применения этого гибрида что то не приходит в голову.

Михаил Павлов

> В том посте про cql+thrift не сказано самое главное: зачем это нужно?

Мне нравится Low level api, он позволяет поверх внешних по отношению к касандре сервисов организовать «свой CQL».
Родной CQL не имеет Join и вообще ограничен. ORM опять же слаб — не то слово.

Можно конечно строить новый CQL поверх CQL, собст…но. Но Low level API позволяет потенциально куда больше.

Для выгрузки данных опять же — очень удобно, практически в потоковом режиме можно данные гнать.

Реально, я проверил их оба и решил «использовать только CQL, по крайней мере пока. А Low level хоть и гибкий — в таком виде, как он сейчас есть, смысла не имеет для нас»

Роман

Thrift — deprecated, это значит, что его нельзя использовать в новых проектах. А Join в Cassandra — признак плохого дизайна базы. Используй иерархические ключи, это эффективно и естественно для неё. Соединение разных таблиц, если всё-таки оно нужно, гораздо лучше имитировать на клиенте, т.к. есть возможность эффективнее использовать асинхронные возможности драйвера, IMHO.

Роман

CQL очень хорошо спроектирован: он позволяет ровно то, что позволяет внутренее устройство кассандры. Если что-то CQL не позволяет, то это либо знак, что не надо это делать с помощью кассандры, либо надо попробовать перепроектировать БД, вынеся минимальную логику на клиентскую часть.

Работа с MySQL. Деревья

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

Структуру данных лучше взять общепринятую — в записи сообщения или рубрики форума содержится идентификатор родителя. Для организации вывода дерева напрашивается рекурсивная функция. Именно так сделано в Phorum’е. Файл include/multi-threads.php содержит функцию thread, которая строит вызывается для каждого корневого сообщения и рекурсивно вызывает себя для ответов на них:

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

Для построения дерева достаточно знать последовательность вывода рубрик и их уровень в дереве. Добавим два поля с этими данными в таблицу: level (TINYINT(4). 127 уровней — хватит?) и sortorder (VARCHAR(128)).

Всё, что нам нужно для построения дерева — это идентификатор рубрики и её родителя. Допустим, мы имеем в каталоге несколько рубрик такого содержания:

Структура дерева, подобие которой мы хотим получить такова:

Правда, данный алгоритм позволит нарисовать дерево, но без веток виде линий, как сделано на этом рисунке. Структура дерева будет нарисована при помощи отступов слева.

Вернёмся ещё раз к таблице id-parent. Это рубрики, уже отсортированные по некоторому признаку, по которому мы хотим сортировать элементы одинакового уровня. Например, по убыванию числа сайтов. Кроме id и родительской рубрики мы знаем и номер каждой из них в данном списке. Выровняем эти номера до нужной длины, добавив слева нули. После этого для каждой рубрики сделаем текстовую строку с номерами всех её родителей от самого корня:

При сортировке по полю sortorder мы получим именно то, что нам нужно:

Отступ слева делается, учитывая поле level.

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

Илон Маск рекомендует:  Рамка с поворотом

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

Отмечу, что данный алгоритм не зацикливается при наличии строк с битым полем parent и не пропускает их, а делает корневыми. Рекурсивный алгоритм их просто пропустит.

После выполнения этого цикла мы имеем массивы «id => level» и «id => sortorder». Отправляем в базу всего один запрос, пользуясь внутренними функциями MySQL ELT и FIND_IN_SET:

Конечно же, в отличие от дерева рубрик каталога, в большом форуме много сообщений. Передёргивать их всех при добавлении одного нового нет смысла.

В форумах чаще всего используется сортировка по дате написания сообщения. Поэтому поле sortorder можно смело делать из своего и родительского timestamp’а, выровненного функцией str_pad до 11-значной длины.

Как представить дерево данных в SQL?

Я пишу структуру дерева данных, объединенную из дерева и дерева-дерева. Дерево будет содержать действия корня и верхнего уровня над данными.
Я использую библиотеку пользовательского интерфейса, чтобы представить дерево в форме windows, где я могу привязать дерево к TreeView.

Мне нужно будет сохранить это дерево и узлы в БД.
Каким будет лучший способ сохранить дерево и получить следующие возможности:

  1. Интуитивная реализация.
  2. Легкая вязка. Будет легко перемещаться из дерева в структуру БД и обратно (если есть)

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

8 ответов

Лучший способ, я думаю, действительно должен дать каждому узлу идентификатор и parent_id, где Родительский идентификатор является идентификатором родительского узла. Это имеет несколько преимуществ

  1. Если вы хотите обновить узел, вам нужно только перезаписать данные этого узла.
  2. Когда вы хотите запросить только определенный узел, вы можете получить именно ту информацию, которую вы хотите, таким образом, имея меньше затрат на подключение к базе данных
  3. Многие языки программирования имеют функциональность для преобразования данных mysql в XML или json, что облегчит открытие приложения с помощью api.

Если вы используете PostgreSQL , который вы можете использовать ltree , пакет в расширении contrib (поставляется по умолчанию), который реализует древовидную структуру данных.

Вы можете делать такие запросы, как:

Самая простая реализация- структура списка смежности:

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

Другая модель-вложенные наборы:

где lft и rgt являются произвольными значениями, определяющими иерархию (любой дочерний lft , rgt должен быть в пределах любого родительского lft , rgt )

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

Однако, в MySQL этом можно улучшить используя SPATIAL abitilies.

Смотрите эти статьи в моем блоге:

для более детальных объяснений.

Поскольку это лучший ответ на вопрос «деревья sql» в поиске google, я попытаюсь обновить это с точки зрения сегодняшнего дня (декабрь 2020).

Большинство ответов подразумевают, что использование списка смежности является простым и медленным, и поэтому рекомендуют другие методы.

Начиная с версии 8 (опубликовано апрель 2020) MySQL поддерживает рекурсивные общие табличные выражения (CTE) . MySQL немного опоздал к шоу, но это открывает новую опцию.

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

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

Блог здесь дает некоторые измерения (которые и предвзяты и для postgres вместо MySQL), но тем не менее он показывает, что списки смежности не должны быть медленными.

Таким образом, мой вывод сегодня:

  • Простой список смежности может быть достаточно быстрым, если компонент database engine поддерживает рекурсию.
  • Сделайте тест с вашими собственными данными и вашим собственным двигателем.
  • Не доверяйте устаревшим рекомендациям, чтобы указать «лучший» метод.

Что-то вроде таблицы «узлы», где каждая строка узла содержит Родительский id (в дополнение к обычным данным узла). Для root родительское значение равно NULL.

Конечно, это делает поиск детей немного более трудоемким, но таким образом фактическая база данных будет довольно простой.

Я заложил этот sl >

Там рекомендуется использовать таблицу закрытия (это объясняется в слайдах).

Вот резюме (слайд 77):

Я удивлен, что никто не упомянул о решении materialized path, которое, вероятно, является самым быстрым способом работы с деревьями в стандартном SQL.

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

Посмотрите на пример узла таблицы:

Для получения потомков узла x можно написать следующий запрос:

Имейте в виду, что путь столбца должен быть индексирован, чтобы выполнить fast с предложением LIKE.

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

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

Если вы только когда-либо обращались ко всему дереву, модель списка смежности затрудняет извлечение всех узлов под корнем без использования рекурсивного запроса. Если вы добавляете дополнительный столбец, который связывается с головкой, то вы можете сделать SELECT * WHERE head_ >и получить все дерево в одном нерекурсивном запросе, но он денормализует базу данных.

Некоторые базы данных имеют пользовательские расширения, облегчающие хранение и извлечение наследственных данных, например Oracle имеет CONNECT BY .

Вопрос по sql, hierarchical-data, tree &#8211 Как представить дерево данных в SQL?

Я пишу структуру дерева данных, которая объединена из дерева и TreeNode. Дерево будет содержать корень и действия верхнего уровня на данных. Я использую библиотеку пользовательского интерфейса, чтобы представить дерево в форме окна, где я могу связать дерево с TreeView.

Мне нужно будет сохранить это дерево и узлы в БД. Что будет лучшим способом сохранить дерево и получить следующие возможности:

Интуитивно понятная реализация.Легкая привязка. Будет легко перейти от дерева к структуре БД и обратно (если есть)

У меня было 2 идеи. Первый заключается в сериализации данных в одну строку в таблице. Второе — сохранить в таблицах, но затем при переходе к объектам данных я потеряю состояния строк в таблице на измененных узлах.

я постараюсь обновить его с точки зрения сегодняшнего дня (декабрь 2020 года).

Большинство ответов подразумевают, что использование списка смежности является простым и медленным, и поэтому рекомендуют другие методы.

Начиная с версии 8 (опубликовано в апреле 2020 года) MySQL поддерживаетрекурсивные общие табличные выражения (CTE), MySQL немного опоздал на шоу, но это открывает новую опцию.

Есть учебникВот это объясняет использование рекурсивных запросов для управления списком смежности.

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

БлогВот дает некоторые измерения (которые являются предвзятыми и для postgres вместо MySQL), но тем не менее показывает, что списки смежности не должны быть медленными.

Итак, мой вывод сегодня:

Простой список смежности может быть достаточно быстрым, если ядро ​​базы данных поддерживает рекурсию.Сделайте тест с вашими собственными данными и вашим собственным движком.Не доверяйте устаревшим рекомендациям, указывающим на «лучший» метод.

что лучший способ — дать каждому узлу идентификатор и parent_id, где родительский идентификатор — это идентификатор родительского узла. Это имеет несколько преимуществ

Когда вы хотите обновить узел, вам нужно только переписать данные этого узла.Когда вы хотите сделать запрос только к определенному узлу, вы можете получить именно ту информацию, которую вы хотите, таким образом, имея меньше затрат на соединение с базой данныхМногие языки программирования имеют функции для преобразования данных mysql в XML или json, что облегчит открытие приложения с помощью API.

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

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

Посмотрите на таблицу примеровузел:

Для того, чтобы получить детей узлаxВы можете написать следующий запрос:

Имейте в виду, что колоннадорожка должны быть проиндексированы, чтобы быстро выполнить сЛАЙК пункт.

Дерево в SQL

Всем добрый день. У меня появился такой вопрос. Скажем имеется таблица в которой хранится древовидная структура. Допустим в таблице есть >

3 ответа 3

Возможность создания рекурсивных запросов есть начиная с SQL 1999. Это возможно с помощью оператора WITH. В MS Sql будет выглядеть так:

Если не ошибаюсь, в MySql это работать не будет. Насчет Oracle — не в курсе

@ReinRaus — вместо NS, я бы посоветовал использовать Materialized path ( PostgreSQL Ltree ). У NS возникают большие нагрузки при перемещении узла с большим количеством дочерних элементов, так как для каждого элемента необходимо пересчитать левый и правый ключи.

По стандарту вроде нельзя. Для Oracle, PostgresSQL есть реализация древовидных запросов. В MS sql server’e вроде от версии зависит, в новых вроде появилась возможность но не уверен. По стандарту можно только если костылями со вложенными запросами ограничив по уровню вложенности например так:

Всё ещё ищете ответ? Посмотрите другие вопросы с метками дерево sql или задайте свой вопрос.

Похожие

Подписаться на ленту

Для подписки на ленту скопируйте и вставьте эту ссылку в вашу программу для чтения RSS.

дизайн сайта / логотип © 2020 Stack Exchange Inc; пользовательское содержимое попадает под действие лицензии cc by-sa 4.0 с указанием ссылки на источник. rev 2020.11.12.35403

Как представить дерево данных в SQL?

Я пишу структуру дерева данных, которая объединена из дерева и TreeNode. Дерево будет содержать корень и действия верхнего уровня на данных. Я использую библиотеку пользовательского интерфейса, чтобы представить дерево в форме окна, где я могу связать дерево с TreeView.

Илон Маск рекомендует:  Что такое код ingres_field_length

Мне нужно будет сохранить это дерево и узлы в БД. Что будет лучшим способом сохранить дерево и получить следующие возможности:

  1. Интуитивно понятная реализация.
  2. Легкая привязка. Будет легко перейти от дерева к структуре БД и обратно (если есть)

У меня было 2 идеи. Первый заключается в сериализации данных в одну строку в таблице. Второе — сохранить в таблицах, но затем при переходе к объектам данных я потеряю состояния строк в таблице на измененных узлах.

8 ответов

Самая простая реализация — это структура списка смежности :

Однако некоторые базы данных, в частности MySQL , имеют некоторые проблемы с обработкой этой модели, потому что она требует способности выполнять рекурсивные запросы, которых нет в MySQL .

Еще одна модель это вложенные множества :

где rgt и rgt — произвольные значения, которые определяют иерархию ( rgt , rgt любого дочернего rgt должен быть в пределах rgt , rgt любого родителя)

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

Тем не менее, в MySQL это можно улучшить с помощью SPATIAL abitilies.

Смотрите эти статьи в моем блоге:

для более подробных объяснений.

Я добавил в закладки этот слайдшоу об SQL-Antipatterns, в котором обсуждаются несколько альтернатив: http://www.sl >

Исходя из этого, рекомендуется использовать таблицу закрытия (это объясняется на слайдах).

Вот резюме (слайд 77):

Я удивлен, что никто не упомянул решение с материализованным путем , которое, вероятно, является самым быстрым способом работы с деревьями в стандартном SQL.

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

Посмотрите на пример таблицы:

Чтобы получить дочерние элементы узла x , вы можете написать следующий запрос:

Имейте в виду, что путь к столбцу должен быть проиндексирован, чтобы быстро выполнять предложение LIKE .

Если вы используете PostgreSQL, вы можете использовать ltree , пакет в расширении contrib (поставляется по умолчанию), который реализует древовидную структуру данных.

Вы можете делать запросы как:

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

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

Если вы когда-либо обращаетесь только ко всему дереву, модель списка смежности затрудняет извлечение всех узлов в корне без использования рекурсивного запроса. Если вы добавите дополнительный столбец, который ссылается на SELECT * WHERE head_ > вы можете выполнить SELECT * WHERE head_ > и получить все дерево одним нерекурсивным запросом, но он денормализует базу данных.

Некоторые базы данных имеют пользовательские расширения, которые упрощают хранение и извлечение иерархических данных, например, Oracle имеет CONNECT BY .

Что-то вроде таблицы «узлов», где каждая строка узла содержит родительский идентификатор (в дополнение к обычным данным узла). Для root родитель является NULL.

Конечно, это делает поиск детей немного более трудоемким, но в этом случае фактическая база данных будет довольно простой.

Я думаю, что лучший способ — дать каждому узлу идентификатор и parent_id, где родительский идентификатор — это идентификатор родительского узла. Это имеет несколько преимуществ

  1. Когда вы хотите обновить узел, вам нужно только переписать данные этого узла.
  2. Когда вы хотите сделать запрос только к определенному узлу, вы можете получить именно ту информацию, которую вы хотите, таким образом, имея меньшую нагрузку на соединение с базой данных
  3. Многие языки программирования имеют функции для преобразования данных mysql в XML или json, что облегчит открытие приложения с помощью API.

Так как это лучший ответ на вопрос «sql trees» в поиске Google, я постараюсь обновить его с точки зрения сегодняшнего дня (декабрь 2020 года).

Большинство ответов подразумевают, что использование списка смежности является простым и медленным, и поэтому рекомендуют другие методы.

Начиная с версии 8 (опубликовано в апреле 2020 г.) MySQL поддерживает рекурсивные общие табличные выражения (CTE) . MySQL немного опоздал на шоу, но это открывает новую опцию.

Здесь есть руководство, которое объясняет использование рекурсивных запросов для управления списком смежности.

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

В этом блоге приводятся некоторые измерения (которые являются предвзятыми и для postgres вместо MySQL), но, тем не менее, показывают, что списки смежности не должны быть медленными.

Итак, мой вывод сегодня:

  • Простой список смежности может быть достаточно быстрым, если ядро базы данных поддерживает рекурсию.
  • Сделайте тест с вашими собственными данными и вашим собственным движком.
  • Не доверяйте устаревшим рекомендациям, указывающим на «лучший» метод.

Как представить дерево данных в SQL?

Я пишу структуру дерева данных, объединенную из дерева и дерева-дерева. Дерево будет содержать действия корня и верхнего уровня над данными.
Я использую библиотеку пользовательского интерфейса, чтобы представить дерево в форме windows, где я могу привязать дерево к TreeView.

Мне нужно будет сохранить это дерево и узлы в БД.
Каким будет лучший способ сохранить дерево и получить следующие возможности:

  1. Интуитивная реализация.
  2. Легкая вязка. Будет легко перемещаться из дерева в структуру БД и обратно (если есть)

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

8 ответов

Лучший способ, я думаю, действительно должен дать каждому узлу идентификатор и parent_id, где Родительский идентификатор является идентификатором родительского узла. Это имеет несколько преимуществ

  1. Если вы хотите обновить узел, вам нужно только перезаписать данные этого узла.
  2. Когда вы хотите запросить только определенный узел, вы можете получить именно ту информацию, которую вы хотите, таким образом, имея меньше затрат на подключение к базе данных
  3. Многие языки программирования имеют функциональность для преобразования данных mysql в XML или json, что облегчит открытие приложения с помощью api.

Если вы используете PostgreSQL , который вы можете использовать ltree , пакет в расширении contrib (поставляется по умолчанию), который реализует древовидную структуру данных.

Вы можете делать такие запросы, как:

Самая простая реализация- структура списка смежности:

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

Другая модель-вложенные наборы:

где lft и rgt являются произвольными значениями, определяющими иерархию (любой дочерний lft , rgt должен быть в пределах любого родительского lft , rgt )

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

Однако, в MySQL этом можно улучшить используя SPATIAL abitilies.

Смотрите эти статьи в моем блоге:

для более детальных объяснений.

Поскольку это лучший ответ на вопрос «деревья sql» в поиске google, я попытаюсь обновить это с точки зрения сегодняшнего дня (декабрь 2020).

Большинство ответов подразумевают, что использование списка смежности является простым и медленным, и поэтому рекомендуют другие методы.

Начиная с версии 8 (опубликовано апрель 2020) MySQL поддерживает рекурсивные общие табличные выражения (CTE) . MySQL немного опоздал к шоу, но это открывает новую опцию.

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

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

Блог здесь дает некоторые измерения (которые и предвзяты и для postgres вместо MySQL), но тем не менее он показывает, что списки смежности не должны быть медленными.

Таким образом, мой вывод сегодня:

  • Простой список смежности может быть достаточно быстрым, если компонент database engine поддерживает рекурсию.
  • Сделайте тест с вашими собственными данными и вашим собственным двигателем.
  • Не доверяйте устаревшим рекомендациям, чтобы указать «лучший» метод.

Что-то вроде таблицы «узлы», где каждая строка узла содержит Родительский id (в дополнение к обычным данным узла). Для root родительское значение равно NULL.

Конечно, это делает поиск детей немного более трудоемким, но таким образом фактическая база данных будет довольно простой.

Я заложил этот sl >

Там рекомендуется использовать таблицу закрытия (это объясняется в слайдах).

Вот резюме (слайд 77):

Я удивлен, что никто не упомянул о решении materialized path, которое, вероятно, является самым быстрым способом работы с деревьями в стандартном SQL.

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

Посмотрите на пример узла таблицы:

Для получения потомков узла x можно написать следующий запрос:

Имейте в виду, что путь столбца должен быть индексирован, чтобы выполнить fast с предложением LIKE.

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

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

Если вы только когда-либо обращались ко всему дереву, модель списка смежности затрудняет извлечение всех узлов под корнем без использования рекурсивного запроса. Если вы добавляете дополнительный столбец, который связывается с головкой, то вы можете сделать SELECT * WHERE head_ >и получить все дерево в одном нерекурсивном запросе, но он денормализует базу данных.

Некоторые базы данных имеют пользовательские расширения, облегчающие хранение и извлечение наследственных данных, например Oracle имеет CONNECT BY .

Деревья в sql

Эта статья о практическом применении деревьев в ваших проектах. На примерах постараюсь показать решения основных задач, с которыми вы, возможно, столкнетесь при проектировании или разработке вашего проекта. В SQL-стандарте для рекурсивных запросов используется CTE. Примеры с CTE будут показаны для СУБД Firebird. Параллельно будут показаны примеры для Oracle, так как в нем синтаксис рекурсивных запросов будет отличаться.

Для наших примеров необходимо создать полигон:

  1. Основную таблицу, в которой будет храниться наше дерево.
  2. Соответствующие индексы и ключи

Простой пример обхода дерева начиная с заданного узла

Вычисление значений для каждого узла с учетом всех его дочерних узлов

В нашем примере мы для каждого узла рассчитаем сумму, максимальное значение и кол-во подузлов.

Понравилась статья? Поделиться с друзьями:
Кодинг, CSS и SQL