mysql - どの階層モデルを使用する必要がありますか? 隣接、ネスト、または列挙?

Question

世界のすべての地理的な場所とそれらの関係の場所を含むテーブルがあります。

階層を示す例を次に示します。データが実際に 3 つすべてとして保存されていることがわかります。

列挙パス
隣接リスト
ネストされたセット

データも明らかに変更されることはありません。以下は、woeid が 13911 であるイギリスのブライトンの場所の直接の祖先の例です。

表: geoplanet_places(560 万行) 大きい画像: http://tinyurl.com/68q4ndx

次に、という別のテーブルがありますentities。このテーブルには、地理的な場所にマップしたいアイテムが保存されます。いくつかの基本的な情報を保存しますが、最も重要なのwoeidはからの外部キーであるを保存することですgeoplanet_places。ここに画像の説明を入力

最終的に、entitiesテーブルには数千のエンティティが含まれます。そして、エンティティを含むすべてのノードの完全なツリーを返すことができる方法が欲しいです。

地理的な位置に基づいてエンティティのフィルタリングと検索を容易にし、その特定のノードで見つかるエンティティの数を検出できるようにするための何かを作成する予定です。

したがって、entitiesテーブルにエンティティが 1 つしかない場合、次のようなものになる可能性があります

`地球 (1)

イギリス (1)

イングランド (1)

イーストサセックス (1)

ブライトンとホーブ市 (1)

ブライトン (1)`

次に、デボンにある別のエンティティがあるとしましょう。次のように表示されます。

アース (2)

イギリス (2)

イングランド (2)

デボン (1)

イーストサセックス (1) ... など

各地理的位置の「内部」にあるエンティティの数を示す (カウント) は、ライブである必要はありません。毎時間オブジェクトを生成してキャッシュすることで生活できます。

目的は、エンティティを持つ国のみを表示するインターフェイスを作成できるようにすることです..

以下のようなので

Argentina (1021)、Chile (291)、...、United States (32,103)、United Kingdom (12,338)

次に、ユーザーが United Kingdom などの場所をクリックすると、United Kingdom の子孫であり、エンティティを含む直接の子ノードがすべて表示されます。

英国に 32 の郡があるが、最終的にドリルダウンしたときに 23 の郡のみにエンティティが格納されている場合、残りの 9 郡は表示したくありません。それは場所だけです。

このサイトは、私が達成したい機能を適切に示しています: http://www.homeaway.com/vacation-rentals/europe/r5 ここに画像の説明を入力

このようなデータ構造をどのように管理することをお勧めしますか?

私が使用しているもの。

PHP
MySQL
ソル

ドリルダウンはできるだけ迅速に行う予定です。私は、検索のためにシームレスな AJAX インターフェイスを作成したいと考えています。

また、インデックスを作成することをお勧めする列を知りたいです。

score 9 · Accepted Answer

通常、問題を引き起こす階層には 3 種類のクエリがあります。

すべての祖先を返す
すべての子孫を返す
すべての子 (直接の子孫) を返します。

のさまざまなメソッドのパフォーマンスを示す小さな表を次に示しますMySQL。

                        Ancestors  Descendants  Children        Maintainability InnoDB
Adjacency list          Good       Decent       Excellent       Easy            Yes
Nested sets (classic)   Poor       Excellent    Poor/Excellent  Very hard       Yes
Nested sets (spatial)   Excellent  Very good    Poor/Excellent  Very hard       No
Materialized path       Excellent  Very good    Poor/Excellent  Hard            Yes

ではchildren、poor/excellentメソッドを隣接リストと混合しているかどうか、つまりparentID各レコードにを格納しているかどうかによって答えが異なることを意味します。

このタスクには、次の 3 つのクエリすべてが必要です。

地球/英国/デボンのことを示すすべての祖先
すべてのお子様に「ヨーロッパの目的地」（アイテム）を見せる
「ヨーロッパの目的地」を表示するすべての子孫 (カウント)

この種のヒエラルキーはめったに変化しないため (戦争や反乱などの場合のみ)、私は具体化された道を選びます。

という varchar 列を作成しpath、インデックスを付けて、次のように値を入力します。

1:234:6345:45454:

ここで、数字は適切な親の主キーであり、正しい順序になっています (1ヨーロッパの場合234、英国の場合など)。

levelsまた、数値を1to から20(または任意の最大ネストレベル)に保持するために呼び出されるテーブルも必要です。

すべての祖先を選択するには:

SELECT   pa.*
FROM     places p
JOIN     levels l
ON       SUBSTRING_INDEX(p.path, ':', l.level) <> p.path
JOIN     places pa
ON       pa.path = CONCAT(SUBSTRING_INDEX(p.path, ':', l.level), ':') 
WHERE    p.id = @id_of_place_in_devon

すべての子とその中の数の場所を選択するには:

SELECT  pc.*, COUNT(pp.id)
FROM    places p
JOIN    places pc
ON      pc.parentId = p.id
JOIN    places pp
ON      pp.path BETWEEN pc.path AND CONCAT(pc.path, ':')
        AND pp.id NOT IN
        (
        SELECT  parentId
        FROM    places
        )
WHERE   p.id = @id_of_europe
GROUP BY
        pc.id

score 0 · Accepted Answer

これが私が思いついたクエリです。これは、あなたが提案した Quassnoi の適応です。

SELECT   pa.*,  level, SUBSTRING_INDEX(p.ancestry, '/', l.level),  p.*
FROM     geoplanet_places p
JOIN     levels l
ON       SUBSTRING_INDEX(p.ancestry, '/', l.level) <> p.ancestry 
JOIN     geoplanet_places  pa
ON       pa.woeid =  SUBSTRING_INDEX( SUBSTRING_INDEX(p.ancestry, '/', l.level),'/',-1)
WHERE    p.woeid = "13911"

これにより、Brighton のすべての親が返されます。

クエリの問題は、親へのパスを返すのではなく、同じパスを共有するノードを返すことでした。

SELECT     pa.*, GROUP_CONCAT(pa.name ORDER BY pa.lft asc),group_concat( pa.lft  ), pa.ancestry
                                            FROM     geo_places p
                                            JOIN     levels l
                                            ON       SUBSTRING_INDEX(CONCAT(p.ancestry, p.woeid,'/'), '/', l.level) <> p.ancestry 
                                            JOIN     geo_places  pa
                                            ON       pa.woeid =  SUBSTRING_INDEX( SUBSTRING_INDEX(CONCAT(p.ancestry, p.woeid,'/'), '/', l.level),'/',-1)
                                            WHERE    p.woeid IN ("12767488","12832668","12844837","131390","131391","12846428","24534461")
                                            GROUP BY p.woeid

mysql - どの階層モデルを使用する必要がありますか? 隣接、ネスト、または列挙?

2 に答える 2

Related

Reference