隣接リストを解析するための素朴なアプローチには多くのクエリが必要であり、大きなリストの場合、メモリに構築するのにかなりの時間がかかる場合があります。参考までに、私が言及している単純なアプローチは次のように要約できます。親のないすべてのアイテムを選択し、各アイテムに対して再帰的に子を取得します。このアプローチでは、n+1 個のデータベース クエリが必要です。
次のアプローチを使用して、1 つのクエリで隣接リストを作成しました。データベースからすべての項目を選択します。キーによってインデックス付けされた配列にすべてのアイテムを転送します。配列をトラバースし、親オブジェクトからの参照をそれぞれの子に割り当てます。もう一度配列をトラバースし、すべての子オブジェクトを削除して、ルート レベルのオブジェクトのみを残します。
LAMPスタックについて言及したので、これを行うPHPコードはおおよそ次のとおりです。
<?php
// Assumes $src is the array if items from the database.
$tmp = array();
// Traverse the array and index it by id, ensuing each item has an empty array of children.
foreach ($src as $item) {
$item['children'] = array();
$tmp[$item['id']] = $item;
}
// Now traverse the array a second time and link children to their parents.
foreach ($tmp as $id => $item) {
if ($item['parent_id'] != 0 || $item['parent_id'] !== NULL) {
$tmp[$item['parent_id']]['children'][$id] = &$tmp[$id];
}
}
// Finally create an array with just root level items.
$tree = array();
foreach ($tmp as $id => $item) {
if ($item['parent_id'] == 0 || $item['parent_id'] === NULL) {
$tree[$id] = $item;
}
}
// $tree now contains our adjacency list in tree form.
?>
このコードは、単一のデータベース クエリから隣接リストを作成する手法を示すことを目的としていることにご注意ください。おそらく、メモリ消費量を減らすなどのために最適化される可能性があります。また、テストされていません。
ジム、