Ruby
Rails
TreeStructuredData
NestedSetModel

Rails でツリー構造をシリアライズして RDB に持つことに抵抗があるときに読む投稿

More than 1 year has passed since last update.


はじめに

Rails + RDB を使っていて、ツリー構造を持ちたくなることありますよね。

例えば企業の部署を構造的に管理しなければならないときとか、ディレクトリ構造を保持しなければならないときとか。

そういうときに、皆さんどうやって管理されてますか?


動機

僕は今までオブジェクトをシリアライズして text型のフィールドに突っ込むことでやり過ごしてきました。

実際、この方法で特に問題なかったんですが、ある案件で、サブツリーを取り出して、コピーしたいなーっていう要件が出てきました。

サブツリーを取り出す?・・・それってまずサブツリーを検出するアルゴリズムを実装しないといけないよね・・・どこに持つ?共通化したいな?どこに持つ?


調査

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

するとそこで目にしたのは、"Nested Set Model" というデータ構造。

あー、昔勉強しましたねこれ!

詳細は省きますが、ツリー構造を集合だと思うとイケてるよってものです。

詳しく知りたい人は Appendix をご覧ください。

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


gem調査


acts_as_tree

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

parent_id を指定していることから、隣接リストモデルで実装されているようです。

シリアライズとあまり変わらない気がするのでちょっと無視。


closure_tree

https://github.com/mceachen/closure_tree

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


awesome_nested_set

https://github.com/collectiveidea/awesome_nested_set

lftrgt を定義しているので、入れ子集合モデルのようです。

parent_id も同時に指定しているのはパフォーマンスのためでしょう。

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


調査結果

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


次のアクション

なかったので、作れば良いかと思って作りました。

エンジニアたるもの、欲しいものは自分で作れの精神ですね。

(作り始めた後でより良い物が見つかることも多いですけど、そんなことでへこたれませ……)

https://github.com/chase0213/fast_tree

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


おわりに

ツリー構造を Rails で扱う方法を簡単に調査して、結局自分で作りました。

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

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


Appendix