3

データベーススキーマでドメインオブジェクトを作成しようとしていて、コードでドメインオブジェクトにハッシュテーブル/リストメンバーがある場合は、次のようになります。

public class SpaceQuadrant : PersistentObject
{

    public SpaceQuadrant()
    {
    }

    public virtual Dictionary<SpaceCoordinate, SpaceObject> Space
    {
        get;
        set;
    }
}

ディクショナリは、オブジェクト キーを値キーにマッピングする単なるハッシュテーブル/リストです。さまざまな結合テーブルを作成したり、手法をロードしたりして、これを行うための複数の方法を考え出しましたが、O(1) を取得するという点では、それらはすべてひどいものです。ハッシュテーブルで取得したアクセス時間。

データベース スキーマで SpaceQuadrant、SpaceCoordinate、および Space Object をどのように表現しますか? 簡単なスキーマ コードの説明があればよいでしょう。

table SpaceQuadrant
{
    ID int not null primary key,
    EntryName varchar(255) not null,
    SpaceQuadrantJoinTableId int not null
                 foreign key references ...anothertable...
}

読んでくれてありがとう！

詳しくは：

すばらしい回答をありがとうございます。すでに、ざっと目を通しただけです。回答する前に、それぞれについて考える時間を取りたいと思います。

これらのクラスを定義するためのより良い方法があると思われる場合は、ぜひ例を示してください。使い慣れた言語はどれでもかまいません。

4

4 に答える 4

2

リレーションはハッシュテーブルではありません。それらはセットです。

座標をキーとしてデータベースを整理することはしません。オブジェクトが場所を変更した場合はどうなりますか？代わりに、おそらく座標をオブジェクトの属性として扱います。

また、次元の数は固定されていると思います。たとえば、3つです。その場合、オブジェクトのこれらの属性を固定列に格納できます。

CREATE TABLE SpaceQuadrant (
  quadrant_id INT NOT NULL PRIMARY KEY,
  quadrant_name VARCHAR(20)
  -- other attributes
);

CREATE TABLE SpaceObject (
  object_id INT NOT NULL PRIMARY KEY,
  x NUMERIC(9,2) NOT NULL,
  y NUMERIC(9,2) NOT NULL
  z NUMERIC(9,2) NOT NULL,
  object_name VARCHAR(20) NOT NULL,
  -- other attributes
  quadrant_id INT NOT NULL,
  FOREIGN KEY (quadrant_id) REFERENCES SpaceQuadrant(quadrant_id)
);

オブジェクト指向クラスでは、オブジェクトが辞書にある理由が明確ではありません。O（1）時間でそれらにアクセスするとおっしゃっていますが、なぜそれを調整して行うのですか？

これを使用して特定のポイント（たとえば、プレーヤーの宇宙船）の近くにあるオブジェクトの検索を最適化する場合は、このSpaceQuadrantにその特定のポイントからのすべてのオブジェクトの距離の計算を入力するSQLクエリを組み込んで、並べ替えることもできます。距離による結果。

私はあなたのプログラムについて、これらの提案が適切かどうかを知るのに十分なことを知りません。しかし、少なくともデータを整理するさまざまな方法を考えさせているのでしょうか。

于 2009-01-16T02:03:40.553 に答える
2

最も単純なケースでは、ディクショナリにはテーブルの主キーにマップされるキーがあります。そのため、キーの値を指定すると、単純なルックアップで一致するデータをすぐに見つけることができます。

この場合、空間象限を記述または特徴付ける一般的な (単一値の) 属性を持つテーブル SpaceQuadrant が必要になります。SpaceQuadrant テーブルには主キー、おそらく生成された ID、おそらく自然値があります。ハッシュテーブルは、SpaceQuadrant を相互参照するための主キー値と、位置 (SpaceCoordinate) および象限と座標の属性を含むテーブルで構成されます。

拡張可能な DBMS を使用している場合は、SpaceCoordinate のユーザー定義型を定義できます。それができない場合は、x、y、z または r、theta、rho などの 3 つの列を使用して、位置 (SpaceCoordinate) を表すことができます。

大まかに言うと、私が説明している構造は Bill Karwin のものと非常によく似ています。キー（メッセージを読み直すまでしゃれは意図されていません）の違いは、私の本では、下位テーブルの主キーの一部として位置を設定しても問題ないということです。それ。代替候補キーであるオブジェクト ID 列がある場合もあります。あるいは、オブジェクトがその瞬間に存在する宇宙象限とは独立した存在を持っている場合 (または複数の位置に存在する可能性があります - それらは点ではなく宇宙ステーションか何かであるため)、その場合、SpaceObject を別のテーブル。何が最善かは、私たちが入手できない情報によって異なります。

主キーの一部として SpaceCoordinate を使用する場合の制限に注意する必要があります。

  • 2 つのオブジェクトが同じ位置を占めることはできません (これは、3D 空間だけでなく、ハッシュ テーブルでも衝突と呼ばれます)。
  • 位置が変更された場合、キー データを更新する必要があります。これは、キー以外のデータを更新するよりもコストがかかります。
  • 近接ルックアップは難しいでしょう - 正確なルックアップは十分に簡単です。

同じことがメモリ内の辞書にも当てはまります。座標を変更した場合は、古い場所からレコードを削除し、辞書の新しい場所に配置する必要があります (または、言語が舞台裏でそれを行う必要があります)。

于 2009-01-16T02:56:07.000 に答える
2

ディクショナリはテーブルです。ハッシュは、使用されるインデックスの種類の問題です。ほとんどの RDBMS は、テーブルが大きくて密集していると想定しているため、ハッシュ インデックスは適切ではありません。

table SpaceQuadrant { 
    ID Primary Key,
    -- whatever other attributes are relevant
}

table Space {
    SpaceCoordinate Primary Key,
    Quadrant Foreign Key SpaceQuadrant(ID),
    SpaceObject -- whatever the object is
}

Space オブジェクトには、それらが配置されている Quadrant への FK 参照があります。

RDBMS によっては、期待どおりのパフォーマンスが得られるハッシュ ベースのインデックスを見つけることができる場合があります。たとえば MySQL では、HEAP ストレージ エンジンを使用すると HASH インデックスがサポートされます。

于 2009-01-16T03:00:03.230 に答える
1

まず、地理的に配置されたデータの専用サポートが多くのデータベースに存在します。さまざまなアルゴリズムを使用でき（たとえば、Bツリーの空間バージョンが存在します）、近接検索のサポートがおそらく存在します。

SpaceQuadrantごとに異なるハッシュテーブルがあるため、次のようなものが必要になります（S.Lottの投稿から編集）：

table Space {
    SpaceCoordinate,
    Quadrant Foreign Key SpaceQuadrant(ID),
    SpaceObject -- whatever the object is (by ID)
    Primary Key(SpaceCoordinate, Quadrant)
}

これは(SpaceCoordinate, Quadrant) -> SpaceObjectId辞書です。

=====

さて、あなたのO（1）パフォーマンスの懸念について、それが間違って扱われる理由はたくさんあります。

誰かが言ったように、多くのDBでメモリベースのテーブルのハッシュインデックスを使用できます。ただし、永続ストレージが必要な場合は、1つではなく2つのテーブル（メモリ1と永続テーブル）を更新する必要があります（これに対する組み込みのサポートがない場合）。それが価値があるかどうかを知るには、実際のデータ（実際のデータサイズを使用）でベンチマークを行う必要があります。

また、テーブルをメモリに強制すると、より悪い影響を与える可能性があります。

何かが交換された場合、あなたは死んでしまいます-Bツリー（つまり、通常のディスクベースのインデックス）を使用していた場合、そのアルゴリズムは必要なI/Oを最小限に抑えていたでしょう。それ以外の場合、すべてのDBMSはハッシュテーブルを使用し、Bツリーの代わりにスワッピングに依存します。あなたはあなたが記憶に収まるかどうかを予測することを試みることができます、しかし...

さらに、BツリーはO（1）ではなく、O（log_512（N））、またはそのようなものです（O（log N）に崩壊することは知っていますが、これに耐えてください）。それを4にするには、（2 ^ 9）^ 4 = 2 ^ 36 = 64GiBが必要です。データが多すぎる場合は、メモリに収まるようにとにかく大きなアイアンサーバーが必要になります。つまり、ほぼO（1）であり、定数係数が実際に重要です。
漸近的複雑性が低く、素因数分解が大きいアルゴリズムについて聞いたことがありますか。これは、非実用的なデータサイズで単純なアルゴリズムよりも高速です。

最後に、DB作成者は私やあなたよりも賢いと思います。特にSQLの宣言型の性質を考えると、この方法でSQLを手動で最適化しても効果はありません。インデックスがメモリに収まる場合、必要に応じて、ディスクインデックスのハッシュテーブルバージョンを作成して使用することを選択できると思います。そのためにドキュメントを調べてください。

しかし、肝心なのは、特にこの種の場合（標準のSQL最適化とは対照的に、私たちが独自に考えている奇妙な最適化）、宣言型言語を使用する場合、時期尚早の最適化は悪です。

于 2009-01-16T04:39:06.947 に答える