リレーショナルデータベースへのツリー構造の保存

投稿日: 2022-10-05 2022-10-23
タグ: Data Structures

1. 序章

この記事では、リレーショナルデータベースにツリー構造を格納する方法をいくつか紹介します。たとえば、家系図やネストされたコメント階層は、このようなモデルに適合します。

2. 問題は何ですか？

リレーショナルデータベースは、一部のデータが他のデータに関連する表形式のデータを格納するのに最適です。相互に関連する2つの異なるテーブルにデータを非常に簡単に格納できます。例えば：

これは、関係が同じテーブルを指している場合に可能ですが、より複雑になります。データを正しく再度読み取るという点でも、データの書き込みと整合性の維持という点でも。また、単一レベルの関係ではなく、深くネストされた構造が必要な場合、これはさらに複雑になります。

ネストされたツリー構造の単一レベルを読み取りたい場合、これは通常のクエリと同じです。ただし、構造全体を読み取りたい場合は、ツリーの多くのレベルをトラバースできる必要があります。さらに悪いことに、それは任意の数のレベルである可能性があるため、これをクエリに計画することはできません。

逆に、ツリー構造の下部に新しいノードを書き込みたい場合、これは単純な書き込みです。ただし、ツリー構造の中央に書き込みたい場合、または構造全体で更新を行いたい場合、これは非常に迅速に複雑になり、レコードの整合性を損なうリスクがあります。

3. JSONBlob

これを実現する最も簡単な方法は、リレーショナルデータベースを使用せず、構造をJSON BLOBに格納することです。これにより、多くのレコードの読み取りと書き込みの複雑さを無視し、すべてを1つのレコードとして格納できます。次に、データベースの代わりにアプリケーションコードで解析と更新を行います。

データベースエンジンは、私たちがここから利益を得ることができない多くのことを自動的に行います。ただし、これを行うと、多くの場合、得られる以上の損失が発生します。たとえば、ツリー内のノード間と他のテーブル間の両方で、参照整合性の概念全体が失われます。ツリー全体が単一のレコードに格納されるため、個々のノードを指すか、個々のノードから他のテーブルを指すデータベース制御の外部キーを持つことはできません。

これもスケーリングがうまくいきません。ツリー全体を単一のレコードとして格納する場合、読み取りと書き込みが扱いにくくなる前に、そのレコードが取得できるサイズには制限があります。

4. 親キーの保存

ツリー全体を一度に保存するのではなく、すべてのノードを個別に保存することを決定したら、これを実現するための最良の方法を決定する必要があります。

これを実現する1つの方法は、すべてのノードにその直接の親のIDを格納することです。親を持たないノードは NULL を格納し、親を持つノードは格納できますその親への参照。たとえば、次のようにテーブルを作成できます。

CREATE TABLE tree (
    node_id INT PRIMARY KEY,
    parent_id INT NULL REFERENCES tree (node_id),
    .... other columns ....
);

これにより、次のツリーを保存できるようになります。

次のように：

これにより、parent_id列の値がnode_id列にも存在することを確認できるため、データベース内の参照整合性が得られます。

また、1つのステートメントを使用して、ツリーの正しい場所にレコードを非常に簡単に挿入できます。

INSERT INTO tree (node_id, parent_id) VALUES (6, 5);

単一のステートメントを使用して、ツリーの一部を別の親に移動するだけでなく、次のようにします。

UPDATE tree SET parent_id = 1 WHERE node_id = 4;

ただし、ここではツリー全体の読み取りがより複雑になります。再帰的共通テーブル式などの追加のデータベースサポートがなければ、ツリーの各レベルを個別に選択して、アプリケーションにまとめる必要があります。同様に、特定のノードの祖先のリスト全体を読み取ることも、一度に1つずつ実行する必要があります。

明らかに、これは非常に非効率的ですが、どうすればこれを改善できますか？

4.1. 再帰的な共通テーブル式を使用した取得

データベースエンジンが再帰的共通テーブル式をサポートしている場合は、 WITH RECURSIVE 句を使用して、このような構造を一度にクエリできます。

これを行うには、基本的にテーブルをそれ自体に結合し、行がなくなるまでこれを再帰的に実行する必要があることをデータベースエンジンに通知するクエリを作成する必要があります。

たとえば、上記のテーブルをクエリするには、次のようにします。

WITH RECURSIVE rectree AS (
  SELECT * 
    FROM tree 
   WHERE node_id = 1 
UNION ALL 
  SELECT t.* 
    FROM tree t 
    JOIN rectree
      ON t.parent_id = rectree.node_id
) SELECT * FROM rectree;

これは、 node_id = 1 のノードを選択することから始まり、 t.parent_id = rectree.node_id である行を見つけるためにツリーを繰り返し、行が返されなくなるまで続けます。すべての子ノードではなくすべての祖先をリストする必要がある場合は、反対方向にトラバースするように同様のクエリを作成できます。

これは、データベースにレコードを安価に挿入し、ツリー構造全体を比較的安価にクエリできるため、この種のツリー構造を操作する最も効率的な方法です。ただし、すべてのデータベースエンジンがこの形式のクエリをサポートしているわけではありません。したがって、それは私たちの選択肢ではないかもしれません。たとえば、MySQLは8.0でこれをサポートしていますが、以前のバージョンではサポートしていません。

4.2. ツリー全体にラベルを付ける

ツリー全体を取得できるようにする別の方法は、各ノードが属するツリーを識別する追加の列を用意することです。これは、ルートノードのID、または全体のその他の識別子である可能性があります。木。

これは、テーブルに余分な列が追加されることを意味するため、より多くのデータを格納しています。また、テーブルへのレコードの挿入は少し複雑です。これは、ツリーの直接の親とルートの両方を提供する必要があるためです。ただし、これは、多くを必要とせずに、単一のクエリで同じツリー内のすべてのノードを選択できることを意味します。

SELECT * FROM tree WHERE tree_id = 1;

次に、このクエリにより、ツリー構造をメモリにまとめることができます。

残念ながら、これを使用してサブツリーを選択することはできません。また、特定のノードのすべての祖先を効率的にリストすることはできません。私たちができる最善のことは、ツリー全体をリストし、返されたデータから祖先を自分で計算することでした。

ただし、正確な要件によっては、これは問題にならない場合があります。

5. クロージャーテーブル

もう1つのメカニズムを使用して、グラフをノードとは別にクロージャーテーブルと呼ばれるものに格納できます。 この並列テーブルには、ノードとその祖先の間の距離を含む、すべてのノードのすべての祖先が格納されます。

たとえば、上記のツリーのクロージャテーブルは次のようになります。

これにより、サブツリー全体を非常に簡単に検索し、特定のノードの祖先のセット全体を取得できます。

ただし、ツリーへのノードの挿入と更新はより複雑です。ノードの深さに応じて、クロージャテーブルに多くのレコードを作成または更新する必要があります。移動するサブツリー内のすべてのノードのクロージャテーブルを再計算する必要があるため、ノードの移動にも非常にコストがかかります。

6. パスの保存

別の方法は、直接の親だけでなく、パス全体をツリーに格納することです。この場合、上記のツリーは次のように格納されます。

ここで、 path 列は、ピリオド文字で区切られた、ツリー内のすべての祖先のIDで構成される文字列です。一部のデータベースエンジンは、代わりに使用できるネイティブ配列または同様の構造をサポートしています。

これを行うと、テーブルからデータを読み取るのに多くの利点があります。すべての行には、その一部として親の階層全体があります。 LIKE 演算子を使用して、サブツリーを簡単にクエリすることもできます。

SELECT * FROM tree WHERE path LIKE '1.3.%';

ノードの一部のマッチングを気にせずにマッチングできるように、最後にピリオドが含まれていることに注意してください。たとえば、最後のピリオドがない場合、次のクエリクエリが実行されます。

SELECT * FROM tree WHERE path LIKE '1.3%';

また、「1.30」などの値が含まれているものと誤って一致します。

ツリーへの新しいレコードの挿入も比較的簡単です。親ノードから派生できるノードの正しいパスを知る必要があります。ただし、ノードの移動はより複雑です。リーフノードのみを移動する場合、これが更新が必要な唯一のパスです。ただし、子を持つノードを移動する場合は、サブツリー全体を更新する必要があり、すべてのノードをその方法で更新する必要があります。

ただし、この方法ではツリー内の参照整合性が失われます。代わりに構造化文字列の一部であるため、親ノードがすべて正しく存在することをデータベースに保証させることはできません。

また、これが私たちのニーズに対してどれほど効率的であるかを確認する必要があります。文字列でのLIKE一致は、整数キーでの等式一致よりも効率が低いため、サブツリールックアップが必要ない場合、これは具体的なメリットのために効率が低くなる可能性があります。

7. 概要

ここでは、リレーショナルデータベースの階層データを表すために使用できるいくつかの手法と、それぞれの利点とコストについて説明しました。次回、そのようなデータを保存する必要があり、専用のグラフデータベースを使用することはできません。これらのオプションのいずれかを試してみませんか。

getdocs

13036