このタスクはかなりハックされています-リレーショナルデータベースにツリーを保存するため。 それ自体は難しいことではありませんが、いくつかの実際的な質問は脳を眉をひそめます。 多くの興味深い解決策がありますが、私にはもう一つのことが起こりました。 オリジナルであるかどうかはわかりませんが、そのような解決策は見ていません。
データベースにツリーを保存する方法を考えるのは難しくありません。 簡単に取得できるデータを考えるのは困難です。 最も一般的なもののいくつかを次に示します。
- このノードが指定されたノードの子孫であるかどうかを確認します
- このノードのすべての子孫ノードを選択します
- 特定のノードのすべての祖先を選択します
説明したソリューションの最初の2つのポイントは、階層の深さに関係なく、関連付けやサブクエリを使用しない非常に単純なクエリによって実行されます。 。 最後の点で-を考える時間がありませんでした:(
データ構造
私は最も典型的なデータ構造から来ていないので、少し説明したいと思います。 エンティティのテーブルがあります（サブジェクトエリアに完全に依存します。たとえば、商品のリストです）。 各行にもう1つフィールド-製品カテゴリの識別子を追加します。 ただし、カテゴリ自体は別のテーブルにあります。 この状況は、すべてのエンティティを説明する1つのテーブルがあるかなり一般的なスキームとは少し異なり、エンティティごとに、このエンティティが子孫を持つノードか子のないノード（ツリーの葉）かを指定するフィールドが入力されます。
つまり、リーフは1つのテーブルにあり、すべてのノードは別のテーブルにあります。
通常、ノードの階層を記述するために、 親フィールドが追加でテーブルに入力されます。このフィールドには、親ノードの識別子が書き込まれます。ノードがルートの場合はNULLになります ）
タスクの本質
ほとんどのタスクが許可するように、同じレベルのノード（すべて「兄弟」ノード）のシーケンスを無視する場合、上記の構造は、構造の（タスクのフレームワーク内の）記述に十分です。 この仮定は簡単にするために行われます。兄弟の順序を考慮するために、ノードテーブルはわずかに補足する必要があり、誰でも簡単にこれらの追加を作成できます。
ただし、問題は、たとえば、現在のノードのすべてのサブノードをいくつかのレベルの子孫にマップするなど、そのような何かを上げる必要があるときに始まります。 これを行うには、構造（ノード）のテーブルを数回参照する必要があり、そのたびに特定の階層に従って目的のノードを選択します。 たとえば、最初の子孫の識別子のセットが返され、受信した識別子ごとに操作を繰り返します。 階層の目的の深さまで。
つまり、再帰関数を使用する必要があります。 そのようなくてリソース集約的な決定を避けるために、彼らはこのサポート情報が保存されるさまざまな追加のテーブルを考え出します。 かなり良い解決策ですが、すみません、面倒です。 エレガントでシンプルなものが欲しいのですが、リクエストは非常に明確に見えました。
いくつかの解決策がありますが、いくつかお話しします。
- 特定の走査順序ですべてのノードに番号を付けます。
残念ながら、ソースへのリンクを失いました。リンクをありがとう。 非常にシンプルで直感的な選択を行うことができますが、1つの欠点があります：階層の変更（たとえば、商品の新しいカテゴリの作成）にノードに番号を付ける必要がある - 現在のノードへのフルパスのストレージ 。 リソースが集中し、あまり便利ではありません。 あるいは、パスは、各ビットが特定の祖先の識別子を示す数字の形式で「エンコード」されます。 たとえば、番号「53」は、現在のノードが3番目のグループの5番目のサブグループにあることを示します。 この表現の明らかな欠点は、グループ/サブグループの数に厳しい制限があることです。
私の決断
私はすぐに予約しますが、それは私のものではなく、誰かによって発明され使用された可能性がありますが、どこからでもコピーして貼り付けたわけではないため、このソリューションを「鉱山」と呼ぶことができます:)
したがって、私のソリューションは2番目のタイプのソリューションのバリエーションですが、既存の実装のほとんどの欠点の多くが欠けています。 ただし、独自の機能を備えています。 しかし、それについては以下で詳しく説明します。
私は提案する：
ノードテーブルでは、素数を識別子として使用し、 「親」フィールドでは、すべての祖先の識別子の積を使用します。
それは何を与えますか？
いくつかのクエリの優雅な構築 1つのアクションで、特定の2つのノードが親子関係にあるかどうかを正確に調べることができます。
ご存知のように 、各複素数は一意に素因数に分解されます。 したがって、既存の親子関係のサインは（ 階層的な距離に関係なく ）、提案された親の識別子による、意図された子の「親」フィールドの分割可能性になります。 または、言葉遣い、表現をわずかに変更する
parent MOD < > = 0
いくつかの例
カテゴリ（ノード）テーブルの構造は最も単純です：
CREATE TABLE categories (`id` INT(11), `parent` INT(11), `name` VARCHAR(50), PRIMARY KEY `id`);
祖先間で特定のノードを持つすべてのノードの選択：
SELECT * FROM `categories`
WHERE `parent` MOD <`id` > = 0;
新しいノードの親フィールドを計算するには、新しい親のidフィールドとparentフィールドを掛けるだけです。
短所
- まだ考えられていません;）
- 素数は恐ろしい動物です、それらを狩るのは簡単ではありません...
- さらに、各親フィールドはすべての親の識別子の乗算であるという意味で階層の複雑さに制限が設けられており、開発された階層では、かなり大きなフィールドサイズが必要になります（ただし、BIGINTを使用して解決できます）
- すべての祖先の不便な検索：親フィールドを分解する必要があります
最初の点について-ここではhabrapeopleに助けを求めます:)主なタスクとして、商品のカタログを操作するために必要なさまざまなリクエストを見積もることを提案します。
2番目の点について、少し明確にしたいと思います。 第一に、 素数の数について ：10億から10億の範囲で約5000万の素数があります。 つまり、10ビット（デフォルトでは、MySQLはINTに11ビットを使用）で、5000万ノードをクラムできます。 確かに、「親」フィールドの状況はもっと悲しいです：5000万ノードがある場合、INT（11）サイズでは十分ではないかもしれません：（...十分かどうか-具体的な構造のタイプによって異なります。
素数の生成は恩恵のない作業ですが、商品のカタログ（および通常は数百を超えないグループ/サブグループ）については完全に解決可能です。
製品カタログの範囲を少し超えると、素数表を使用して新しい素数（新しいノードの識別子）を取得できます。 つまり データベースに素数のテーブルを直接入力します。1つのフィールドはシリアル番号で、2番目のフィールドは対応する素数です。 階層のパワーを事前に推定しておくと、適切なサイズの素数のテーブルを作成できます。
ただし、私が知る限り、カテゴリの階層を変更しても、階層に関するデータが抽出される可能性ははるかに低くなります。