17

クロージャ テーブルとして格納された階層データ構造の並べ替えに関する問題を解決する方法を教えてください。

この構造を使用して、Web サイトのメニューを保存したいと考えていました。すべて正常に動作しますが、問題は、正確なサブツリーをカスタム順序でソートする方法がわからないことです。現時点では、アイテムがデータベースに追加された順序でツリーがソートされます。

私の構造は、Closure Tables に関するBill Karwin の記事やその他の投稿に基づいています。

以下は、いくつかの DEMO データを含む私の MySQL データベース構造です。

--
-- Table `category`
--

CREATE TABLE IF NOT EXISTS `category` (
  `id` int(11) NOT NULL AUTO_INCREMENT,
  `name` varchar(100) COLLATE utf8_czech_ci NOT NULL,
  `active` tinyint(1) NOT NULL,
  PRIMARY KEY (`id`)
) ENGINE=InnoDB;


INSERT INTO `category` (`id`, `name`, `active`) VALUES
(1, 'Cat 1', 1),
(2, 'Cat 2', 1),
(3, 'Cat  1.1', 1),
(4, 'Cat  1.1.1', 1),
(5, 'Cat 2.1', 1),
(6, 'Cat 1.2', 1),
(7, 'Cat 1.1.2', 1);

--
-- Table `category_closure`
--

CREATE TABLE IF NOT EXISTS `category_closure` (
  `id` bigint(20) NOT NULL AUTO_INCREMENT,
  `ancestor` int(11) DEFAULT NULL,
  `descendant` int(11) DEFAULT NULL,
  `depth` int(11) DEFAULT NULL,
  PRIMARY KEY (`id`),
  KEY `fk_category_closure_ancestor_category_id` (`ancestor`),
  KEY `fk_category_closure_descendant_category_id` (`descendant`)
) ENGINE=InnoDB;

INSERT INTO `category_closure` (`id`, `ancestor`, `descendant`, `depth`) VALUES
(1, 1, 1, 0),
(2, 2, 2, 0),
(3, 3, 3, 0),
(4, 1, 3, 1),
(5, 4, 4, 0),
(7, 3, 4, 1),
(8, 1, 4, 2),
(10, 6, 6, 0),
(11, 1, 6, 1),
(12, 7, 7, 0),
(13, 3, 7, 1),
(14, 1, 7, 2),
(16, 5, 5, 0),
(17, 2, 5, 1);

1 つのツリーに対する SELECT クエリは次のとおりです。

SELECT c2.*, cc2.ancestor AS `_parent`
FROM category AS c1
JOIN category_closure AS cc1 ON (cc1.ancestor = c1.id)
JOIN category AS c2 ON (cc1.descendant = c2.id)
LEFT OUTER JOIN category_closure AS cc2 ON (cc2.descendant = c2.id AND cc2.depth = 1)
WHERE c1.id = __ROOT__ AND c1.active = 1
ORDER BY cc1.depth

クエリが取得する __ROOT_ = 1 の DEMO インスタンスの場合:

id  name        active     _parent
1   Cat 1       1          NULL
3   Cat 1.1     1          1
6   Cat 1.2     1          1
4   Cat 1.1.1   1          3
7   Cat 1.1.2   1          3

しかし、たとえば、Cat 1.1 と Cat 1.2 の順序を変更する必要がある場合はどうすればよいでしょうか (名前またはカスタム オーダーに従って)。

ブレッドクラムのソリューション (ブレッドクラムでソートする方法) を見たことがありますが、それらを生成および変更する方法がわかりません。

4

1 に答える 1

18

この質問は、Closure Table だけでなく、階層データを格納する他の方法についても頻繁に出てきます。どのデザインでも簡単ではありません。

Closure Table について私が思いついた解決策には、結合を 1 つ追加する必要があります。ツリー内のすべてのノードは、「ブレッドクラム」タイプのクエリのように、その先祖のチェーンに参加します。次に GROUP_CONCAT() を使用してブレッドクラムをコンマ区切りの文字列に折りたたみ、ID 番号をツリーの深さで並べ替えます。これで、ソートできる文字列ができました。

SELECT c2.*, cc2.ancestor AS `_parent`,
  GROUP_CONCAT(breadcrumb.ancestor ORDER BY breadcrumb.depth DESC) AS breadcrumbs
FROM category AS c1
JOIN category_closure AS cc1 ON (cc1.ancestor = c1.id)
JOIN category AS c2 ON (cc1.descendant = c2.id)
LEFT OUTER JOIN category_closure AS cc2 ON (cc2.descendant = c2.id AND cc2.depth = 1)
JOIN category_closure AS breadcrumb ON (cc1.descendant = breadcrumb.descendant)
WHERE c1.id = 1/*__ROOT__*/ AND c1.active = 1
GROUP BY cc1.descendant
ORDER BY breadcrumbs;

+----+------------+--------+---------+-------------+
| id | name       | active | _parent | breadcrumbs |
+----+------------+--------+---------+-------------+
|  1 | Cat 1      |      1 |    NULL | 1           |
|  3 | Cat  1.1   |      1 |       1 | 1,3         |
|  4 | Cat  1.1.1 |      1 |       3 | 1,3,4       |
|  7 | Cat 1.1.2  |      1 |       3 | 1,3,7       |
|  6 | Cat 1.2    |      1 |       1 | 1,6         |
+----+------------+--------+---------+-------------+

警告:

  • 「1,3」、「1,6」、および「1,327」をソートすると意図した順序にならない可能性があるため、id 値の長さは均一にする必要があります。ただし、「001,003」と「001,006」と「001,327」を並べ替えると、. したがって、id 値を 1000000+ から開始するかZEROFILL、category_closure テーブルの祖先と子孫に使用する必要があります。
  • このソリューションでは、表示順序はカテゴリ ID の番号順に依存します。id 値のその数値の順序は、ツリーを表示する順序を表していない場合があります。または、数値の id 値に関係なく、自由に表示順序を変更したい場合があります。または、同じカテゴリ データを、それぞれ異なる表示順序で複数のツリーに表示することができます。
    もっと自由が必要な場合は、並べ替え順序の値を ID とは別に保存する必要があり、ソリューションはさらに複雑になります。しかし、ほとんどのプロジェクトでは、ショートカットを使用して、ツリーの表示順序としてカテゴリ ID の 2 つの役割を与えることができます。

あなたのコメントについて：

はい、「兄弟並べ替え順序」をクロージャー テーブルの別の列として保存しancestor、パンくずリスト文字列を作成する代わりにその値を使用できます。しかし、それを行うと、多くのデータ冗長性が発生します。つまり、指定された祖先は複数の行に格納され、そこから派生するパスごとに 1 つずつ格納されます。そのため、これらすべての行の兄弟並べ替え順序に同じ値を格納する必要があり、異常が発生するリスクが生じます。

別の方法として、ツリー内の個別の祖先ごとに1 つの行のみを含む別のテーブルを作成し、そのテーブルに結合して兄弟の順序を取得することもできます。

CREATE TABLE category_closure_order (
  ancestor INT PRIMARY KEY,
  sibling_order SMALLINT UNSIGNED NOT NULL DEFAULT 1
);

SELECT c2.*, cc2.ancestor AS `_parent`,
  GROUP_CONCAT(o.sibling_order ORDER BY breadcrumb.depth DESC) AS breadcrumbs
FROM category AS c1
JOIN category_closure AS cc1 ON (cc1.ancestor = c1.id)
JOIN category AS c2 ON (cc1.descendant = c2.id)
LEFT OUTER JOIN category_closure AS cc2 ON (cc2.descendant = c2.id AND cc2.depth = 1)
JOIN category_closure AS breadcrumb ON (cc1.descendant = breadcrumb.descendant)
JOIN category_closure_order AS o ON breadcrumb.ancestor = o.ancestor
WHERE c1.id = 1/*__ROOT__*/ AND c1.active = 1
GROUP BY cc1.descendant
ORDER BY breadcrumbs;

+----+------------+--------+---------+-------------+
| id | name       | active | _parent | breadcrumbs |
+----+------------+--------+---------+-------------+
|  1 | Cat 1      |      1 |    NULL | 1           |
|  3 | Cat  1.1   |      1 |       1 | 1,1         |
|  4 | Cat  1.1.1 |      1 |       3 | 1,1,1       |
|  7 | Cat 1.1.2  |      1 |       3 | 1,1,2       |
|  6 | Cat 1.2    |      1 |       1 | 1,2         |
+----+------------+--------+---------+-------------+
于 2012-12-28T18:53:35.037 に答える