ツリー構造テーブルの並列クエリ設計

本文はネットユーザー長空Xより寄稿されました。転載・共有は自由です。

原文著者：長空 X（CSDN 同名「長空 X」、CkTools の作者、github: https://github.com/hjkl950217）

原文リンク：https://www.cnblogs.com/gtxck/articles/16293295.html

発端

今日、懒得勤快と木構造テーブルの処理について話していたところ、現在私たちが知っている木構造テーブルの検索はどちらも再帰クエリが必要で、この方法は極めて効率が悪く、保守も難しいことに気づきました。では、もっとシンプルで平行クエリが可能な方法はないのでしょうか？その後、実際に議論して1つの方法を考案し、彼はすぐに自分のサイトに反映させました。

懒得勤快官网

宣言

記事中のいくつかの案は、私たちの議論の結果とインターネット上の資料をまとめたものです。設計手法は千差万別であり、記事で紹介する設計手法は、ほとんどの木構造テーブルが必要なケースを対象としたものであり、最適解を意味するものではありません！最適解とは、設計手法、人員のスキル、業務状況などの要素を総合的に考慮した結果であり、この記事はあなたの最適解を見つけるための一助となるものです。

木構造テーブルとは？

リレーショナルデータベースのテーブルにおいて、木構造データを格納するテーブルです。例えば、あるフィールドで分類を選択する必要があり、1次、2次、...N次の階層がある場合、次のように設計できます：

このようなデータは、大学のデータ構造で学ぶ木に組み立てることができ、階層関係を表現します。ここでのIdは通常、数値が最適ですが、数値でない場合もあります。この点は、採用する手法の選択に影響を与える可能性があるため、後述します。 このデータ構造のエンティティ定義は、一般的に次のようになります：

class CommentEntity
{
	public int ID {get;set;}
	public int PID {get;set;}
	//.. いくつかのデータフィールド
	public CommentEntity ParentNode {get;set;}
	public List<CommentEntity> ChildNode {get;set;}
}

エンティティ定義において、ParentNodeは親ノードを指し、ChildNodeは複数の子ノードを指します。データ構造のリストの知識があれば、この2つのフィールドがポインタフィールドの役割を果たすことがわかるでしょう。

データはデータベースに行単位で格納されます。データを取得した後、ParentNodeとChildNodeの参照関係を組み立てれば、実際の業務に応じて使用できます。

何に使うのか？

所属関係があるものはすべてこの方法で保存できます。例：権限関係、分類、タイプ、階層区分、行政区画、コメントなどなど...

しかし、厄介なのはクエリが不便なことです。例えば、1次分類以下の全データを取得したい場合、従来の方法では最初にid=1の1次分類を検索し、次にPID=1のデータを検索し、さらにPID=先ほど取得したデータのIDというように再帰的に複数回クエリを実行する必要があります。

目標

コメントを例にとります。

以下の要件を満たす必要があります：

1. ページ表示時にメインコメントをページングで取得し、階層関係に従って返信コメントを表示する
2. 特定のコメントからその下の全コメントを検索できる
3. 平行クエリ（再帰ではない）
4. 各コメントデータは、メインコメントにも子コメントにもなり得る

案1: タグ（tag）で木をマークする

この案は、フィールドtagを追加して木全体をマークするものです。構造は次の通り：

Tagはデータベースクエリに使用し、IDとPIDはメモリ内でのデータ組み立てに使用します。同時に、Tag列に非クラスター化インデックスを作成します。

クエリ方法：

ここで追加したフィールドは、各木で同じ値になります。最大2回のデータベースクエリで済み、その後メモリ内でPIDを使って参照関係を再構築し、不要なデータを削除します。

1回目のクエリ： コメントIDで記事IDを取得（記事IDが既にある場合は2回目へ）

2回目のクエリ： 記事IDで全データを取得

ページングクエリ： クエリ後、メモリ内で不要なデータを削除

この設計の根拠：

1. Idが数値の場合、連続したデータはディスク上で連続して格納される可能性が高く、ディスクI/Oの効率が向上します。Idが数値でない場合でも、記事Idで非クラスター化インデックスを作成すれば高速にクエリできます。
2. メモリ内での参照関係の組み立ては非常に高速で、再帰を必要としません（ループ内でPIDを検索し、見つかったらChildNodeに追加し、同時にParentNodeに代入するだけです）。
3. 設計ロジックがシンプルで、インターンレベル以上の開発者であれば容易に保守できます。

欠点： もし1つのコメント木が1000階層ある場合、大量の不要なデータを取得することになります。

改善：レベル（level）で階層をマークする

階層フィールドを追加：

クエリ時にlevelを追加することで、不要なデータ転送を一部削減でき、最後に上記の組み立てコードを再利用します。

案2: パス（path）で依存パスをマークする

ネット上の画像を借用して考え方を説明します（出典不明、侵害削除）：

上記の考え方に基づき改造：

子ノードを書き込む際には親ノードのpathを知る必要がありますが、通常これは満たせます。TagとPathはデータベースクエリに使用し、IDとPIDはメモリ内でのデータ組み立てに使用します。

クエリ方法：

全件取得： 記事IDで全データを取得し、メモリ内でPIDを使って組み立て

ID=2およびその下のデータを取得：

1回目のクエリ： ID=2のpathを取得

2回目のクエリ： ID=2 または startwith $",2"

ページングクエリ：

まず記事IDで時刻順に並べて先頭X件を取得し、その後2回目のクエリで「コメント内のコメント」データを取得。2回目のクエリでは複数の startwith を組み合わせることが可能。

また、必要に応じて level フィールドを冗長化してクエリ効率を上げることを推奨します。pathには暗黙的に階層情報が含まれていますが、クエリには不向きです。

この設計の根拠：

1. 案1とほぼ同じで、理解コストがさらに低い。

欠点： 特別な欠点ではないが、pathで子ノードをフィルタリングする際にインデックスが利用できない。

案3: 「コメント内のコメント」を設計しない

知乎の設計を参考に、一目でわかるシリーズ：

知乎の構造では、コメントと返信コメントのみで、返信コメントは直前のコメントIDのみを保存すればよい。この方式は設計がシンプルで、読みやすさも極めて良い（深い「コメント内のコメント」は見栄えが悪い場合がある）。

クエリ方法：

全件取得： 記事IDでPID is nullのデータをすべて取得し、メモリ内でPIDを使って組み立て

ID=1およびその下のデータを取得： GroupID = 1のデータをクエリ。この設計では、返信コメントのデータを単独でクエリすることはない。

利点： 理解コストが非常に低く、ストレージの負荷も小さい。

案4: 再帰を使用する

前述のように再帰は使わないと言いましたが、なぜここで触れるのか？理由は：

1. 一部のチームでは、データベースは余分なデータを返すべきではなく、冗長ノードも追加すべきでないと固執する人がいる。
2. MySQL 8.0では、データベースレベルで再帰を実現するRECURSIVEが追加された。
3. その他のやむを得ない事情。

したがって、上記の3つの案が適さない場合、再帰の路線に戻らざるを得ないかもしれません。具体的な内容はここでは触れませんが、ネット上に多くの記事があります。

まとめ

案1, 2, 3は、冗長フィールドを使用してクエリコストと理解コストを低減し、異なるストレージの特性（データベースは演算に不向き、メモリは高速読み書きに適している）を活用して目標を達成しています。

案3も同様であり、業務分析を通じて技術コストと顧客体験の両立を実現しています。

案4は最終手段としての案です。

個人的にはlevel + pathの組み合わせをお勧めします。この組み合わせはコメントだけでなく、他の木構造も適切に処理できます。開発者が常に業務要件に影響を与える機会があるとは限らないからです。

より良い案があれば、ぜひコメントで議論しましょう～