え?知らないのと言われないための入れ子集合モデル[理論編]

周りに聞くと結構知らない人が多かったので、(自分も使っているgemを詳しく調査するまで知らなかったけど)
詳しく調べたので、メモがてら
読む時間の目安: 30分くらい(長いです)


入れ子集合モデル(Nested set model)について


木構造、階層構造をRDBで実現するためのテクニックのことをいうそうです。


http://en.wikipedia.org/wiki/Nested_set_model

The nested set model is a particular technique for representing nested sets (also known as trees or hierarchies) in relational databases.


入れ子集合モデルの概要


以下のようなディレクトリ構造を想像してみましょう。
nestedset_1.png


入れ子集合モデルは、各要素の左側、右側に以下のように番号をつけます。
nestedset_2.png
この時つける番号は以下のルールに従っている必要があります。


  • 各番号は一度しか使われないこと
  • ある要素(Xとする)の子要素(Yとする)は以下の関係を示すこと
    ※(L)は左側の番号, (R)は右側の番号を示す
    X(L) < Y(L) < Y(R) < X(R)
  • ある要素(Xとする)の右側に位置する要素(Yとする)について以下の関係を示すこと
    X(R) < Y(L)

まぁ左側から一筆書きにして、番号を振っていけばOKです


入れ子集合モデルにおけるデータの取り出し方
なお、慣習的に左の番号をlft, 右の番号をrgtとしているようなので、今後はそれに従います。


位置関係、順序関係を維持したまま全データを取り出すには?


左の番号が小さいほうが順序関係上上位にあたるものとし、以下のような順序でデータを取り出したい場合を想定します。


[ a, a1, a1-1, a2, a2-1, a2-2, b, b1 ]

これはlftの昇順でデータを取り出すことで簡単に実現します。


SELECT * FROM tablename ORDER BY lft ASC

ある要素の先祖(親)を取り出すには?


[a2-2]の先祖を取り出す方法を考えてみます。
取り出したい要素は, [a] と [a2]です。
値の関係をみてみると、[a], [a-2]は共にlftが [a2-2]より小さいことがわかります。
また、rgtは [a2-2]より大きいことがわかります。
このことから以下のようなSQLになります


SELECT * FROM tablename where lft < 9 AND rgt > 10;

つまり、ある要素の先祖をたどるには、その要素のlftより小さくかつrgtより大きい要素を検索するとなります


ある要素の子孫を取り出すには?


[a]の子孫を取り出す方法を考えてみます。
取り出したい要素は, [a1], [a1-1], [a2], [a2-1], [a2-2]です。
値の関係をみてみると、 それぞれ、 lftが [a]より大きく、rgtが [a]より小さいことがわかります。
このことから以下のSQLになります。


SELECT * FROM tablename where lft > 1 AND rgt < 12;

つまり、ある要素の子孫をたどるには、その要素のlftより大きく、かつrgtより小さい要素を検索するとなります


ここまでが、入れ子集合モデルの基本です。
一般的に用いられているparent_idを用いた方法と比べた場合より検索性が優れていることがお分かりいただけたでしょうか?


注) 検索について、このモデルでいくつかの問題点(ある要素の直接の子孫を一発で取り出すことができない([a1], [a2]を一回で取り出す方法が存在しない)など)がありますが、
それは、このモデルの派生によって解決可能ですので、後ほど解説します。


入れ子集合モデルの大きな問題点


入れ子集合モデルは、既にlft, rgtが設定済みの場合で、主に検索でしか使わないような場合には素晴らしいパフォーマンスをみせてくれますが、
lft, rgtを設定する作業が非常に大変です。
以下に作業手順を解説します。


要素を追加する場合


先ほどの構造に要素を追加する場合の作業をみてみましょう。
nestedset_2.png


上図の[a2-1]の子要素として[a2-1-1]を追加してみます。
ここで、色がついた要素が新たに追加された要素。下線がついている数字は、数字に変更があったものを示します。
nestedset_3.png


理論的には、以下のように要素の数字を再構築します。


  • 親となる要素のrgtを追加される要素のlftとし、rgtはそのlftに1を加算した値を設定する
    (a2-1のrgtは8なので、追加される要素のlftは9, rgtは10となる)
  • 追加される要素に設定されるrgtより大きいlftをもつ要素のlftを2加算する。
    同様に、追加される要素に設定されるrgtより大きいrgtをもつ要素について、2加算する

要素の追加に関しては、そう複雑な作業ではないのですが、要素を追加するだけなのに、更新対象が非常に広くなっていることがわかるかと思います。
parent_idとsornoを用いたモデルにおいては、更新対象は、同一のparent_idを持ち、指定されたsortno以上の要素に限られますので、この点では、parent_idを用いたモデルのほうが効率的になります。


要素を移動する場合


同様に先ほどの構造を元に移動させる場合の手順について解説します。
今回は[a2]を[a1]の子要素として移動させ、かつ[a1-1]より左側に配置する場合を考えます。
この際[a2]の子孫については、その関係を保持したままとします。


移動の場合は、追加と異なり、数字の更新が加算だけでなく、減算も発生する場合があります。
その為、処理はより複雑になります。


元の形は以下です。
nestedset_2.png


完成形は以下のようになります。
nestedset_4.png
先程と同様に更新が必要な数字には下線をつけてあります。


この場合は、以下のような更新が必要になります。


  • [a2]のlftより大きく、rgtより小さい要素は、lft, rgtそれぞれを -3する
  • lftが3から5である要素のlftを+6する(対象が[a1-1]だけであることに注意)
  • rgtが3から5である要素のrgtを+6する(対象は[a1]と[a1-1]

とここまで来ると、わけがわからなくなり、プログラムにおける実装もどうすれば良いのかわからなくなってしまいます。
削除も同様に非常に複雑な操作が必要になり、プログラム上での実装も非常に厄介なものになります。
(ここでは、追加、移動、削除のオペレーションにおける更新対象のレコード数が多くなることをご理解いただければと思います。)


入れ子集合モデルのおける移動の解法の例


要素の移動をプログラム的にどのように実装すれば良いのかを一応掲載しておきます。
なお、awesome_nested_setの実装を解説したものとなります。


awesome_nested_setにおいて、移動というオペレーションは、基準となる要素の左側、右側、子供の3つとroot(一番上の要素)に移動するの4つ可能です。
それぞれをSQL1つで処理しているのも興味深いところです。(諸処問題はありますが)
各要素の移動量の計算を以下のように処理をしています。


移動量と移動対象の計算のため、[a, b, c, d]の4つの値を求める


[手順1] 移動する要素をXとします。


  • a を Xのlftとする
  • b をXのrgtとする
  • c をXのlft - 1とする

dはオペレーションの種類によって変わり、以下のように計算されます。
ここで、基準となる要素をYとします。(例: XをYの子として追加する)


  • 子とする場合 Yのrgtとする
  • 左側に移動する場合 Yのlftとする
  • 右側に移動する場合 Yのrgt + 1とする
  • root要素にする場合 1とする

[手順2] ここで c > d となる場合は、以下のように値を更に調整する


  • cを Xのrgt + 1とする
  • dを 現在のdの値 - 1とする

[手順3] 計算が終わったので、a, b, c, dを用いて、要素のlft, rgtを更新していく


  • [a, b, c, d]を昇順に並べ替え、それぞれをa', b', c', d'とする
  • a' から b'の範囲のlft, rgtをそれぞれ d' - b' する
  • c' から d'の範囲のlft, rgtをそれぞれ、 a' - c' する

以上で移動処理が完了します。


実際に先ほどの移動例を用いて、このアルゴリズムで正しく動作するか調べてみましょう。


移動前
nestedset_2.png


移動後
nestedset_4.png


この場合は[a2]を[a1-1]の左側に移動するというオペレーションになります。


[手順1] a = 6, b = 11, c = 5, d = 3
[手順2] は c > dを満たさないため、スキップします。
[手順3] a' = 3, b' = 5, c' = 6, d' = 11
数字が3から5 を (d' - b') = +6 する
数字が6から11を (a' - c') = -3 する
うまくいく感じですね!


depthとparent_idについて


awesome_nested_setやその他のnestedsetを実現するライブラリ群の多くは、depth(深さ)とparent_id(親ID)を含めている場合が多いです。
その理由としては、直接の子孫(子)、直接の祖先(親)や兄弟を容易に検索可能にするためです。
depthがある場合では祖先を1つ辿る場合(親を調べる)は以下で検索できます。
(LFTは基準となる要素のlft, RGTは基準となる要素のrgt, DEPTHは基準となる要素のdepthを示します)


SELECT * FROM tablename WHERE lft < LFT AND rgt > RGT AND depth = DEPTH -1;

-1の部分を-2にすれば、2つ辿ることができます。


parent_idがある場合は、兄弟を容易に検索可能にします。(parent_idとsortnoを用いた実装と同じ機能)
(PARENTは基準となる要素のparent_idを示します。)


SELECT * FROM tablename WHERE parent_id = PARENT;

順序を含める場合は以下のようにします。


SELECT * FROM tablename WHERE parent_id = PARENT ORDER BY lft ASC;

なお、parent_idがない場合において、兄弟を検索するには以下のように2段階踏みます。


  • 親を調べる
    SELECT * FROM tablename WHERE lft < LFT AND rgt > RGT AND depth = DEPTH - 1;

  • 調べた親の1世代子供を調べる
    SELECT * FROM tablename WHERE lft > LFT AND rgt < RGT AND depth = DEPTH + 1;

勿論、depth, parent_idを含めた実装の場合は、その分更新の手間が増えるため、より重くなります。


雑記


nestedsetにおいて、使用するライブラリがどのように実装されているかをみるのは非常に大事になります。
用途に応じたライブラリ選定をすると良いかと思います。
いくつか実装をみましたが、lft, rgtを別々に更新していたり、ルートノードを複数もてるが、
ルートノードの左番号は必ず1にするという実装だったりと、、、
awesome_nested_setの削除などのアルゴリズムは要望があれば解説します。。。

スポンサーサイト
上記広告は1ヶ月以上更新のないブログに表示されています。新しい記事を書くことで広告を消せます。