Mengurutkan subpohon dalam struktur data hierarki tabel penutupan

Pertanyaan ini sering muncul tidak hanya untuk Tabel Penutupan tetapi juga untuk metode lain dalam menyimpan data hierarkis. Tidak mudah dalam desain apa pun.

Solusi yang saya buat untuk Tabel Penutupan melibatkan satu gabungan tambahan. Setiap simpul di pohon bergabung ke rantai leluhurnya, seperti kueri jenis "remah roti". Kemudian gunakan GROUP_CONCAT() untuk menciutkan remah roti menjadi string yang dipisahkan koma, mengurutkan nomor id berdasarkan kedalaman di pohon. Sekarang Anda memiliki string yang dapat digunakan untuk mengurutkan.

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         |
+----+------------+--------+---------+-------------+

Peringatan:

• Nilai id harus memiliki panjang yang seragam, karena pengurutan "1,3" dan "1,6" dan "1,327" mungkin tidak memberikan urutan yang Anda inginkan. Tapi menyortir "001.003" dan "001.006" dan "001.327" akan. Jadi, Anda harus memulai nilai id Anda di 1000000+, atau gunakan ZEROFILL untuk leluhur dan keturunan dalam tabel kategori_penutupan.
• Dalam solusi ini urutan tampilan tergantung pada urutan numerik dari id kategori. Urutan numerik nilai id itu mungkin tidak mewakili urutan yang Anda inginkan untuk menampilkan pohon. Atau Anda mungkin menginginkan kebebasan untuk mengubah urutan tampilan terlepas dari nilai id numerik. Atau Anda mungkin ingin data kategori yang sama muncul di lebih dari satu pohon, masing-masing dengan urutan tampilan yang berbeda.
  Jika Anda membutuhkan lebih banyak kebebasan, Anda perlu menyimpan nilai urutan-urutan secara terpisah dari id, dan solusinya mendapatkan bahkan lebih kompleks. Namun di sebagian besar proyek, penggunaan pintasan dapat diterima, yang memberikan tugas ganda id kategori sebagai urutan tampilan hierarki.

Kembali komentar Anda:

Ya, Anda dapat menyimpan "urutan pengurutan saudara" sebagai kolom lain di tabel penutupan, lalu gunakan nilai itu alih-alih ancestor untuk membangun string remah roti. Tetapi jika Anda melakukannya, Anda berakhir dengan banyak redundansi data. Artinya, leluhur yang diberikan disimpan di beberapa baris, satu untuk setiap jalur yang turun darinya. Jadi, Anda harus menyimpan nilai yang sama untuk urutan pengurutan saudara pada semua baris tersebut, yang menimbulkan risiko anomali.

Alternatifnya adalah membuat tabel lain, dengan hanya satu baris per leluhur yang berbeda di pohon, dan gabungkan ke tabel itu untuk mendapatkan urutan saudara.

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         |
+----+------------+--------+---------+-------------+