Pull to refresh

Древовидные СУБД

Lumber room
Приглашаются к обсуждению все, имеющие опыт использования, в качестве хранилища данных, древовидных СУБД. Было бы полезно делится опытом разработки древовидных структур, описанием конкретики построения дерева индексов и алгоритмов полнотекстового поиска информации внутри хранилища данных.

Поскольку любая компьютерная система с целью оптимизации обмена производит обмен между памятью и диском в виде блоков, то атомарным элементом, хранящим данные на диске, является блок. Ни для кого не секрет, что многие СУБД (тот же ORACLE и MSSQL) фактически хранят данные в Б-деревьях. Б-дерево – это набор логически связанных блоков, выстроенных в иерархию, на каждом уровне которой определены блоки, у каждого из которых одинаковое количество уровней потомков. Описание алгоритма работы Б-дерева выходит за рамки данного блога.

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

Приведу несколько примеров использования, из личного опыта, древовидных структур данных (глобалов).
Читать дальше
Total votes 19: ↑12 and ↓7 +5
Views 3.2K
Comments 24

Хранение деревьев в базе данных. Часть первая, теоретическая

PHP *Programming *
Tutorial
Sandbox
Полгода назад написал бандл ClosureTable для фреймворка Laravel 3. Поводом для написания стала вот эта замечательная презентация Билла Карвина о способах хранения и обработки иерархических данных в MySQL с использованием PHP.

Итак. Существует несколько шаблонов проектирования баз данных для хранения и обработки иерархических структур:
  • Adjacency List («список смежности»)
  • Materialized Path («материализованный путь»)
  • Nested Sets («вложенные множества»)
  • Closure Table («таблица связей»)

Читать дальше →
Total votes 47: ↑41 and ↓6 +35
Views 125K
Comments 66

Древовидная (точечная) поддержка моделей в 3D печати

Navigator campus corporate blog
В статье описан личный опыт создания и применения древовидных поддержек при печати сложных объектов на 3D-принтере.



Обычно поддержки создаются при 3D-печати в ПО для генерации gcode, например в Cura, прямо перед генераций gcode. Проще всего на 3D-принтере печатаются объекты в форме пирамиды. Тогда каждый следующий слой ложится на предыдущий и не нависает над пустым пространством. Поддержки позволяют печатать нависающие части объектов, но стандартные поддержки не всегда оптимальны с точки зрения расхода пластика и простоты их последующего отделения от самого объекта, поэтому в этой статье я опишу личный опыт создания и применения древовидных поддержек.
Читать дальше →
Total votes 27: ↑27 and ↓0 +27
Views 44K
Comments 23

Cartesius — метод хранения и извлечения древовидных структур в реляционных базах данных или SQL деревья без червей и тараканов

MySQL *SQL *
Sandbox
Лучше совсем не помышлять об отыскании каких бы то ни было истин, чем делать это без всякого метода. (Рене Декарт)

image

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

Существует много методов от самых примитивных до очень сложных и возможно слишком сложных. Мы не будем описывать их в этой статье. При желании вы можете найти множество прекрасных обзорных статей в интернете “Google forever”.

Мы представляем на суд разработчиков метод Cartesius который основан на представлении иерархической структуры на координатной плоскости где каждый узел имеет свою координату в виде двух параметров ord и dep.
Читать дальше →
Total votes 9: ↑6 and ↓3 +3
Views 9K
Comments 23

Рекурсия на PHP — алгоритм, применение

Abnormal programming *PHP *Algorithms *
Recovery mode
Sandbox
К написанию статьи сподвигли часы раздумий и экспериментов в области построения иерархических списков. Изначально логика обкатывалась на SQL запросах, но в последствии решил реализовать на PHP, дабы снять зависимость от СУБД. На простом примере я покажу как можно пройти от корня иерархии до каждого конечного элемента и обратно, информация скорее для новичков.

Итак, тестовая иерархия, с которой нам предстоит работать:

image

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

Создадим таблицу:

CREATE TABLE [dbo].[Test](
	[uid] [int] IDENTITY(1,1) NOT NULL,  -- уникальное поле, автоинкрементное
	[pid] [int] NULL,                    -- это поле указывает на элемент уровнем выше, содержит uid родителя
	[name] [varchar](255) NULL,
	[access] [varchar](50) NULL,         -- права доступа
) ON [PRIMARY]
Читать дальше →
Total votes 20: ↑4 and ↓16 -12
Views 41K
Comments 27