はじめに
Rails + RDB を使っていて、ツリー構造を持ちたくなることありますよね。
例えば企業の部署を構造的に管理しなければならないときとか、ディレクトリ構造を保持しなければならないときとか。
そういうときに、皆さんどうやって管理されてますか？
動機
僕は今までオブジェクトをシリアライズして text型のフィールドに突っ込むことでやり過ごしてきました。
実際、この方法で特に問題なかったんですが、ある案件で、サブツリーを取り出して、コピーしたいなーっていう要件が出てきました。
サブツリーを取り出す？・・・それってまずサブツリーを検出するアルゴリズムを実装しないといけないよね・・・どこに持つ？共通化したいな？どこに持つ？
調査
というわけで、そもそもツリー構造って RDB でみんなどう扱っているの？っていうのを知りたくて情報の海（Google）に飛び込みました。
するとそこで目にしたのは、"Nested Set Model" というデータ構造。
あー、昔勉強しましたねこれ！
詳細は省きますが、ツリー構造を集合だと思うとイケてるよってものです。
詳しく知りたい人は Appendix をご覧ください。
それで、アルゴリズムにあたりを付けたところで github で実装を調査すると、以下のようなものが見つかりました。
gem調査
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