1

私は、それぞれが任意の多角形である 5,000 個のセルで構成される幾何学的図を持っています。私のアプリケーションでは、このような図を多数保存する必要があります。

このマップに対してインデックス付きクエリを作成するには、データベースを使用する必要があると判断しました。すべてのマップ データをロードすることは、単純なクエリにすばやく応答するにはあまりにも非効率的です。

セル データをデータベースに追加しました。それはかなり単純な構造を持っています:

CREATE TABLE map_cell (
map_id INT  NOT NULL ,
cell_index INT  NOT NULL ,

...    
PRIMARY KEY (map_id, cell_index)
)

マップごとに 5,000 行というのはかなり少ない数ですが、メインの結合インデックスをクラスター化できるため、クエリは数百万行でも効率的である必要があります。扱いにくい場合は、map_id 境界で分割できます。マップあたりの行数が多いにもかかわらず、このテーブルは非常にスケーラブルです。

問題は、どのセルが互いに隣接しているかを示すデータを保存することです。セル隣接関係は、同じテーブルに対する多対多の関係です。また、マップごとにそのような関係が非常に多数あります。正規化されたテーブルは、おそらく次のようになります。

CREATE TABLE map_cell_neighbors (
id INT  NOT NULL AUTO INCREMENT ,
map_id INT  NOT NULL ,
cell_index INT  NOT NULL ,
neighbor_index INT ,
...
INDEX IX_neighbors (map_id, cell_index)
)

このテーブルには、結合で決して使用されない代理キーが必要です。また、このテーブルには重複するエントリが含まれています。セル 0 がセル 1 の隣接セルである場合、セル 1 は常にセル 0 の隣接セルです。追加のインデックス スペースを犠牲にして、これらのエントリを削除できます。

CREATE TABLE map_cell_neighbors (
id INT  NOT NULL AUTO INCREMENT ,
map_id INT  NOT NULL ,
neighbor1 INT  NOT NULL ,
neighbor2 INT  NOT NULL ,
...
INDEX IX_neighbor1 (map_id, neighbor1),
INDEX IX_neighbor2 (map_id, neighbor2)
)

オプション 1 には重複するエントリが含まれており (リレーションシップが持つプロパティの複製を含む)、オプション 2 は正規化されているとは感じられないかなり奇妙なデータベース設計であるため、どちらがより「正規化された」と見なされるかはわかりません。どちらのオプションもスペース効率は高くありません。10 個のマップの場合、オプション 1 では 300,000 行が使用され、12M のファイル スペースが使用されました。オプション 2 は 150,000 行で、8M のファイル スペースを占めていました。両方のテーブルで、データが行ごとに約 20 バイトである必要があることを考慮すると、インデックスはデータよりも多くのスペースを占有していますが、実際にはディスク上で 40 ～ 50 バイトを使用しています。

3 番目のオプションはまったく正規化されませんが、スペースと行の効率が非常に高くなります。これには、map_cell に VARBINARY フィールドを配置し、セル テーブル自体にバイナリ パックされた近隣のリストを格納する必要があります。これには、関係ごとに 40 ～ 50 バイトではなく、セルごとに 24 ～ 36 バイトが必要です。また、全体の行数が減り、クラスター化された主キーにより、セル テーブルに対するクエリが非常に高速になります。ただし、このデータに対して結合を実行することは不可能です。再帰クエリは、一度に 1 ステップずつ実行する必要があります。また、これは本当に醜いデータベース設計です。

残念ながら、50 個のマップだけで SQL のボトルネックにぶつからないように、アプリケーションを適切にスケーリングする必要があります。他に何か思いつかない限り、実際に機能するのは後者のオプションだけかもしれません。そのような卑劣なアイデアをコードにコミットする前に、すべてのオプションを明確に見ていることを確認したかった. 私が考えていない別の設計パターンがあるかもしれませんし、私が予見している問題は見た目ほど悪くないかもしれません。いずれにせよ、これを押し進める前に、他の人の意見を聞きたかったのです。

このデータに対する最も複雑なクエリは、パスの検索とパスの発見です。これらは、特定のセルで始まり、いくつかの反復で隣接セルを移動し、これらのセルのプロパティを収集/比較する再帰クエリになります。これらすべてを SQL で行うことはできないと確信しています。全体にいくつかのアプリケーション コードが存在する可能性があります。このような中程度のサイズのクエリを実行し、ユーザーに「応答」していると感じるのに許容できる時間、約 1 秒で結果を取得できるようにしたいと考えています。全体的な目標は、大きなテーブル サイズによってクエリが繰り返されたり、固定深度の再帰クエリに数秒以上かかったりしないようにすることです。

4

1 に答える 1