はじめに

Rails + RDB を使っていて、ツリー構造を持ちたくなることありますよね。
例えば企業の部署を構造的に管理しなければならないときとか、ディレクトリ構造を保持しなければならないときとか。
そういうときに、皆さんどうやって管理されてますか？

動機

僕は今までオブジェクトをシリアライズして text型のフィールドに突っ込むことでやり過ごしてきました。
実際、この方法で特に問題なかったんですが、ある案件で、サブツリーを取り出して、コピーしたいなーっていう要件が出てきました。
サブツリーを取り出す？・・・それってまずサブツリーを検出するアルゴリズムを実装しないといけないよね・・・どこに持つ？共通化したいな？どこに持つ？

調査

というわけで、そもそもツリー構造って RDB でみんなどう扱っているの？っていうのを知りたくて情報の海（Google）に飛び込みました。

するとそこで目にしたのは、"Nested Set Model" というデータ構造。
あー、昔勉強しましたねこれ！
詳細は省きますが、ツリー構造を集合だと思うとイケてるよってものです。
詳しく知りたい人は Appendix をご覧ください。

それで、アルゴリズムにあたりを付けたところで github で実装を調査すると、以下のようなものが見つかりました。

gem調査

acts_as_tree

（旧）https://github.com/rails/acts_as_tree
（新）https://github.com/amerine/acts_as_tree

なぜか rails のオーガニゼーションから別のところに移管されていました。

parent_id を指定していることから、隣接リストモデルで実装されているようです。
シリアライズとあまり変わらない気がするのでちょっと無視。

closure_tree

これも parent_id 指定してるから隣接リストモデルかな？またちょっと無視

awesome_nested_set

lft、rgt を定義しているので、入れ子集合モデルのようです。
parent_id も同時に指定しているのはパフォーマンスのためでしょう。

というわけで、少しこの gem の中身を見てみたんですが、left とか right を操作するのがちょっと嫌だなと思いました。僕はツリー構造の操作に興味があるのであって、その実装は（少なくとも使用者であるときには）無視できるべきだという感覚からです。

調査結果

Google の検索結果 1ページに目には、めぼしいものがなかった。

次のアクション

なかったので、作れば良いかと思って作りました。
エンジニアたるもの、欲しいものは自分で作れの精神ですね。
（作り始めた後でより良い物が見つかることも多いですけど、そんなことでへこたれませ……）

メソッドの詳細は README に書いているので省略しますが、高速であることと、メソッドが直感的であることを目指してデザインしました。

おわりに

ツリー構造を Rails で扱う方法を簡単に調査して、結局自分で作りました。
僕は、適当にツリーっぽいものを構築した後で、一気にガチャってツリーを再構築できるようなメソッドだったり、オブジェクトからツリーを構築できるメソッドだったりが欲しいんですけど、そういうリクエストやバグがあれば github の issues/pull-requests に投げていただければ幸いです。できればそれほど大きくない限り PR の方が良いです。

あと、パフォーマンス上、生の SQL 書いているところがあって、それは他の DB だとどうかなーって感じがするので、テスト追加の PR とかもお待ちしてます。

Appendix

Nested set model - wiki pedia
https://en.wikipedia.org/wiki/Nested_set_model
SQLで木と階層構造のデータを扱う（１）―― 入れ子集合モデル
http://www.geocities.jp/mickindex/database/db_tree_ns.html