- 階層型UIが必要に見えても、まず確認すべきなのは、データが本当に 親子関係 を持つ必要があるのか、それともそう見えればよいだけなのかという点
- 実際のツリーが不要なら、親IDの代わりに、一覧全体の 絶対ソート順 と
indent 値だけで画面上の構造を表現できる
- Hissゲームエディタは
banana.eat のような名前をソートしたうえで、ピリオド（.）の後ろをインデントして表示し、名前空間のように見えるUI を作っている
- この方式は、ユーザーが項目を上下に移動し、インデントや逆インデントを行う ワードプロセッサ的な編集 に近く、ツリーデータ構造の負担を減らせる
- 項目間の関係を実際に参照したり維持したりする必要があるなら、インデントや文字列記号のハックではなく 本物のツリーモデル が必要になる
ツリーではないが、ツリーのように見えるリスト
- アプリケーションで
Foo、Bar のような動的リストを ツリービュー で見せようとすると、通常は各項目が親項目を参照する構造を思い浮かべる
- リレーショナルデータベースでは、たとえば
parent カラムに親IDを保存できる
Foo の parent は nullFoo 1 の parent は FooFoo 1.a の parent は Foo 1
- このようなツリーデータをSQLで取得するには、再帰CTE のような方式が必要になることがある
- しかし多くのリストでは、実際の関係よりも、人が見やすい 整った見た目 のほうが重要な場合がある
インデント値をデータとして保存する方式
- 実際の親子関係が不要なら、リストは次のフィールドだけで保存できる
sort は下位項目内の順序ではなく、一覧全体の絶対順序 を表すindent は項目の前に入れる余白量をそのまま表すため、画面描画が単純になる- 編集UIもツリー操作よりシンプルにできる
- ユーザーは項目を上下に移動できる
- 項目をインデントしたり逆インデントしたりできる
- 必要なら、正しいインデントを強制する簡単なルールを追加できる
- 結果として、コンピュータサイエンスの教科書的なデータ構造を直接操作するより、ワードプロセッサでリストを編集 する体験に近くなる
Hissのピリオド（.）ベースの偽の名前空間
- テキストアドベンチャーゲームエディタ Hiss は、
banana、banana.eat、banana.peel のような名前をUI上で階層のように見せる
- HissScriptに実際の名前空間機能を実装しているわけではない
- 実装方法はシンプル
- オブジェクト名をアルファベット順にソートする
- 名前にピリオド（
.）があれば前半部分を切り取る
- 残った部分をインデントして出力する
- サンプルコードの中核ロジックも同じ流れ
things.keys をソートする- 各名前にピリオドがあれば、インデントしたうえでピリオドより前の部分を削除して出力する
- ピリオドがなければ名前をそのまま出力する
- その後、与えられた接頭辞を持つ「親」項目が存在するか確認するチェックが数行追加される
- 任意の深さのネストも追加できるが、実際に必要になるまでは待つ方針になっている
- この 名前空間のように見えるUI はゲームを整理する人には重要だが、ゲームエディタやプレイヤーにとって特別な意味はない
- ピリオドを含む名前も、単なる名前にすぎない
- 名前空間のように見える部分は、名前を一意に保つ役割を果たしているだけである
フラットなリストとして扱う、ツリーに似た事例
- Dave Long は「ローテクな本物のツリー」として、パスと情報を フラットなリスト に保存する方式を提案している
- これは
banana.eat の例と似た洞察である
find の出力のように、次のようなパスの一覧を考えられる
./foo/zonk./foo/bonk./bar/boop/bop./bar/boop/bleep
- 深さ優先走査が必要なら、パスを 辞書順にソート すればよい
- 幅優先走査が必要なら、パス区切り文字を基準にパスを反転し、深さをそろえるために空項目を追加してからソートできる
- この例は概念を示すためのもので、実際には区切り文字で行を分割して配列として処理する方法が自然である
- フラットなリストは全般的に扱いやすく、可能であれば項目を plain old lists に入れるアプローチを好んでいる
床の上のスクラップブックという比喩
- 個人のスクラップブック作業では、写真、メモ、はがき、チケットなどを床に広げてグループを作ることができる
- 人にはグループ関係が明確に見えても、床そのものにその関係を強制する物理的な仕組みはない
- この比喩の核心は、表現された関係 と 実際の構造的関係 が異なりうるという点にある
- UIのリストも同様に、人には階層のように見える配置が、内部データモデルの実際の階層を意味しないことがある
実際のツリーが必要な場合
- インデントや文字列記号ベースの方式は、状況に応じて大きく調整が必要であり、一般的なプログラミングの文脈では ハック と見なされる可能性がある
- 実際に項目間の関係を把握する必要があるなら、親IDや親子結合テーブルなど、データモデルに合った 本物のツリー構造 を使うべきである
- 大規模な研究プロジェクトを分類するように、物理的なファイルキャビネットやフォルダレベルの整理力が必要なら、「床方式」は適していない
- 後になって項目間の関係を本当に把握する必要があるプロジェクトで、インデントや文字列内の記号数で構造を模倣すると、プロジェクトの寿命と保守期間を通じて苦しい道のりになりうる
1件のコメント
Hacker News のコメント
1つ目の方式、つまり「当然これしかない」ように見える方式は 隣接リスト（adjacency list） と呼ばれます。
2つ目の「はるかに単純な方法」は以前見た記憶がなく、明らかな欠点もありますが、場合によっては十分そうです。
3つ目の「名前空間化」は 具体化パス（materialized path） と呼ばれ、ツリーを表現する別の方式として入れ子集合（nested sets）もあります: https://www.ibase.ru/files/articles/programming/dbmstrees/sq...
人々がリレーショナルデータベースを真剣に扱っていた時代には、どれもよく知られた内容で、たとえば http://www.dbazine.com/oracle/or-articles/tropashko4/ のような記事もあります。
今では忘れられた知識のように見えます。
問題のさまざまな側面を自分で把握している最中に、その概念の既存の名前を見つけ出すのは本当に難しいと感じます。
結局、ツリーを表示するためのすべてのロジックをコード側で処理することになりますが、最新のリレーショナルデータベースと少しの CTE だけで、多くのユースケースをエレガントに、しかも追加コストなしで扱えるので残念です。
https://www.oreilly.com/library/view/joe-celkos-trees/978155...
Postgres には、このような形でネイティブに動作する ltree 型 と検索演算子があります: https://www.postgresql.org/docs/current/ltree.html
たとえば
CREATE TABLE test (path ltree);、INSERT INTO test VALUES ('Top');、INSERT INTO test VALUES ('Top.Science');、INSERT INTO test VALUES ('Top.Science.Astronomy');のように入れて、SELECT path FROM test WHERE path <@ 'Top.Science';でTop.ScienceとTop.Science.Astronomyを見つけられます。上の例で
Top.Scienceレコードを削除しても、Top.Science.Astronomyレコードは切り落とされません。ltree 値のラベルは具体化パスを通じて論理的なツリーを示唆しますが、示唆されたすべての親ノードに対応するレコードの存在を強制するわけではありません。
アプリケーションによっては、これがまさに望む動作かもしれませんし、まったく逆かもしれません。後者なら、整合性を保つ仕組みを別途用意する必要があります。
/を使えるのか気になります。[1] https://learn.microsoft.com/en-us/sql/relational-databases/h...
ただし、JSON インデックスが ltree インデックスほどよく機能しないかもしれないという懸念があります。
ここで問題なのは、構造の中の価値はたいてい表示用のツリーではなく、データの階層構造にあるということ
データを走査したり、関係を示したり、並べ替えたりといった作業をする可能性が高い
データベースのデータ構造に視覚的情報を含めるのは危険で近視眼的に見える
「いや、そんなはずはない」が答えなのか？
YAGNIが有名な設計ヒューリスティックであるのには理由がある。「常に必要だと仮定せよ」は正しくない
最適化されたデータ型の専用カラムに保存する代わりに、データ文字列の先頭に付けているだけ
数字ではないかもしれないし ID カラムではないかもしれないが、別の期待値を指す識別子である点は変わらないので、形式が変わったからといって親 ID でなくなるわけではない
もちろん、親のない子のような不正なインデントが保存されないよう保証する必要がある
だから最も簡単な方法は、まず順序/深さとして保存し、必要な機能を実装するときに親/子モデルへ移行することだと思う
ただし「インデント」は、レンダリングする空白数ではなく、ツリーにおける深さとしてより抽象的に定義するのがよい。不正なデータを見つけやすく、後の移行も容易で、ネストした
/、タブ、8 文字、4 文字、1 文字など、ユーザーごとのレンダリングの柔軟性も生まれるstruct item_t { char key[255]; char display_value[255]; }のようなデータ構造があり、キーがa/b/cのように一貫したパス区切り文字を持つなら、親と子を見つけるのは非常に簡単最悪の場合は配列を線形探索すればよく、ソート済みなら親に到達するまで前の項目だけを見ればよい
ツリー形式のデータを大量に扱う会社を始めたことがある。ツリー構造をインデント付きリストに変換するのは O(n) 時間で可能
当時の面接質問の一つでもあり、複数の SQL データベースには、再帰クエリなしでもツリーの一部を高速に取得してレンダリングできるように保存する方法がある
こうした概念を理解すると、データをきちんとツリーとして保存する方が、このようなインデント方式よりはるかに多くの利点がある
「SQL クエリでリレーショナルデータベースからツリー構造データを取得する方法の一つは、再帰 CTE（Common Table Expressions）を使うことだが、これは名前と同じくらい面白い」
CTEは再帰 CTE まで含めても怖いものではなく、慣れれば実際に面白いと断言できる
階層の深さが d のノードパスを組み立てるには、クエリ結果を得る時間が少なくとも d 倍は遅くなった
利点はツリー編集操作が安いことだったが、読み取りに比べるとはるかに稀にしか起きなかった
「人々は実際にはツリーを望んだり必要としたりしているのではなく、ツリーのように見えるものだけが必要な場合の方が多い」という点で、HN と Reddit の違いが見えてくる
HN では、子コメントは親コメントの
nextSiblingであり、親のインデント値に 1 を加えてツリーのように見せているReddit、少なくとも old.reddit.com では、子コメントは実際に親コメントの中にネストされている。新しいサイトはよく知らない
データに対するあらゆる操作が、ツリー構造を推論したうえで再び暗黙的なツリー形式に翻訳する、複雑な大混乱になるはず
この記事の核心的なアイデアは単純。問題に合った構造を使おうということ
ただし語り口は間違っていると思う。データベースからツリーを取得するのに CTE が必須というわけではなく、フラットなリストを取得してからローカルでツリーを構築すればよい。その後の操作のためにも、どうせそうする可能性が高い
同じ論理なら、リストを保存するためにリレーショナルデータベースを使う人にも、テキストファイルに保存しろと言える。なぜネットワーク遅延のコストを払うのか？
逆に、提案された構造は十分に大きなツリーで枝を移動したり深さを変えたりするには動作がよくない。線形コストがかかるから
最初から意図を明かすべきだった。3 つの例を説明した後、結論で「ツリーが必要ならツリーを使え」と無効化するのではなく。ただ、それを記事の冒頭に置いていたら、ずっとクリックベイト感は少なかっただろう
数年前、OpenGL について似たような気づきを得た。階層的な 3D オブジェクトの世界を描く必要があるのではなく、ソートされた三角形のリストを描けばよかった
その考えが頭の中のスイッチを入れてくれて、いくつもの最適化が非常に簡単になった
複雑なエンティティ階層があるゲームでも、レンダーキューに入れるときは、透明度ソートなどの理由でフラットな構造に畳み込まなければならないことが多い
「もののフラットなリスト」は ECS/DOD の基盤でもある
データベースでこうした作業を扱う本が丸ごとある
https://www.oreilly.com/library/view/joe-celkos-trees/978155...
偽のツリーを作るもう一つの方法は、JSON ブロブを保存すること
データが内部関係だけを持つなら、ソート番号を一意かつ順序付きに保とうとするより簡単かもしれない