Dec 02 2008

Основы организации древовидных структур в базах данных (Nested Sets)

Category: Symfony,Разработкаingvar @ 22:46

Подборка материалов по работе с деревьями (Nested Sets) в SQL.

Wikipedia: Иерархические базы данных
Иерархическая модель базы данных состоит из объектов с указателями от родительских объектов к потомкам, соединяя вместе связанную информацию.

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

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

MySQL:

Managing Hierarchical Data in MySQL

Symfony:

http://propel.phpdb.org/trac/wiki/Users/Documentation/1.3/Tree/NestedSet
Symfony 1.1 oraz NestedSet Tree z sfPropelPlugin (Propel 1.3)
http://www.symfony-project.org/plugins/sfPropelActAsNestedSetBehaviorPlugin
Habrahabr: Иерархические структуры данных и Doctrine
http://www.doctrine-project.org/documentation/manual/1_0/en/one-page#hierarchical-data:nested-set
Иерархические структуры данных и Doctrine
http://codeutopia.net/blog/2008/08/30/understanding-doctrines-nestedset-feature/
Drag&Drop Nested Set Editor for Admin Generator
Деревья в admin generator. Переделываем под Propel 1.2
How-to Symfony: Gestion d’un arbre en Propel via les NestedSet — Part 1

Материал на русском:

Метод хранения деревьев в БД — Preordered Tree Traversal (Nested Sets)
Проектирование баз данных: иерархические структуры. Деревья в SQL
Как подружить Zend Framework and Nested Sets
Иерархические структуры данных и производительность
Habrahabr: SQL → Иерархические (рекурсивные) запросы
http://phpclub.ru/faq/Tree/NsFaq
http://phpclub.ru/faq/Tree/FaqSelect
http://phpclub.ru/talk/showthread.php?s=&threadid=98248
Деревья в SQL
Дерево каталогов nested sets (вложенные множества) и управление им
db_tree: хранение древовидных структур в Базах данных
Библиотека для работы с деревьями Nested Sets
Библиотека Максима Полторака phpDBTree 1.4

Материал на английском языке:

http://www.sitepoint.com/article/hierarchical-data-database/
http://labs.adobe.com/technologies/spry/samples/data_region/NestedXMLDataSample.html
http://codeigniter.com/wiki/Nested_sets/
http://wiki.akelos.org/acts-as-nested-set
http://www.ewgenij.net/CakePHP-Tree-Behavior.html
http://book.cakephp.org/view/91/Tree
Рекомендую книгу по теории организации древовидных структур в базах данных на английском языке: Joe Celko’s Trees and Hierarchies in SQL for Smarties (The Morgan Kaufmann Series in Data Management Systems).. В книге описывается теория по организации деревьев, различные алгоритмы, модели, структуры данных и примеры запросов SQL.

DHTML/ Javascript Tree (drag and drop):

Saving a sortable nested list — mootools 1.2
http://habrahabr.ru/blogs/webdev/30302/
http://codethat.com/tree/tree_examples.html
http://www.mattkruse.com/javascript/mktree/
http://www.treeview.net/
http://www.addobject.com/nlstreedemo/demo/contextmenu.htm
http://www.dhtmlgoodies.com/index.html?whichScript=drag-drop-folder-tree
http://mifjs.net/tree/
http://code.google.com/p/jstree/
http://www.dhtmlx.com/docs/products/dhtmlxTree/index.shtml
• • http://www.aequustechnologies.com/webcontent/doc/guide.html
http://alder.sourceforge.net/
http://destroydrop.com/javascripts/tree/
http://www.dynamicdrive.com/dynamicindex1/navigate1.htm
http://jquery.bassistance.de/treeview/demo/
http://code.gosu.pl/
http://developer.yahoo.com/yui/treeview/
http://www.zapatec.com/website/main/products/prod3/demo.jsp
http://www.blueshoes.org/en/javascript/tree/
http://www.dotvoid.com/2007/09/reordering-nested-sets-using-php-and-javascript/
Drag and drop using Ext JS with the CakePHP Tree Behavior
http://dbtree.megalingo.com/web/demo/advanced-edit-mode.cfm
http://www.codethat.com/tree/tree_api.html
http://phoinix.ucoz.ru/publ/1-1-0-16

Tags: , ,

3 Responses to “Основы организации древовидных структур в базах данных (Nested Sets)”

  1. Vit228 says:

    Коллега, если интересно, могу поделиться опытом реализации работы с деревьями на SF1.2 + Propel 1.3 + jQuery

    Конечно сорцы еще сырые, но уже есть для админки виджет по отображению дерева в листбоксе, а так же есть модуль для построения на jQ+AJAX+SF1.2 дерева с возможностью перетаскивания веток + добавление + удаление + редактирование записей.

    Сейчас я прикручиваю inline обработку/валидацию форм, потом немного шлифую и выкладываю на суд общественности.

  2. ingvar says:

    Спасибо, было б интересно посмотреть на реализацию. А для какой цели используете деревья?

  3. rpsblog.com » A week of symfony #101 (1->7 december 2008) says:

    […] ?Основы организации древовидных структур в базах данных (Nested Sets) […]

Leave a Reply