🍃
ltreeを使って実現する階層データ構造

tom
2025/09/16に公開
PostgreSQL
tech
こんにちは、COTENで世界史データベースを作っているトムです。
データモデルを設計していると、木構造や階層構造など何らかのグラフをRDBで扱う場面に出会うことありますよね？RDBではグラフを素直に扱うことが難しく、エンジニアの腕の見せどころとなります。
すでにこの問題に対しては、隣接リストや経路列挙、クロージャーテーブルなどの手法がよく知られています。場合によっては、グラフの部分だけ、RDBではない他のソリューション（例えば、グラフDBやドキュメントDB）を使うことも検討の余地はあります。

PostgreSQLを使っている場合、ltreeという拡張機能の利用も選択肢の一つになるよという紹介が本記事です。

 ltree型でできることltreeは、PostgreSQLの標準拡張機能として提供される、階層的なツリー構造データを表現するためのデータ型です。コアではないですが、拡張機能として同梱されているので、
CREATE EXTENSION ltree;
でほとんどの場合利用可能でしょう (PostgreSQL 9.1以降)。
ラベルパス（例：Top.Electronics.Audio.Headphones）の形式で階層を表現し、さまざまなパターンマッチングに対応したクエリが用意されています。
主な特徴として、
ラベルパス形式 - ドット区切りのラベルで階層を表現（parent.child.grandchild）
高速な階層検索 - 祖先・子孫の検索が専用の演算子で高速に実行可能
パターンマッチング - lqueryやltxtqueryを使った柔軟な検索に対応

があげられます。

 ラベルパスとその制約ラベルパスはC Localeで、最長1000文字まで対応しており、ほとんどのユースケースで十分な長さだと言えそうです。後述しますが、GiSTインデックスなどのインデックス作成も可能で、大規模データでも高速な検索が実現可能です。
一方で、制約としては、ラベルパスに使える文字はalphanumericなものに限られるため、UUIDをラベルに使いたい場合は、-を_に変えるなどの一手間が必要だったり、そもそもマルチバイト文字には対応しておらず、動物.哺乳類.猫のようなラベルパスは作成できません。

また、区切り文字は.に固定されているため、.を含むラベルも利用できません。このため、URLやファイルパスをそのままltreeに渡すことはできず、UUID同様、変換の一手間が必要です。

 ltree型の特性ltreeは読み取り性能は優れていますが、書き込み、特に親子関係の変更や中間ノードの削除が頻発するシステムでは要注意です。

 Read性能ltreeの最大の強みは読み取り性能で、正規表現のようなワイルドカードにも対応しています。以下のような探索がすでにサポートされているため、かなり複雑なケースにおいても、効率的に探索できるように関数・演算子が準備されています。
祖先・子孫の一括取得（@>, <@演算子）
パスベースの検索（完全一致、前方一致）
階層の深さによる検索（nlevel()関数）
共通祖先の検索（lca()関数）
例としては、
Top.*{0,2}.sport*@.!football|tennis{1,}.Russ*|Spain
というような複雑なラベルパスの検索が公式ドキュメントでは紹介されていますね。

 クエリ例例１. 全ての子孫を検索（サブツリー検索）
SELECT path FROM categories WHERE path <@ 'Top.Electronics';
---
Top.Electronics
Top.Electronics.Audio
Top.Electronics.Audio.Headphones
例2. 全ての親を検索（パンくずリスト）
SELECT path FROM categories WHERE path @> 'Top.Electronics.Audio.Headphones';
---
Top
Top.Electronics
Top.Electronics.Audio
Top.Electronics.Audio.Headphones
例3. 直下の子だけを検索
SELECT path FROM categories WHERE path ~ 'Top.*{1}';
---
Top.Electronics
Top.Books
RDBでグラフ構造を実現するのによく用いられる隣接リストモデルでは再帰CTEが必要な処理も、ltreeなら単純なWHERE句で実現できます。

 Index戦略B-tree, hash, Gistインデックスがサポートされています。クエリの特性に応じて、インデックスの種類を選べるのはうれしいですね。
CREATE INDEX path_gist_idx ON categories USING GIST (path);
Gistインデックスを使うと、等価比較や範囲比較に加えて、<@, @>, ~, ? などのltree専用演算子にもインデックスを効かせることができるようになりますが、一方で、インデックスサイズが肥大化するという報告もあります。

単純比較が大半を占めるようなユースケースでは、b-treeまたは17からサポートされたhash indexで代替可能か考慮してみてください。

 Write性能メリット
単一レコードの挿入・更新は通常のVARCHARカラムと同等の性能
パスの更新も単純なUPDATE文で完結
注意が必要なケース
大規模な階層再編成 - 親ノードのパス変更時、すべての子孫のパスを更新する必要がある
パスの一意性制約 - 同じパスを持つノードを作らないよう、アプリケーション側での制御が必要
-- 階層の再編成例（AudioをEntertainmentの下に移動）
UPDATE category_paths
SET path = 'Top.Entertainment' || subpath(path, 2)
WHERE path <@ 'Top.Electronics.Audio';
上記の例のような階層の再編成を伴う更新は、隣接リストモデルなら親IDの更新だけで済みます。一方、ltreeでは全子孫の更新が必要です。

実際のアプリケーションで階層の再編成が頻発するケースはあまり想定しづらいですが、かなり動的にエッジ・ノードが変更されるようなWrite-heavyなユースケースには不向きだと言えるでしょう。

 世界史データベースでの利用方法さて、ltreeの特性を紹介してきましたが、COTEN世界史データベースにおいては、歴史上の出来事、人物、場所などをカテゴライズする、その名の通り、Categoryテーブルにltreeを利用しています。

Categoryは、人物・出来事・場所などのEntityやEntity同士の関連であるRelationに持たせており、人物ならactor.person、出来事なら event というラベルパスを持つカテゴリを割り当てています。
このCategory自体に、階層構造を持たせており、例えば、人物の中でもさらに、職業による分類をするのであれば、
- actor.person.priest
- actor.person.warrior
- actor.person.warrior.samurai
のようなカテゴリを増やしていくことになります。

（なお、本記事で紹介しているカテゴリ例は全て実際のデータとは異なります）

 Prismaでの制約と対処法世界史データベースのバックエンドはNodeJSで書かれており、ORMとしてPrismaを利用しています。

しかし、Prismaは2025年8月現在、ltree型を直接サポートしていません。そのため、

Unsupported型として定義する
prismaの提供するAPIではなく、実際のSQLを$queryRawや$executeRawを使用して記述
SQLインジェクション対策として、パラメータ化クエリを必ず使用 (Unsafe関数は利用しない)
などの工夫が必要です。

 データベース設計世界史データベースにおいては、Category自体の定義を持つcategoriesテーブルと、ltreeのラベルパスを保持するcategory_pathsテーブルを分離して管理しています。

これは、categoriesテーブルの中にltreeのpathを埋め込んでしまうと、特定のノードは単一のパスしか持てず、ルートが単一であり、特定のノードの親ノードもまた単一である厳密な「木構造」しか表現できません。
しかし、世界史のカテゴリにおいて、この制約は厳しく、カテゴリの階層構造をDAG (有向グラフ)として扱いたい可能性を考慮した結果、分離することにしました。

これにより、あるCategoryのノードが複数のpathを持つことが可能になり、すなわち、複数の親ノードを許容することができるようになります。
model Category {
  id String @id @db.Uuid
  // ...
}

model CategoryPath {
  categoryId String               @id @map("category_id") @db.Uuid
  path       Unsupported("ltree") @unique
  // ...
}
ltreeを使ったDAGの実現については、この記事がとても参考になりました。

https://busta.win/posts/dags-with-materialized-paths-using-postgres-ltree

 実装依存型の是非ジョー・セルコの「プログラマのためのSQLグラフ原論」[1]では、 SQLServerのhierarchyid型を説明した段落の注釈として、
PostgresQLにも、経路列挙モデルを実現するためのltree 型というデータ型が実装されている。もちろん実装依存なので互換性はない。使うことはあまりおすすめしない。
のように指摘されています。

特定のデータベース製品固有のデータ型や拡張機能を使うことのデメリットは認識しておくべきでしょう。当然、mysqlやMicrosoft SQL Serverでは利用できないため、可搬性に問題を抱えることになります。
私たちの場合は、技術的な意思決定は自分たちで判断可能であるという状況であり、また、PostgreSQLから乗り換える予定はなく、今後の見込みとしてもほぼなさそうです。また、AWS RDS, AWS Aurora, PlanetScale, NeonなどのPostgreSQL互換製品でもltree型がサポートされていることも確認しています（実際に、私たちは、AWS RDSを利用しています）。
また、PostgreSQL16ではサポートする文字数が増えたり、2025年8月時点での最新Majorバージョンの17にもltreeに関する変更 (hashサポート)が入っており、継続してメンテナンスされていることもプラスです。
このような理由を考慮して、可搬性に目を瞑っても、ltree型を採用する方が、将来の負債になりにくいだろうという判断をしています。
こうした事情は各社・各サービスによっても異なると思うので、ぜひ慎重に判断してください。

 最後にPostgreSQLのltree型の概観および、COTEN世界史データベースにおける活用例について紹介しました。
RDBは便利な道具ですが、グラフ構造の表現において、銀の弾丸はなく、アプリケーション開発者が、自身のシステムの特性を踏まえて、適切な実装例を考える必要が出てくる場面です。

その中でも、PostgreSQLを使っているのであれば、ltreeは導入しやすく、多くのユースケースに耐えうる実用性を持った実装をして推薦できるものとなっています。
とはいえ、学習用や個人ホビー用として、セルコ[1:1]やKarwin「SQLアンチパターン」[2]を参考に、SQL標準に沿う形で木構造・グラフ構造を実装するのは非常に楽しいことです。仕事はltreeでさくっと片付けておいて、趣味の実装で、ぜひさまざまなグラフをRDBで表現する遊びに興じてみてはいかがでしょうか。

脚注
ジョー・セルコ「プログラマのためのSQLグラフ原論 リレーショナルデータベースで木と階層構造を扱うために」 ↩︎ ↩︎
Bill Karwin「SQLアンチパターン 第2版 ―データベースプログラミングで陥りがちな失敗とその対策」 ↩︎
株式会社COTENPublication
株式会社COTENの世界史データベース開発チームが日々の発見や試行錯誤について発信します。
ltree型でできること

ラベルパスとその制約

ltree型の特性

Read性能

クエリ例

Index戦略

Write性能

世界史データベースでの利用方法

Prismaでの制約と対処法

データベース設計

実装依存型の是非

最後に

Discussion
