Blog株式会社CINCのエンジニアチームが日々習得した技術やTipsを公開するブログです2018-10-01RDBで経路列挙モデルを用いて木構造を扱うCore開発部のTです。再帰的な関連を持ったデータをリレーショナルデータベースで扱う機会があったので紹介したいと思います。そもそもMySQLをはじめとしたリレーショナルデータベースは、列と行で構成されるテーブルの構造体であり、木構造のような再帰的構造を表現することが苦手とされています。現在では、リレーショナルデータベースで階層構造を扱うにあたり、いくつかの解法が存在します。隣接リストモデル入れ子集合モデル経路列挙型モデル今回私は、経路列挙モデルを取り上げることにします。経路列挙モデル経路列挙モデルとは、対象ノードの先祖までの経路を属性として格納することで、木構造を表現するモデルです。下記のディレクトリ構造を例に見ていきます。経路列挙モデルでは、上記の構造を下記のように表現することができます。/top/technology/programming/7.0/または、各ノードのパス文字列を数値に置き換えることで経路(path)を表現してもいいでしょう。/1/2/1/1/1/このモデルが優れているのは、各ノードまでの絶対パスをそれぞれのレコードに持つことで可能にするその経路探索のパフォーマンスです。「programming」の先祖を取得するには、下記のクエリで可能です。'%');このクエリは/top/%、/top/technology/%、/top/technology/programming/%の各パターンとマッチします。「programming」の子孫はWHERE句の条件式を逆順にすることで取得ができます。'%');/top/technology/programming/の子孫をパス文字列の前方一致で検索をかけます。各ノードは自身の包含関係のためテーブル上に置いて常に一意になるためインデックを使用しての検索も可能になります。その際、pathカラムはパス文字列の文字列長にカラムのサイズが左右されるため、上記で提示した数値パスに置き換えることも検討に入れても良いかもしれません。各ノードの深さは、パスの文字列長からパスを削除したパス文字列を減算して、両端の/(スラッシュ)分削除することで取得できます。directories;新しいノードの追加には、多少複雑ですが、正規表現を使用することで可能になります。「machinelearning」というディレクトリを、「programming」、「database」、「server」の3階層目に追加します。3階層目に一意なディレクトリがいくつ存在するか、をカウントすることがこの処理において重要です。正規表現で3階層目に存在するディレクトリを抽出します。BYで重複を弾いたカラム数をカウントしている。クエリは下記の様になります。path_str;出力の結果が、3階層目に存在する既存のディレクトリ数になるので、2階層目までのパスと+1してあげた値を連結したあものが新規ノードの数値パスになります。経路列挙モデルを用いてデータ構造を設計することで、任意の数(正確にはカラムで指定したデータ型の許容バイト数まで)の包含関係を単純なクエリで取得することが可能であることを紹介してきました。経路列挙モデルも万能ではありません。各レコードに自身までの経路をすべて保持しているため、更新や削除の処理が複雑化してしまうという欠点もあります。したデメリットも把握した上で、今回のディレクトリ構造のように、頻繁な更新のない階層構造データをRDBで扱う場合には一つの選択肢になるかと思います。CINC開発部のTです。»プロフィール株式会社CINCのエンジニアチームです。日々マーケティングツールの開発やR&Dを行っています。月別アーカイブスターをつけました引用をストックしましたストック一覧を見る閉じる引用するにはまずログインしてくださいログイン閉じる引用をストックできませんでした。再度お試しください閉じる限定公開記事のため引用できません。