7. Проверка целостности дерева
Так как структура дерева использует неявное подчинение, существует вариант того что дерево может "разлететься", потерять организацию. Для этого используем проверки описанные в первой статье:
- Левый ключ ВСЕГДА меньше правого;
- Наименьший левый ключ ВСЕГДА равен 1;
- Наибольший правый ключ ВСЕГДА равен двойному числу узлов;
- Разница между правым и левым ключом ВСЕГДА нечетное число;
- Если уровень узла нечетное число то тогда левый ключ ВСЕГДА нечетное число, то же самое и для четных чисел;
- Ключи ВСЕГДА уникальны, вне зависимости от того правый он или левый;
Код:
sub check_tree {
# Получаем данные: объект
my ($self, $repair) = @_;
# Результат проверки
my %data;
# Левый ключ ВСЕГДА меньше правого
my $sql = 'SELECT '.($self->{'type'} eq 'M' ?
$self->{'multi'}.' AS multi' : 'COUNT('.$self->{'id'}.') AS num').
' FROM '.$self->{'table'}.
' WHERE '.$self->{'left'}.' >= '.$self->{'right'}.
($self->{'type'} eq 'M' ? ' GROUP BY '.$self->{'multi'} : '');
my $sth = $self->{'DBI'}->prepare($sql); $sth->execute();
while (my $row = $sth->fetchrow_hashref()) {
if ($self->{'type'} eq 'M') {$data{$$row{'multi'}} = 1}
elsif ($$row{'num'} && $$row{'num'} > 0) {$data{'check'} = 'no'}
}
$sth->finish();
# Наименьший левый ключ ВСЕГДА равен 1
# Наибольший правый ключ ВСЕГДА равен двойному числу узлов
$sql = 'SELECT '.($self->{'type'} eq 'M' ? $self->{'multi'}.' AS multi, ' : '').
' COUNT('.$self->{'id'}.') AS num, '.
' MIN('.$self->{'left'}.') AS lk, '.
' MAX('.$self->{'right'}.') AS rk'.
' FROM '.$self->{'table'}.
($self->{'type'} eq 'M' ? ' GROUP BY '.$self->{'multi'} : '');
$sth = $self->{'DBI'}->prepare($sql); $sth->execute();
while (my $row = $sth->fetchrow_hashref()) {
unless ($$row{'lk'} == 1 && $$row{'rk'} / $$row{'num'} == 2) {
if ($self->{'type'} eq 'M') {$data{$$row{'multi'}} = 1} else {$data{'check'} = 'no'}
}
}
$sth->finish();
# Разница между правым и левым ключом ВСЕГДА нечетное число
$sql = 'SELECT '.($self->{'type'} eq 'M' ?
$self->{'multi'}.' AS multi, ' : 'COUNT('.$self->{'id'}.') AS num, ').
' MOD(('.$self->{'right'}.' - '.$self->{'left'}.'), 2) AS os'.
' FROM '.$self->{'table'}.
' GROUP BY '.$self->{'id'}.
' HAVING os = 0';
$sth = $self->{'DBI'}->prepare($sql); $sth->execute();
while (my $row = $sth->fetchrow_hashref()) {
if ($self->{'type'} eq 'M') {$data{$$row{'multi'}} = 1}
elsif ($$row{'num'} && $$row{'num'} > 0) {$data{'check'} = 'no'}
}
$sth->finish();
# Если уровень узла нечетное число то тогда левый ключ ВСЕГДА нечетное число,
# то же самое и для четных чисел
$sql = 'SELECT '.($self->{'type'} eq 'M' ?
$self->{'multi'}.' AS multi, ' : 'COUNT('.$self->{'id'}.') AS num, ').
' MOD(('.$self->{'left'}.' - '.$self->{'level'}.' + 2), 2) AS os'.
' FROM '.$self->{'table'}.
' GROUP BY '.$self->{'id'}.
' HAVING os = 1';
$sth = $self->{'DBI'}->prepare($sql); $sth->execute();
while (my $row = $sth->fetchrow_hashref()) {
if ($self->{'type'} eq 'M') {$data{$$row{'multi'}} = 1}
elsif ($$row{'num'} && $$row{'num'} > 0) {$data{'check'} = 'no'}
}
$sth->finish();
# Ключи ВСЕГДА уникальны, вне зависимости от того правый он или левый
if ($self->{'type'} eq 'M') {
my $sql = 'SELECT '.$self->{'multi'}.' AS multi'.
' FROM '.$self->{'table'}.
' GROUP BY '.$self->{'multi'};
my $sth = $self->{'DBI'}->prepare($sql); $sth->execute();
while (my $multi = $sth->fetchrow_hashref()) {
my $sql = 'SELECT '.$self->{'left'}.' AS lk, '.$self->{'right'}.' AS rk'.
' FROM '.$self->{'table'}.
' WHERE '.$self->{'multi'}.' = '.$$multi{'multi'};
my $sth = $self->{'DBI'}->prepare($sql); $sth->execute();
my %check;
while (my $row = $sth->fetchrow_hashref()) {
if ($check{$$row{'lk'}}) {$data{$$multi{'multi'}} = 1} else {$check{$$row{'lk'}} = 1}
if ($check{$$row{'rk'}}) {$data{$$multi{'multi'}} = 1} else {$check{$$row{'rk'}} = 1}
}
$sth->finish();
}
$sth->finish();
} else {
my $sql = 'SELECT '.$self->{'left'}.' AS lk, '.$self->{'right'}.' AS rk'.
' FROM '.$self->{'table'};
my $sth = $self->{'DBI'}->prepare($sql); $sth->execute();
my %check;
while (my $row = $sth->fetchrow_hashref()) {
if ($check{$$row{'lk'}}) {$data{'check'} = 'no'} else {$check{$$row{'lk'}} = 1}
if ($check{$$row{'rk'}}) {$data{'check'} = 'no'} else {$check{$$row{'rk'}} = 1}
}
$sth->finish();
}
# Проверяем, найдены ли ошибки
my $result = 'No error';
if (%data && $repair eq 'repair') {$result = &repair_tree($self, %data)}
elsif (%data && $repair ne 'repair') {$result = 'Found error! Not repaired!'}
return $result
}
В процессе этого метода формируется хеш %data в котором перечислены либо идентификаторы деревьев (если мультидерево), либо один элемент для инициализации. Последняя проверка на уникальнось ключей, не такая, как описано в статье. Дело в том, что при использовании мультидеревьев а так же при большом количестве узлов, получается большая нагрузка на базу данных, что не совсем правильно.
В конце процедуры мы ссылаемся на другую процедуру repair_tree. Так как ручное исправление целостности дерева - дело неблагодарное, и муторное; а чаще всего сводится к простейшему обнулению структуры, напишем отдельную процедуру, в которой попытаемся, хотя бы частично её восстановить.
8. Принудительное восстановление дерева
Восстановление структуры дерева - простое "обнуление", во время которого, все узлы устанавливаются на первый уровень в соответствии со своими идентификаторами.
sub repair_tree {
# Получаем данные
my ($self, %multi) = @_;
# Обработка дерева
if ($self->{'type'} eq 'M') {
foreach my $class (keys %multi) {
$self->{'DBI'}->do('SET @count1 := -1');
$self->{'DBI'}->do('SET @count2 := 0');
$self->{'DBI'}->do('UPDATE '.$self->{'table'}.
' SET '.$self->{'left'}.' = @count1 := @count1 + 2, '.
$self->{'right'}.' = @count2 := @count2 + 2, '.
$self->{'level'}.' = 1'.
' WHERE '.$self->{'multi'}.' = \''.$class.'\''.
' ORDER BY '.$self->{'id'})
}
} else {
$self->{'DBI'}->do('SET @count1 := -1');
$self->{'DBI'}->do('SET @count2 := 0');
$self->{'DBI'}->do('UPDATE '.$self->{'table'}.
' SET '.$self->{'left'}.' = @count1 := @count1 + 2, '.
$self->{'right'}.' = @count2 := @count2 + 2, '.
$self->{'level'}.' = 1'.
' ORDER BY '.$self->{'id'})
}
return 'Repair OK!';
}
9. Заключение
В итоге получился модуль, который позволяет максимально упростить работу с деревьями Nested Sets. Сам модуль ближайшее время выложу на CPAN, а так его можно скачать здесь. Устанавливать его не нужно, просто положить в соответсвующую папку (в моем случае это MPM) а в скрипте подключиль дополнительный каталог баблиотеки (eq: use lib './../lib';). В процессе буду его модернизировать и обновновлять поэтому если интересно, следите за обновлениями.
| 
