2

ソーシャルネットワークの要素をいくつか備えたウェブサイトを構築したいと思います。

だから私は友達リストを保存する効率的な方法を考えようとしてきました（Facebookのようなものです）。

そして、少し検索した後、私が出くわした唯一の提案は、友情を示す2つの「ID」を持つ「テーブル」を作成することです。

これは小さなWebサイトでは機能するかもしれませんが、少し効率的ではないようです。

私はJavaのバックグラウンドを持っていますが、PHPに精通していません。

かなりうまくいくと思うアイデアが頭に浮かびました。問題は、それをどのように実装するかわからないことです。

アイデアは、友達のすべての「ID」をツリーデータ構造に保存することです。そのツリーの各ノードは、友達のIDから1桁の数字に似ています。

最初に1つのノードから開始し、次にユーザーが友達を追加するときにノードを追加します。（Lempel–Zivに少し似ています）。

すべてのノードは、0から9およびXの11個の他のノードを指すことができます。

「X」はIDの終わりを示します。

たとえば、次のツリーを参照してください。

例

このツリーでは、ユーザーには次の「id」を持つ4人の友達がいます。

  • 0
  • 143
  • 1436
  • 15

更新：以前は不明確だったかもしれませんが、すべてのユーザーが多次元配列の形式のツリーを持ち、ポインター自体の存在が友人の「ID」を示すという考え方です。

すべてのユーザーがそのような多次元配列を持っている場合、id "y"が私の友達かどうかを検索したり、友達リストからid "y"を削除したり、友達リストにid "y"を追加したりすると、すべて一定の時間が必要になります。ウェブサイトのユーザー数に依存しているので、欠点は、そのような巨大な配列を取得し、それをシリアル化してテーブルの各行にプッシュすることは正しくないようです。

-これを実装することも可能ですか？

-シリアル化を使用してそのツリーをテーブルに挿入することは実用的でしょうか？

-これを行うためのより良い方法はありますか？

私がこれを選んだ利点は、IDの数が非常に多い場合（数百万または数十億）でも、検索、追加、削除の時間が線形であるということです（桁数によって異なります）。

これを実装する際の助け、またはこの方法を改善または変更するための代替方法の提案をいただければ幸いです。

4

4 に答える 4

3

これに反対することを強くお勧めします。

  • ストレージの節約は重要ではなく、(おそらく?) 悪化する可能性があります。実際のデータセットでは、このアプローチで得られる実際のスペース節約は最小限です。平均節約額の計算は非常に難しい問題ですが、いくつかの実数を使用し、ランダムな ID でいくつかのサンプルを試してみてください。100 万人のユーザーがいる場合、15 人の友人を持つユーザーを考えてみてください。このアプローチでどれくらいのデータを節約できますか? ツリー隣接モデルでは大量のデータが必要になる可能性があるため、実際にはより多くのスペースを使用する場合があります。

  • ユーザーのリストを「レンダリング」するには、CPU への投資が必要です。

  • 挿入は非決定論的で自明ではありません。 新しいユーザーを既存のツリーに追加する場合、さまざまな方法でユーザーを挿入できます。任意に選択しないと仮定すると、どのアプローチが最適かを計算するのは困難です (ヒューリスティックにのみ基づいています)。

これは私の頭に浮かんだ大きなものです。しかし、一般的に、あなたはこれを考えすぎていると思います。

于 2011-08-01T18:37:40.790 に答える
2

タイトルに「PHP を使用する」と書いてありますが、これは単にデータベースに関する質問のようです。そして、信じられないかもしれませんが、リンク テーブルが最適な方法です。特に何百万、何十億ものユーザーがいる場合。処理が速くなり、PHP コードでの処理が容易になり、保存も小さくなります。

アップデート

ユーザー テーブル:

  id    |   name   |   moreInfo
   1    |    Joe   |     stuff
   2    |    Bob   |     stuff
   3    |   Katie  |     stuff
   4    |   Harold |     stuff

友好度表:

   left   |   right
    1     |     4
    1     |     2
    3     |     1
    3     |     4

この例では、Joe は全員を知っており、Katie は Harold を知っています。

もちろん、これは単純化された例です。

誰かが左右のより良い論理とその理由についての説明を持っているかどうか聞いてみたい.

アップデート

以下のコメントでいくつかのphpコードを提供しましたが、マークアップが間違っていたので、ここにもう一度載せます。

$sqlcmd = sprintf( 'SELECT IF( `left` = %1$d, `right`, `left`) AS "friend" FROM `friendship` WHERE `left` = %1$d OR `right` = %1$d', $userid);
于 2011-08-01T18:15:54.030 に答える
2

Open Query グラフ ストレージ エンジンであるOQGRAPHを確認してください。MySQL の効率的なツリーおよびグラフ ストレージを処理するように設計されています。

私のプレゼンテーションModels for Hierarchical Data with SQL and PHP 、またはWhat is the most effective/elegant way to parse a flat table into a tree?に対する私の回答もご覧ください。ここスタックオーバーフローで。

Closure Tableと呼んでいるデザインについて説明します。これは、階層内の先祖と子孫の間のすべてのパスを記録します。

于 2011-08-01T18:14:09.887 に答える
1

いくつかのアイデア:

  • 順序付けリスト - 順序付け自体は重いかもしれませんが、順序付けリストの検索は高速です。
  • 水平分割データ。
  • 時期尚早の最適化を取り除きます。
于 2011-08-02T07:32:15.717 に答える