RDBMSでのツリー表現

gistfile1.txt

## RDBMSでのツリー表現

RDBMSでツリーデータを表現するためには大きく4つの手法がある

* Adjacency relation
* Nested sets
* Materialized path
* Nested intervals

## ツリーデータはいつ使う？
* カテゴリ階層の表現
* ディレクトリの表現
* 家系図は、ちょっと工夫しないと使えないかも

## Adjacency relation

parent_idを保持しておく

create table tree (
  id,
  parent_id,
  contents
)

###特徴
* 子孫の列挙に時間がかかる
* oracle の階層演算を使えばsqlだけで表現できるが、速度はデータ数に比例する

##Nested sets
lft, rgtフィールドを持つ。

子要素は親要素のlft, rgtに挟まれるように値をセットする。


  Folder1
  ∟File1
  ∟Folder2
  　∟File21
  　∟File22
  ∟Folder3
  　∟File31
  ∟Folder4
  　∟File41

↑のようなディレクトリ階層は、以下のデータで表現できる


Folder1.lft = 1 .rgt = 18
    File1  .lft = 2 .rgt = 3
    Folder2.lft = 4 .rgt = 9
        File21 .lft = 5 .rgt = 6
        File22 .lft = 7 .rgt = 8
    Folder3.lft = 10    .rgt = 13
        File31 .lft = 11    .rgt = 12
    Folder4.lft = 14    .rgt = 17
        File41 .lft = 15    .rgt = 16

### 特徴

* 子孫要素の列挙がすごく速い(lft, rgtの間にある要素を抽出するだけで良い)
* 子要素の抽出は遅い
* 親要素の抽出は遅い
* 祖先要素の列挙は遅い
* 挿入、移動がすごく遅い

## Materialized path
* path文字列を持っておき、これを使って階層を表現する
* パス文字列の例: /1/3/7/

### 特徴
* 子孫要素の列挙は速い
* 子要素の列挙は遅い
* 祖先要素の列挙はトリッキーだが速い
* 親要素の抽出は速い
* 挿入は簡単。移動は簡単だが、あまり効率的ではない


## Nested intervals
Nested Setsの問題を解決したものらしい。 その分複雑になってる。
概念的には、範囲を数学的に決定して、再構成に時間がかからないようにしたものらしい

### 特徴

* 子孫要素の列挙は速い
* 祖先要素の列挙はトリッキーだが速い
* 子要素の列挙は速い
* 親要素の抽出は速い
* データ構造ややこしいので、手動での修正が難しい気がする(わかってないけど)

## 結論

* Adjacency relationは単純だが、子孫要素の列挙以外は速い。子要素の列挙の必要がなければこれでいいと思う。
* Nested sets、データ構造複雑だし、データの更新に時間かかるし、使う価値ない。
* Materialized path、検討する価値ある。
* Nested intervals、もうちょっと調べないとわからない。