VPF::хранение деревьев в базе - Форум программистов

Ramirez

Дата 30.1.2009, 18:41 (ссылка)

(нет голосов)

Загрузка ...

Опытный

Профиль
Группа: Участник
Сообщений: 305
Регистрация: 18.1.2005
Где: Moscow, ExUSSR

Репутация: 4
Всего: 5

Извиняюсь за небольшой оффтоп, но всетаки спрошу здесь: кто какие способы хранения древовидных структур в реляционных бд знает/использует?

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

кто-нибудь ковырял эту тему?

gcc

Дата 30.1.2009, 19:27 (ссылка)

(нет голосов)

Загрузка ...

Агент алкомафии

Профиль
Группа: Участник
Сообщений: 2691
Регистрация: 25.4.2008
Где: %&й

Репутация: 1
Всего: 17

про это видел,
http://gsbelarus.com/gs/modules.php?name=N...cle&sid=314

а связи из вложениями не могут подойти по id с LEFT JOIN и etc?

--------------------

Perl FAQ
freelance
perl, jquery, js, php
perl, jquery

Aslan74

Дата 30.1.2009, 20:42 (ссылка)

(нет голосов)

Загрузка ...

Новичок

Профиль
Группа: Участник
Сообщений: 10
Регистрация: 23.12.2004

Репутация: нет
Всего: нет

связи ID<->ParentID самое очевидное. Вас интересует способ хранения или загрузки?

KSURi

Дата 30.1.2009, 21:25 (ссылка)

(нет голосов)

Загрузка ...

Опытный

Профиль
Группа: Участник
Сообщений: 887
Регистрация: 8.6.2006
Где: Russia

Репутация: 20
Всего: 27

Вопрос скорее в раздел про базы данных

--------------------

Died at Life.pl line 21

gcc

Дата 5.2.2009, 01:21 (ссылка)

(нет голосов)

Загрузка ...

Агент алкомафии

Профиль
Группа: Участник
Сообщений: 2691
Регистрация: 25.4.2008
Где: %&й

Репутация: 1
Всего: 17

не совсем понятно как это сделать

вот есть еще модуль DBIx::Tree

если дерево будет так, то как мне вытащить, рекурсию надо как-то написать на perl?

Код

Код



o- 3
|
+-o- 10
| |
| +-o- 16
| | |
| | +-o- 21
| |
| +-o- 60
|
+-o- 13
| |
| +-o- 73
|
+-o- 30

o- 5
|
+-o- 12

o- 7
|
+-o- 11
| |
| +-o- 26
|
+-o- 47
  |
  +-o- 75

Добавлено @ 01:29
Aslan74, и хранения, и загрузки smile

mysql

UPD:

довольно не плохо описано в модуле DBIx::Tree

Это сообщение отредактировал(а) gcc - 5.2.2009, 02:03

--------------------

Perl FAQ
freelance
perl, jquery, js, php
perl, jquery

Ramirez

Дата 5.2.2009, 12:01 (ссылка)

(нет голосов)

Загрузка ...

Опытный

Профиль
Группа: Участник
Сообщений: 305
Регистрация: 18.1.2005
Где: Moscow, ExUSSR

Репутация: 4
Всего: 5

Цитата(Aslan74 @ 30.1.2009, 20:42

)

связи ID<->ParentID самое очевидное. Вас интересует способ хранения или загрузки?

Вот в том-то и дело, что самое очевидное обычно не самое удобное =(
Вот сколько запросов придется делать чтобы в такой схеме выполнить следующие стандартные операции (рекурсию не рассматриваем):

1. Выбрать дерево целиком (с уровнем каждого элемента)
2. Выбор подчиненных узлов определенного узла
3. Выбор родительской ветки (с уровнями элементов)
4. Выбор ветки в которой участвует заданный узел (с уровнями элементов)

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

Это сообщение отредактировал(а) Ramirez - 5.2.2009, 12:01

gcc

Дата 5.2.2009, 13:22 (ссылка)

(нет голосов)

Загрузка ...

Агент алкомафии

Профиль
Группа: Участник
Сообщений: 2691
Регистрация: 25.4.2008
Где: %&й

Репутация: 1
Всего: 17

в innodb программно как делается, наверное на внешних ключах...

я хотел как раз это сделать на MyISA, мне этот модуль подходит, там еще есть http://search.cpan.org/search?query=DBIx%3...e+&mode=all

--------------------

Perl FAQ
freelance
perl, jquery, js, php
perl, jquery

NuINu

Дата 5.2.2009, 17:05 (ссылка)

(голосов:2)

Загрузка ...

Шустрый

Профиль
Группа: Участник
Сообщений: 131
Регистрация: 19.7.2008

Репутация: 5
Всего: 6

хотите дам реализацию на Rose?

делаем так: база такая

CREATE TABLE nodes (
    id          INTEGER PRIMARY KEY,
    parent_id   INTEGER,
    name        TEXT
);

это для sqlite

создаем объект My::Node

Код


package My::Node;

use base 'My::DB::Object';

__PACKAGE__->meta->setup
(
      table      => 'nodes',
      #columns    => [ qw(id parent_id name) ],
      columns =>
      [
        id      => { type => 'integer', primary_key => 1, not_null => 1 },
        parent_id => { type => 'integer' },
        name      => { type => 'varchar', length => 255 },
      ],

      pk_columns => 'id',

      relationships =>
      [
        parent =>
        {
             type       => 'many to one',
             class      => 'My::Node',
             column_map => { parent_id => 'id' },
        },
        child =>
        {
             type       => 'one to many',
             class      => 'My::Node',
             column_map => { id => 'parent_id' },
        },

      ],

);


package My::Node::Manager;
use base qw(Rose::DB::Object::Manager);

sub object_class { 'My::Node' }

__PACKAGE__->make_manager_methods('nodes');


1;

заполняем:

Код


#!/usr/bin/perl -w

use strict;
use My::Node;

package main;

#подготовим базу для работы с классом My::Node
my @pr_data = (
{id=>3, name => 'my 3'},
{id=>5, name => 'my 5'},
{id=>7, name => 'my 7'},
{id=>10, parent_id=>3, name => 'my 10'},
{id=>11, parent_id=>7, name => 'my 11'},
{id=>12, parent_id=>5, name => 'my 12'},
{id=>13, parent_id=>3, name => 'my 13'},
{id=>16, parent_id=>10, name => 'my 16'},
{id=>21, parent_id=>16, name => 'my 21'},
{id=>26, parent_id=>11, name => 'my 26'},
{id=>30, parent_id=>3, name => 'my 30'},
{id=>47, parent_id=>7, name => 'my 47'},
{id=>60, parent_id=>10,name => 'my 60'},
{id=>73, parent_id=>13, name => 'my 73'},
{id=>75, parent_id=>47, name => 'my 75'}
);  


foreach my $p_d (@pr_data) {
    my $p = My::Node->new(%$p_d);
    $p->save;
    print_node($p);
}

print "Exit\n";

sub print_node {
    my $node = shift;
    print "id: $node->{id}, p_id: $node->{parent_id}, N: $node->{name}\n"
}

получаем выбоку из "леса"

Код


#!/usr/bin/perl -w

use strict;
use Data::Dumper;
#unshift (@INC, ".");
use My::Node;


package main;

#Теперь обработаем всю базу, начнем с узлов не имющих предков!!!

my %query =
(
      parent_id  => undef
);

my @q = (%query);
my $rez = My::Node::Manager->get_nodes(
    query   => \@q,
    multi_many_ok   => 1,
);


foreach my $cur (@$rez) {
    print "Tree: $cur->{id}\n";
    print_node($cur);
    node_child_walk($cur->{id});
    print "\n";
}
print "Exit\n";

sub node_child_walk {
    my $cur_id = shift;
    my $lev    = shift || 0;
    $lev++;
    
    my %query =
    (
      parent_id  => $cur_id
    );

    my @q = (%query);
    my $rez = My::Node::Manager->get_nodes(
    query   => \@q,
    with_objects => [ 'child' ],
    multi_many_ok   => 1,
    );

    foreach my $p (@$rez) {
    print "\t"x($lev);
    print_node($p); 
        #дальше ищем узлы у которых текущий является родителем
    if($p->child) {
        $lev++;
        foreach my $c (@{$p->child}) {
        print "\t"x$lev;
        print_node($c); #распечатка теперь будет в низлежащей функции
        node_child_walk($c->{id}, $lev);
        }
        $lev--;
    }
    }
}


sub print_node {
    my $node = shift;
    my $id   = $node->{id} || '0';
    my $p_id = $node->{parent_id} || '0';
    my $name = $node->{name} || 'unknown';
    print "id: $id, p_id: $p_id, N: $name\n"
}

ну и наблюдаем результ:

Код


$ ./get_child_nodes_04.pl
Tree: 3
id: 3, p_id: 0, N: my 3
        id: 10, p_id: 3, N: my 10
                id: 16, p_id: 10, N: my 16
                        id: 21, p_id: 16, N: my 21
                id: 60, p_id: 10, N: my 60
        id: 13, p_id: 3, N: my 13
                id: 73, p_id: 13, N: my 73
        id: 30, p_id: 3, N: my 30

Tree: 5
id: 5, p_id: 0, N: my 5
        id: 12, p_id: 5, N: my 12

Tree: 7
id: 7, p_id: 0, N: my 7
        id: 11, p_id: 7, N: my 11
                id: 26, p_id: 11, N: my 26
        id: 47, p_id: 7, N: my 47
                id: 75, p_id: 47, N: my 75

Exit

вот такие дела. smile

Это сообщение отредактировал(а) NuINu - 5.2.2009, 17:17

gcc

Дата 5.2.2009, 17:39 (ссылка)

(нет голосов)

Загрузка ...

Агент алкомафии

Профиль
Группа: Участник
Сообщений: 2691
Регистрация: 25.4.2008
Где: %&й

Репутация: 1
Всего: 17

NuINu, кстате, а ORM делает один запрос или несколько маленьких? ну если вытаскивать много данных на одну страницы с разных таблиц?

--------------------

Perl FAQ
freelance
perl, jquery, js, php
perl, jquery

NuINu

Дата 5.2.2009, 17:47 (ссылка)

(нет голосов)

Загрузка ...

Шустрый

Профиль
Группа: Участник
Сообщений: 131
Регистрация: 19.7.2008

Репутация: 5
Всего: 6

по разному
хочешь посмотреть добавь:

package main;
$Rose: smile

B::Object::QueryBuilder::Debug = 1;

sir_nuf_nuf

Дата 5.2.2009, 20:00 (ссылка)

(нет голосов)

Загрузка ...

Опытный

Профиль
Группа: Участник
Сообщений: 920
Регистрация: 6.1.2008

Репутация: 14
Всего: 31

gcc, да несколько она делает.. это только Oracle (ну может еще что то стольже дорогое) умеет делать рекурсивные запросы,
а mysql и postgresql - только за несколько раз

--------------------

Ramirez

Дата 6.2.2009, 10:52 (ссылка)

(нет голосов)

Загрузка ...

Опытный

Профиль
Группа: Участник
Сообщений: 305
Регистрация: 18.1.2005
Где: Moscow, ExUSSR

Репутация: 4
Всего: 5

NuINu, вы предложили все ту-же архитектуру "в лоб" (child <-> parent), просто красиво скрыв реализацию за фреймворком. Но волшебства-то не бывает, например если выбирать ветку дерева БД все равно придется выполнить несколько запросов (на каждый уровень по запросу). Это физическое ограничение выбранной архитектуры данных. Этим конечно можно пренебрегать пока данных не много. А если уровень вложенности 100 или 1000 уровней а количество записей миллионы? И таких проблем у архитектур "в лоб" множество. Решить их можно только использовав другую архитектуру, представив данные в БД другим, более оптимальным способом.

Вопрос, был скорее: как оптимальнее переложить древовидную структуру в БД, чтобы с ней было удобно работать. кто нибудь встречал что-то лучше чем Nested Sets?

NuINu

Дата 6.2.2009, 12:31 (ссылка)

(нет голосов)

Загрузка ...

Шустрый

Профиль
Группа: Участник
Сообщений: 131
Регистрация: 19.7.2008

Репутация: 5
Всего: 6

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

Цитата(Ramirez @ 6.2.2009, 08:52

)

Вопрос, был скорее: как оптимальнее переложить древовидную структуру в БД, чтобы с ней было удобно работать. кто нибудь встречал что-то лучше чем Nested Sets?

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

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

gcc

Дата 8.2.2009, 23:07 (ссылка)

(нет голосов)

Загрузка ...

Агент алкомафии

Профиль
Группа: Участник
Сообщений: 2691
Регистрация: 25.4.2008
Где: %&й

Репутация: 1
Всего: 17

вот еще не мого про DBIx::Tree

http://www.dbpd.com/vault/9810/edb.html

--------------------

Perl FAQ
freelance
perl, jquery, js, php
perl, jquery

gcc

Дата 3.4.2009, 13:56 (ссылка)

(нет голосов)

Загрузка ...

Агент алкомафии

Профиль
Группа: Участник
Сообщений: 2691
Регистрация: 25.4.2008
Где: %&й

Репутация: 1
Всего: 17

я вот сделал это дерево для одно сайтика

а как управлять с помошью HTML форм этим деревом? если я захожу переметсить какой-то раздел, то как это сделать красиво (показаст ьродителя и подродителлей), может с JS как-то? кто делал?

--------------------

Perl FAQ
freelance
perl, jquery, js, php
perl, jquery

0 Пользователей читают эту тему (0 Гостей и 0 Скрытых Пользователей)
0 Пользователей:
« Предыдущая тема \| Perl: Общие вопросы \| Следующая тема »