入れ子集合モデルについて、簡単にしか説明しません。詳しくは、ぐぐってください。
すでに詳しく知ってる人は、飛ばして 作ったもの までどうぞ。
入れ子集合モデル
木構造（階層構造）をデータベースに格納しようと思ったとき、自分のテーブルへのリレーションを作るのが、単純だしわかりやすい。しかし、SQLで木の一部を取得するのが面倒だったりして、使いやすくはない。
そこで、入れ子集合モデルという考え方で木構造を保存する場合がある。階層構造を、入れ子の集合構造と見なして保存するわけである。
自分のテーブルへのリレーションを持った、使いやすくないテーブルの例
| ID | 名前 | 上司ID |
|---|---|---|
| 1 | 佐藤 | NULL |
| 2 | 鈴木 | 1 |
| 3 | 高橋 | 2 |
| 4 | 田中 | 2 |
| 5 | 伊藤 | 1 |
| 6 | 渡辺 | 5 |
入れ子集合モデルの考え方
作りたい木構造
入れ子構造だとみなす
入れ子集合モデルのテーブルの例
| ID | 名前 | Left | Right |
|---|---|---|---|
| 1 | 佐藤 | 1 | 12 |
| 2 | 鈴木 | 2 | 7 |
| 3 | 高橋 | 3 | 4 |
| 4 | 田中 | 5 | 6 |
| 5 | 伊藤 | 8 | 11 |
| 6 | 渡辺 | 9 | 10 |
入れ子集合モデルを使うと、木の一部を取り出すのが簡単。
例えば鈴木さんの部下が誰か知りたければ、Leftが2以上、Rightが7以下の行を取り出せば、どれだけ階層が深かろうとごっそり全員取り出せる。逆にLeftが2未満でRightが7を超える行は鈴木さんの上司であり、その中でLeftが最も小さい人が鈴木さんの直属の上司となる。
作ったもの
プログラム全体はこちら→ https://github.com/ShTair/TreeBuilder/tree/master/TreeBuilder
プログラムの役割としては、入れ子集合モデルのリストから、木構造を生成すること。
そして、木構造から入れ子集合モデルのLeftとRightを更新すること。
2つのインタフェースがある。
-
ITreeItemは入れ子集合モデルを表すために、LeftとRightを持つ。- データベースに格納するモデルクラスにでも実装してください。
-
ITreeNodeは木構造を表すために、ParentとChildrenを持つ。- ビューモデルとかに実装したらいいと思います。
もしデータベースのモデルクラスを木のノードとしても使える場合は、一つのクラスにITreeItemとITreeNodeを両方実装することもできます。
使い方
// 木構造の構築
// ITreeItem を実装するクラスのリストと、 ITreeItem から ITreeNode を生成するメソッドを渡す。
// 渡す ITreeItem のリストは、Left順にソートしてある必要がある。
// 木構造が構築されて、ルートノードのリストが返ってくる。
var roots = TreeBuilder.Rebuild(items, item => new Node(item));
// 木構造を表示したり、何らかの操作を加える
// Left、Rightの更新
// ルートノードのリストと、ITreeNode から ITreeItem を取得するメソッドを渡す。
// ITreeItem はnodeの中に持っておくと便利。もしくはディクショナリにでもしておく。
TreeBuilder.Update(roots, node => node.Item);
テスト用のプロジェクトがリポジトリの中にあるので、そっちも参照のこと。
https://github.com/ShTair/TreeBuilder