経路列挙モデル（準備編）：MySQLで階層化データを使う

(0)

(0)

(0)

(0)Total: 0

階層化されたデータのサンプルとして、４階層のデータを例とし、MySQLで経路列挙モデルを導入して階層問合せを実現します。

各ノードがルートからのパス情報を保持します。
検索クエリの簡素化と効率化に絶大な威力を発揮し、UNIXのファイルシステムやURLの構造にそっくりです。

Amazon アソシエイト Web サービスの名称が、「Product Advertising API」に変わりましたが、その「Product Advertising API」で取り扱う大量の商品 Browse Node ID を納めて検索も早く行いたいという様な要件にぴったりだと思います。

試しに、手元にあるデータ 66,914件で試した所、検索も更新も早く行えて満足のいく結果でした。
※検索速度は、早撃ちのゴルゴ13：約0.17秒、次元：0.3秒というのと同じぐらいのレベルでした。

おしながき

nodeテーブル作成する
nodeテーブルにデータ挿入する
nodeテーブルより全レコードを取得する
関連記事

図１ツリー構造

                             +-----+
                             |Apple|
                             +--+--+
                                |
       +--------------------+---+--------------+------------+
       |                    |                  |            |
+------+-------+ +----------+-----------+ +----+---+ +------+-----+
|コンピューター| |デジタル音楽プレーヤー| |携帯電話| |ソフトウェア|
+------+-------+ +----------------------+ +--------+ +------------+
       |
       +----------------+----------------+
       |                |                |
+------+-------+ +------+-------+ +------+-------+
|デスクトップPC| |ラップトップPC| |ハンドヘルドPC|
+------+-------+ +--------------+ +--------------+
       |
       +----------+
       |          |
   +---+----+ +---+--+
   |タワー型| |一体型|
   +--------+ +------+

図２ツリー構造

Apple
 ├ コンピューター
 │  ├ デスクトップPC
 │  │  ├ タワー型
 │  │  └ 一体型
 │  ├ ラップトップPC
 │  └ ハンドヘルドPC
 ├ デジタル音楽プレーヤー
 ├ 携帯電話
 └ ソフトウェア

図１をMySQLにテーブルとデータを作成します。
各ノードの名前をパスとして作成することもできますが、パスの文字列が巨大化する可能性があり非効率ですのでID番号に変換して使用します。
※ID番号の属性を ZEROFILL で左側0詰めにすると、さらに良いかと思いますが説明を簡素化するため ZEROFILL は除きます。

SQLで表現すると以下のようになります。

nodeテーブル作成する
CREATE TABLE node( node_id INT(10) UNSIGNED NOT NULL AUTO_INCREMENT, name VARCHAR(64) NOT NULL, path varchar(255) NOT NULL, PRIMARY KEY (node_id), UNIQUE KEY (path) );

nodeテーブルにデータ挿入する
INSERT INTO node VALUES ( 1, 'Apple', '.1.'), ( 2, 'コンピューター', '.1.2.'), ( 3, 'デスクトップPC', '.1.2.3.'), ( 4, 'タワー型', '.1.2.3.4.'), ( 5, '一体型', '.1.2.3.5.'), ( 6, 'ラップトップPC', '.1.2.6.'), ( 7, 'ハンドヘルドPC', '.1.2.7.'), ( 8, 'デジタル音楽プレーヤー','.1.8.'), ( 9, '携帯電話', '.1.9.'), (10, 'ソフトウェア', '.1.10.');

nodeテーブルより全レコードを取得する
SELECT * FROM node ORDER BY node_id;

+---------+------------------------+-----------+
| node_id | name                   | path      |
+---------+------------------------+-----------+
|       1 | Apple                  | .1.       |
|       2 | コンピューター         | .1.2.     |
|       3 | デスクトップPC         | .1.2.3.   |
|       4 | タワー型               | .1.2.3.4. |
|       5 | 一体型                 | .1.2.3.5. |
|       6 | ラップトップPC         | .1.2.6.   |
|       7 | ハンドヘルドPC         | .1.2.7.   |
|       8 | デジタル音楽プレーヤー | .1.8.     |
|       9 | 携帯電話               | .1.9.     |
|      10 | ソフトウェア           | .1.10.    |
+---------+------------------------+-----------+

pathはnode_idを区切り文字「.」で表現しています。

また、pathの前後にも区切り文字があります。後々分かると思いますが、これは更新クエリの効率を最大限に上げる為につけています。
UNIXのパスの表現も「/usr/local/src/」のように前後に区切り文字を入れるのは同じ理由かもしれません。

関連記事