12

隣接リストとネストされたツリーの2つのアプローチがあることを知っています。多数のクエリが原因で、トラバーサルでの隣接リストの使用が遅くなる可能性があると言われています。しかし、私はこれについての現実的な数字を知りません。私が作っているサイトは 200 ページ程度です。(たとえば) サイトマップを生成するためのトラバーサルには、約 0.3 秒以上かかりますか?

LAMP スタックを使用して MySQL (innoDB) で実行します。

より単純な設計のため、可能であれば隣接関係を実装したいと思います。

ありがとう。

4

6 に答える 6

4

MySQL での階層データの管理の記事では、これについて詳しく説明しています。

1 つのクエリでツリー全体 (およびその子) を取得できるため、「ネストされたセット」手法をお勧めします。基本的に読み取りは安価ですが、ツリー全体のバランスを再調整する必要があるため、書き込みは高価です。ただし、読み取り率が 99% の場合は、完全に正当化できます。

于 2009-02-13T04:02:09.620 に答える
3

隣接リストを解析するための素朴なアプローチには多くのクエリが必要であり、大きなリストの場合、メモリに構築するのにかなりの時間がかかる場合があります。参考までに、私が言及している単純なアプローチは次のように要約できます。親のないすべてのアイテムを選択し、各アイテムに対して再帰的に子を取得します。このアプローチでは、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.
?>

このコードは、単一のデータベース クエリから隣接リストを作成する手法を示すことを目的としていることにご注意ください。おそらく、メモリ消費量を減らすなどのために最適化される可能性があります。また、テストされていません。

ジム、

于 2009-02-13T05:04:05.150 に答える
2

以下に、役立つかもしれないいくつかの質問を示します。

階層を格納およびナビゲートするSQL方法

私のナビゲーションに最適なデータベーススキーマはどれですか

于 2009-02-13T03:54:33.663 に答える
2

もう1つのアプローチは、「ネストされたツリー」ではなく、「ネストされたセット」と呼ばれます。

とにかく、サイト マップの良いところは、その最大の深さを知ることができるということです。隣接モデルの問題は、対応する SQL が一度に 1 つのレベルで機能することだと思います。そのため、「n」個のレベルがある場合、「n」個の SQL ステートメントのループが必要になります ...しかし、私は (私はm はわかりません) 最大の 'n' が事前にわかっている場合は、対応する複数レベルの固定数の SQL をコーディングできます。

0.3 秒は 200 ページを計算するには非常に長い時間のように聞こえるので、おそらく問題ありません。

また、サイト マップは頻繁に更新されるわけではありません。そのため、SQL からの取得に時間がかかる場合でも、取得/計算されたツリーを RAM にキャッシュできる可能性があります。

または、ツリーを構築する SQL について心配する代わりに、ツリーをできるだけ単純に (隣接リストとして) 格納し、単純な行セットとしてデータベースから取得し、RAM にツリーを構築することができます (ループを使用してSQL ステートメントを使用してツリーを構築するために SQL でループを使用する代わりに、高レベルのプログラミング言語)。

于 2009-02-13T03:56:59.243 に答える