Заметки программиста

Перевод статьи Hierarchical Data With PHP and MySQL.

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

Для начала, есть таблица данных:

CREATE TABLE  `categories` (
  `id` int(10) UNSIGNED NOT NULL AUTO_INCREMENT,
  `parent_id` int(10) UNSIGNED DEFAULT NULL,
  `title` varchar(255) NOT NULL,
  `active` tinyint(1) NOT NULL DEFAULT '1',
  PRIMARY KEY  (`id`),
  KEY `fk_categories_categories` (`parent_id`),
  CONSTRAINT `fk_categories_categories`
  FOREIGN KEY (`parent_id`)
  REFERENCES `categories` (`id`)
  ON DELETE NO ACTION ON UPDATE NO ACTION
) ENGINE=InnoDB DEFAULT CHARSET=latin1;

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

if( intval($depth) < 1 )
	$depth = 1;

$select = array();
$from = array();
$where = array();
$order = array();

for( $i = 1; $i <= $depth; $i++ )
{
	$select[] = "level" . $i . ".id AS level" . $i . "_id";
	$from[] = "`categories` AS level" . $i . "";
	$where[] = "( level" . $i . ".active = 1 OR level" . $i . ".active IS NULL )";
	$order[] = "level" . $i . "_id";
}

//SELECT
$sql = "SELECT " . implode(', ', $select) . ", level" . $depth . ".title AS title " ;

//FROM
$sql .= "FROM " . $from[0] . " ";

unset($from[0]);
if( count($select) > 0 )
{
	foreach( $from as $key => $value )
	{
		$from[$key] = $value . " ON level" . ($key) . ".id = level" . ($key+1) . ".parent_id";
	}

	$sql .= " RIGHT JOIN " . implode(" RIGHT JOIN ", $from) . " ";
}

//WHERE
$sql .= "WHERE level1.parent_id IS NULL AND " . implode(" AND ", $where) . " ";

//ORDER
$sql .= "ORDER BY " . implode(", ", $order);

$rs = $this->query($sql);

С глубиной 5 наш SQL запрос будет иметь такой вид:

SELECT
  level1.id AS level1_id,
  level2.id AS level2_id,
  level3.id AS level3_id,
  level4.id AS level4_id,
  level5.id AS level5_id,
  level5.title AS title
FROM
  `categories` AS level1
  RIGHT JOIN `categories` AS level2 ON level1.id = level2.parent_id
  RIGHT JOIN `categories` AS level3 ON level2.id = level3.parent_id
  RIGHT JOIN `categories` AS level4 ON level3.id = level4.parent_id
  RIGHT JOIN `categories` AS level5 ON level4.id = level5.parent_id
WHERE
  level1.parent_id IS NULL
  AND ( level1.active = 1 OR level1.active IS NULL )
  AND ( level2.active = 1 OR level2.active IS NULL )
  AND ( level3.active = 1 OR level3.active IS NULL )
  AND ( level4.active = 1 OR level4.active IS NULL )
  AND ( level5.active = 1 OR level5.active IS NULL )
ORDER BY
  level1_id, level2_id, level3_id, level4_id, level5_id

Возвращенные данные будут иметь такой вид:

Теперь очистив от нулевых значений массив $category мы получим наш путь:

$data = $rs->getRows();

$categories = array();
foreach( $data as $category )
{
	$title = $category['title'];
	unset($category['title']);

	foreach( array_reverse($category,true) as $key => $value )
	{
		if( $value === null )
		{
			unset($category[$key]);
		}
	}

	array_set($categories, array_merge(array(count($category)-1),array_values($category)), $title, "-- SELECT CATEGORY --");
}

return $categories;

Вы заметите, что мы также включили в наш массив $categories в соответствии с hierselect формате это указано выше. Это само по себе является интересной функцией, как, например, вхождение в Great Great Grandchild будет выглядеть так: $categories[4][1][6][8][10][12] = 'Great Great Grandchild'; и нам нужны пустые позиции для каждого уровня.

array_set () код:

function array_set(array &$array, array $keys, $value, $emptyText)
{
	$tmp =& $array;

	$lastKey = array_pop($keys);
	foreach( $keys as $key )
	{
		if( !is_array($tmp[$key]) )
		{
			$tmp[$key] = array();
		}

		$tmp =& $tmp[$key];
	}

	if( !isset($tmp['']) )
	{
		$tmp[''] = $emptyText;
	}

	$tmp[$lastKey] = $value;
}

И наш окончательный вывод массива будет выглядеть так:

Array
(
    [0] => Array
        (
            [] => -- SELECT CATEGORY --
            [1] => Parent
            [2] => Parent 2
        )

    [1] => Array
        (
            [1] => Array
                (
                    [] => -- SELECT CATEGORY --
                    [6] => Child
                    [7] => Child 2
                )

            [2] => Array
                (
                    [] => -- SELECT CATEGORY --
                    [4] => Child
                    [5] => Child 2
                )
        )

    [2] => Array
        (
            [1] => Array
                (
                    [6] => Array
                        (
                            [] => -- SELECT CATEGORY --
                            [8] => Grandchild
                            [9] => Grandchild 2
                        )
                )
        )

    [3] => Array
        (
            [1] => Array
                (
                    [6] => Array
                        (
                            [8] => Array
                                (
                                    [] => -- SELECT CATEGORY --
                                    [10] => Grandchild
                                    [11] => Grandchild 2
                                )
                        )
                )
        )

    [4] => Array
        (
            [1] => Array
                (
                    [6] => Array
                        (
                            [8] => Array
                                (
                                    [10] => Array
                                        (
                                            [] => -- SELECT CATEGORY --
                                            [12] => Great Grandchild
                                            [13] => Great Grandchild 2
                                        )
                                )
                        )
                )
        )
)

Весь прикол в том, чтоб изменить глубину дерева, достаточно указать ее в переменной $depth.

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