こんにちは、株式会社ビービットの玉越です。

表題の通り、今日は木構造を効率的に表現する方法について情報がないかなと思
い、徒然に質問してみました。

木構造は表形式で表現しにくく、いつも困るのですが、皆さんはどのようにされ
ているでしょうか？
（リスト構造も同様ですね）


まずは普通に再帰構造が思い浮かびます。

( id        INT PRIMARY KEY,
  name      VARCHAR(128),
  parent_id INT )

これですと、木の末尾の要素にアクセスするのは木の段数だけSELECTを発行しな
ければならないので、非常に時間が掛かってしまいます。


そこで、ルートからそのノードへのパスをそのまま持ってしまう方法もあるかも
しれません。

( id   INT PRIMARY KEY,
  name VARCHAR(128),
  path BLOG(767) UNIQUE )

pathは、ノード番号のリストを文字列展開したものとでもします。
例えば、ノード1の下のノード2の下のノード5であれば、1,2,5という感じです。
より具体的には0x00010x00020x0005というバイナリ表現にするとビットを効率的
に利用できます。

この場合、MySQLの制約により、INTは4バイトなのでpathの長さは767/4=191まで
に制限されます（MyISAMエンジンであれば1000/4=250まで）。

また、もう一つデメリットとしてはパスを全て持つのでデータ量が増えます。


という感じでつらつら考えたのですが、他に何か表現方法はあるものでしょうか？


--
株式会社ビービット　玉越 大輝
ユーザビリティ コンサルタント
beBit,Inc. Tamakoshi Hiroki hiroki.tamakoshi@xxxxxxxxxx
--------------------------------------------------------
〒105-0001 東京都港区虎ノ門1-18-1 虎ノ門10森ビル7F
TEL: 03-3509-7602 / FAX: 03-3509-7605
URL: http://www.bebit.co.jp/
--------------------------------------------------------
◆◆◆お知らせ◆◆◆
・ビービット新刊書籍 『ユーザ中心ウェブサイト戦略』発売
  http://www.bebit.co.jp/news/2006/book.html
  http://www.amazon.co.jp/gp/product/4797333529/