QA@IT

SQLで2分木構造の左右の要素数を取るクエリは書けますか?

4447 PV

2分木(BinaryTree)構造において、ある要素(node)の左右それぞれの個数をSQL文一回で算出できるようなデータ構造とSQLをご存知でしたら教えて下さい。
現在のデータ構造は以下のとおりです。

id(int)
left(int)
parent(int)
right(int)

回答

再帰クエリ(WITH RECURSIVE)を使えば可能です。

http://ja.wikipedia.org/wiki/再帰クエリ

ただし、DBMSによって実装状況が異なるのでお使いのDBMSで使えるかは確認してください。

※再帰クエリが実装されていない場合はこういう方法もあります
http://www.geocities.jp/mickindex/database/db_tree_ns.html

試しに書いてみました。DBはPostgreSQL 9.1です。

CREATE TABLE tree(
    id int,
    leftnode int,
    parentnode int,
    rightnode int)
;
INSERT INTO tree
VALUES
    (1, 2, NULL, 3),
    (2, 4, 1, NULL),
    (3, 5, 1, 6),
    (4, NULL, 2, NULL),
    (5, NULL, 3, NULL),
    (6, NULL, 3, NULL)
;  
WITH RECURSIVE r AS (
    SELECT
        *
    FROM
        tree
    WHERE
        id = 1
    UNION
    SELECT
        tree.*
    FROM
        r
    INNER JOIN
        tree ON tree.parentnode = r.id
)
SELECT
    *
FROM
    r
;
 id | leftnode | parentnode | rightnode
----+----------+------------+-----------
  1 |        2 |            |         3
  2 |        4 |          1 |
  3 |        5 |          1 |         6
  4 |          |          2 |
  5 |          |          3 |
  6 |          |          3 |
(6 rows)

WITH RECURSIVE r AS (
    SELECT
        *
    FROM
        tree
    WHERE
        id = 2
    UNION
    SELECT
        tree.*
    FROM
        r
    INNER JOIN
        tree ON tree.parentnode = r.id
)
SELECT
    *
FROM
    r
;
 id | leftnode | parentnode | rightnode 
----+----------+------------+-----------
  2 |        4 |          1 |          
  4 |          |          2 |          
(2 rows)

WITH RECURSIVE r AS (
    SELECT
        *
    FROM
        tree
    WHERE
        id = 3
    UNION
    SELECT
        tree.*
    FROM
        r
    INNER JOIN
        tree ON tree.parentnode = r.id
)
SELECT
    *
FROM
    r
;
 id | leftnode | parentnode | rightnode
----+----------+------------+-----------
  3 |        5 |          1 |         6
  5 |          |          3 |
  6 |          |          3 |
(3 rows)
編集 履歴 (2)
  • ありがとうございます。
    ターゲットのDBMSがMySQL5系なので、現在のところ再帰クエリは使用不可のようです。
    ※次期バージョンでは実装の予定とのことです。
    PostgreSQLに変更もありでしたが、ストアドで追っかけるしか無いかなと考えています。
    「入れ子集合モデル」の記事は読んでいましたので、参考にさせて頂きました。
    サンプルまで提示していただいて、恐縮です。
    -

SNMPなどで使われているMIBツリーのような感じにして見てはどうでしょうか?
MIBツリーでは、全てのノードにoidが設定されています。

CREATE TABLE node(id int, oid varchar);

例えば、左ノードのoidを0、右ノードのoidを1とした場合、
ROOTノードから、左→左→右と辿ったところにあるノードAのoidは0.0.1となります。
あとは、oidに0.0.1.0.を含むoidを持つノードがノードAの左側、oidに0.0.1.1.を含むoidを持つノードがノードAの右側になります。

SELECT count(*) FROM node WHERE oid LIKE '0.0.1.0.%';
SELECT count(*) FROM node WHERE oid LIKE '0.0.1.1.%';
編集 履歴 (0)
  • ありがとうございます。
    やはり、データ構造をダイレクトに持たせる方が簡素化できますね。
    あとは階層が深くなった場合の効率を考えてみます。
    -

2文木は再帰的な構造なため各レコードに該当する情報を持っていないと
1回のSQL文で取得するのは厳しいかと思います。データ登録時各Node毎の
左右の要素数をそれぞれ取得し保存すると良いと思います。

編集 履歴 (0)
  • ありがとうございます。
    要素毎にカウント数をもたせると、階層が深くなったとき更新時のオーバーヘッドが避けられません。
    ストアドで追っかけてカウントする事も考えましたが、根本的な解決にはならないので、有効なデータ構造が無いか探しています。
    -
ウォッチ

この質問への回答やコメントをメールでお知らせします。