MYSQL の 3 つのツリー構造テーブル設計の長所と短所の簡単な分析と共有

導入

開発では、ツリー構造のシナリオによく遭遇します。この記事では、部門テーブルを例に、いくつかの設計の長所と短所を比較します。

質問

需要背景：部門別に人材を検索します。
質問: 最上位の部門を選択する場合、現在の部門とその下位部門のすべての人員をレベル全体にわたって表示するようにテーブルをどのように設計すればよいでしょうか?

画像.png

再帰？再帰はこの問題を解決できるが、パフォーマンスは必然的に低下する。

設計 1: 隣接リスト

注: (共通の親IDデザイン)

テーブルデザイン

テーブル `dept_info01` を作成します (
  `id` int(10) unsigned NOT NULL AUTO_INCREMENT COMMENT '自動増分主キー',
  `dept_id` int(10) NOT NULL COMMENT '部門ID',
  `dept_name` varchar(100) NOT NULL COMMENT '部門名',
  `dept_parent_id` int(11) NOT NULL COMMENT '親部門ID',
  `create_time` datetime NOT NULL DEFAULT CURRENT_TIMESTAMP COMMENT '作成時刻',
  `update_time` datetime NOT NULL DEFAULT CURRENT_TIMESTAMP ON UPDATE CURRENT_TIMESTAMP COMMENT '変更時刻',
  BTREE を使用した主キー (`id`)
) ENGINE=InnoDB AUTO_INCREMENT=1 デフォルト CHARSET=utf8;

画像.png

これは最も一般的な設計であり、冗長なデータなしでメニューのツリー構造を正しく表現できますが、レベル間のクエリには再帰処理が必要です。

SQL の例

1. ノードの直接のサブセットをクエリする

dept_info01 から * を選択、dept_parent_id = 1001 とする

アドバンテージ

シンプルな構造。

欠点

1.再帰なしでノードのすべての親とすべての子を照会することは不可能である

デザイン 2: パスの列挙

デザイン 1 に基づいて、すべての親セットを格納するための親部門 ID セットフィールドが追加され、複数のセットはコンマなどの固定区切り文字で区切られます。

テーブルデザイン

テーブル `dept_info02` を作成します (
  `id` int(10) unsigned NOT NULL AUTO_INCREMENT COMMENT '自動増分主キー',
  `dept_id` int(10) NOT NULL COMMENT '部門ID',
  `dept_name` varchar(100) NOT NULL COMMENT '部門名',
  `dept_parent_id` int(11) NOT NULL COMMENT '親部門ID',
  `dept_parent_ids` varchar(255) NOT NULL DEFAULT '' COMMENT '親部門IDセット',
  `create_time` datetime NOT NULL DEFAULT CURRENT_TIMESTAMP COMMENT '作成時刻',
  `update_time` datetime NOT NULL DEFAULT CURRENT_TIMESTAMP ON UPDATE CURRENT_TIMESTAMP COMMENT '変更時刻',
  BTREE を使用した主キー (`id`)
) ENGINE=InnoDB AUTO_INCREMENT=1 デフォルト CHARSET=utf8;

画像.png

SQL の例

1. すべてのサブセットをクエリする
1). ファジークエリを通じて

選択
 *
から
	部門情報02
どこ
	dept_parent_ids は '%1001%' のようになります

2) FIND_IN_SET関数を使用することをお勧めします。

選択
	* 
から
	部門情報02 
どこ
	FIND_IN_SET( '1001', 部門の親ID )

アドバンテージ

すべてのサブセットをクエリするのに便利です。
したがって、文字列 dept_parent_ids の長さを比較することで、現在のノードレベルを取得できます。

欠点

新しいノードを追加するときは、dept_parent_ids フィールドの値を適切に処理する必要があります。
dept_parent_ids フィールドの長さを決定するのは困難です。長さがどれだけ大きくても、無限に拡張することはできません。
ポイントの移動は複雑であり、すべてのサブセット内の dept_parent_ids フィールド値を同時に変更する必要があります。

デザイン3: クロージャーテーブル

クロージャテーブルは、階層型ストレージの問題に対するシンプルでエレガントなソリューションであり、スペースと時間を交換する方法です。
ツリー内のすべてのノード間の関係を記録する追加の TreePaths テーブルを作成する必要があります。
2 つのノード間に直接の親子関係がない場合でも、祖先列と子孫列の 2 つの列が含まれます。また、ノード自体を指す行も追加されます。

テーブルデザイン

メインテーブル

テーブル `dept_info03` を作成します (
  `id` int(10) unsigned NOT NULL AUTO_INCREMENT COMMENT '自動増分主キー',
  `dept_id` int(10) NOT NULL COMMENT '部門ID',
  `dept_name` varchar(100) NOT NULL COMMENT '部門名',
  `create_time` datetime NOT NULL DEFAULT CURRENT_TIMESTAMP COMMENT '作成時刻',
  `update_time` datetime NOT NULL DEFAULT CURRENT_TIMESTAMP ON UPDATE CURRENT_TIMESTAMP COMMENT '変更時刻',
  BTREE を使用した主キー (`id`)
) ENGINE=InnoDB AUTO_INCREMENT=1 デフォルト CHARSET=utf8;

画像.png

祖先と子孫の関係表

テーブル `dept_tree_path_info` を作成します (
  `id` int(10) unsigned NOT NULL AUTO_INCREMENT COMMENT '自動増分主キー',
  `ancestor` int(10) NOT NULL COMMENT 'ancestor id',
  `子孫` int(10) NOT NULL COMMENT '子孫ID',
  `depth` tinyint(4) NOT NULL DEFAULT '0' COMMENT 'レベル深度',
  BTREE を使用した主キー (`id`)
) ENGINE=InnoDB AUTO_INCREMENT=1 デフォルト CHARSET=utf8;

注: depth はレベルの深さフィールドです。自己参照は 1、直接の子ノードは 2、次のレベルは 3 などです。レベルはレベルと同じです。

画像.png

SQL の例

新しいノードの挿入

dept_tree_path_info (祖先、子孫、深さ) に INSERT INTO
dept_tree_path_info から t.ancestor、3001、t.depth+1 を選択 
ここで、t.descendant = 2001
ユニオンオール
3001,3001,1 を選択

すべての祖先を照会する

選択
	年
から
	dept_info03 AS c
内部結合 dept_tree_path_info t ON c.dept_id = t.ancestor
どこ
	t.子孫 = 3001

すべての子孫を照会する

選択
	年
から
	dept_info03 AS c
内部結合 dept_tree_path_info t ON c.dept_id = t.descendant
どこ
先祖 = 1001

すべてのサブツリーを削除

消去 
から
	部門ツリーパス情報 
どこ
	子孫 IN 
	（ 
		選択
			部門ID 
		から
		( SELECT 子孫 dept_id FROM dept_tree_path_info WHERE 祖先 = 1001 ) a
	）

リーフノードを削除する

消去 
から
	部門ツリーパス情報 
どこ
	子孫 = 2001

モバイルノード

すべてのサブツリーを削除します（最初に元の祖先から切断します）
新しい関係を築く

アドバンテージ

非再帰クエリにより冗長な計算時間が短縮されます。
任意のノードのすべての親セットの便利な非再帰クエリ。
任意のノードのすべてのサブセットをクエリすると便利です。
無制限のレベルを達成できます。
モバイルノードをサポートします。

欠点

レベルが多すぎる場合、ツリーノードを移動すると、関係テーブルに対して複数の操作が発生します。
対応する関係を格納するために別のテーブルが必要であり、ノードを追加および編集する際の操作が比較的複雑です。

組み合わせて使う

隣接リスト方式は、閉包テーブル方式と組み合わせることができます。実際、親 ID はメインテーブルに重複して追加されます。直接的な関係のみをクエリする必要があるビジネスでは、2 つのテーブルをリンクせずにメインテーブルを直接クエリできます。先祖-子孫関係テーブルは、レベル間のクエリが必要な場合に特に重要です。

テーブルデザイン

メインテーブル

テーブル `dept_info04` を作成します (
  `id` int(10) unsigned NOT NULL AUTO_INCREMENT COMMENT '自動増分主キー',
  `dept_id` int(10) NOT NULL COMMENT '部門ID',
  `dept_name` varchar(100) NOT NULL COMMENT '部門名',
  `dept_parent_id` int(11) NOT NULL COMMENT '親部門ID',
  `create_time` datetime NOT NULL DEFAULT CURRENT_TIMESTAMP COMMENT '作成時刻',
  `update_time` datetime NOT NULL DEFAULT CURRENT_TIMESTAMP ON UPDATE CURRENT_TIMESTAMP COMMENT '変更時刻',
  BTREE を使用した主キー (`id`)
) ENGINE=InnoDB AUTO_INCREMENT=1 デフォルト CHARSET=utf8;

祖先と子孫の関係表

テーブル `dept_tree_path_info` を作成します (
  `id` int(10) unsigned NOT NULL AUTO_INCREMENT COMMENT '自動増分主キー',
  `ancestor` int(10) NOT NULL COMMENT 'ancestor id',
  `子孫` int(10) NOT NULL COMMENT '子孫ID',
  `depth` tinyint(4) NOT NULL DEFAULT '0' COMMENT 'レベル深度',
  BTREE を使用した主キー (`id`)
) ENGINE=InnoDB AUTO_INCREMENT=1 デフォルト CHARSET=utf8;

要約する

実際、私の以前の仕事では、隣接リスト、パス列挙、隣接リストとパス列挙を組み合わせたものなど、さまざまな種類の設計を見てきました。それぞれの設計には長所と短所があり、選択する設計は、アプリケーション内のどの操作に最もパフォーマンスの最適化が必要かによって異なります。

デザイン	テーブルの数	直接の子をクエリする	クエリサブツリー	複数のノードサブツリーを同時にクエリする	入れる	消去	動く
隣接リスト	1	単純	再帰が必要	再帰が必要	単純	単純	単純
列挙パス	1	単純	単純	複数回チェックする	比較的複雑	単純	複雑な
閉鎖テーブル	2	単純	単純	単純	比較的複雑	単純	複雑な

要約すれば

子と親のセット関係を確立し、隣接リスト方式を使用するだけです。
上向きおよび下向きの検索では、閉鎖テーブル方式を使用することをお勧めします。

これで、MYSQL のツリー構造テーブルの 3 つの設計の長所と短所の分析と共有に関するこの記事は終了です。MYSQL ツリー構造テーブルに関するより関連性の高いコンテンツについては、123WORDPRESS.COM の以前の記事を検索するか、次の関連記事を引き続き参照してください。今後とも 123WORDPRESS.COM を応援していただければ幸いです。

以下もご興味があるかもしれません: