ソフトウェア開発では、樹状構造を必要とする場面がよくあります。例えば、ナビゲーションメニュー、組織構造図、商品カテゴリ階層などがあります。これらはすべて、親子のような階層構造を持っています。
そんな樹状構造を表すデータベース設計はどのようにしたらよいのでしょうか？今回はその設計と検索方法について探ります。
まず最初に、非リレーショナルデータベースでの保存は可能ですか？
肯定的に「可能」です。例えばMongoDBでは、一本の木全体をJSON形式で保存できます。しかし、条件検索がしにくいという欠点があります。もちろん、具体的な要件に依存しますが、要件を無視した設計はナンセンスです。
メニューのシーンでは一般的にリレーショナルデータベースを使用します。最終的な検索結果をキャッシングするのが一般的です。
一般的な方法は4種類あります。
- 各レコードにparent_idを保存する方法
- 各レコードにツリー経路を保存する方法
- 各レコードにnleftとnrightを保存する方法
- ツリー構造を表す専用の表を作成する方法
第一の方法：各レコードにparent_idを保存する方法
この方法はシンプルで直感的ですが、特定の節点の親や子の検索時にリカursive処理が必要になります。MySQLではストアドプロシージャーを使用する必要がありますが、これには手間がかかります。
ただし、2階層までのメニューであれば単純にセルフジョインで済みます。
第四の方法：専用の表で節点間の関係を保存する方法
CREATE TABLE `city` (
`id` int(11) NOT NULL AUTO_INCREMENT,
`name` varchar(16),
PRIMARY KEY (`id`) USING BTREE
) ENGINE = InnoDB AUTO_INCREMENT = 1 CHARACTER SET = utf8mb4;
CREATE TABLE `city_tree_path_info` (
`id` int(11) NOT NULL AUTO_INCREMENT,
`city_id` int(11) NOT NULL,
`ancestor_id` int(11) NOT NULL COMMENT '祖先ID',
`level` tinyint(4) NOT NULL COMMENT 'レベル',
PRIMARY KEY (`id`) USING BTREE
) ENGINE = InnoDB AUTO_INCREMENT = 1 CHARACTER SET = utf8mb4;
この例では、city表が都市を表し、city_tree_path_info表が都市間の階層関係を表します。ancestor_idは親や祖父などのIDを示し、levelは現在のレコードがancestor_idに対してのレベルを示します。このようにして全体の階層関係を保存することができます。
そして、このような階層構造を構築するのに最適なのはJavaコードです。
Javaでのメニュー樹の生成
Menu.java
1 package com.example.demo.model;
2
3 import lombok.AllArgsConstructor;
4 import lombok.Data;
5 import lombok.NoArgsConstructor;
6
7 import java.util.List;
8
9 @AllArgsConstructor
10 @NoArgsConstructor
11 @Data
12 public class Menu {
13
14 /**
15 * メニューID
16 */
17 private Integer id;
18
19 /**
20 * 親メニューID
21 */
22 private Integer pid;
23
24 /**
25 * メニュー名
26 */
27 private String name;
28
29 /**
30 * メニュー識別子
31 */
32 private String code;
33
34 /**
35 * メニューリンク
36 */
37 private String url;
38
39 /**
40 * メニューアイコン
41 */
42 private String icon;
43
44 /**
45 * 順番
46 */
47 private int sort;
48
49 /**
50 * 子メニュー
51 */
52 private List<Menu> children;
53
54 public Menu(Integer id, Integer pid, String name, String code, String url, String icon, int sort) {
55 this.id = id;
56 this.pid = pid;
57 this.name = name;
58 this.code = code;
59 this.url = url;
60 this.icon = icon;
61 this.sort = sort;
62 }
63
64 }
Test.java
1 package com.example.demo.model;
2
3 import com.fasterxml.jackson.core.JsonProcessingException;
4 import com.fasterxml.jackson.databind.ObjectMapper;
5
6 import java.util.ArrayList;
7 import java.util.Comparator;
8 import java.util.List;
9 import java.util.stream.Collectors;
10
11 public class Hello {
12 public static void main(String[] args) throws JsonProcessingException {
13 List<Menu> allMenuList = new ArrayList<>();
14 allMenuList.add(new Menu(1, 0, "湖北", "HuBei", "/a", "a", 3));
15 allMenuList.add(new Menu(2, 0, "河南", "HeNan", "/b", "b", 2));
16 allMenuList.add(new Menu(3, 1, "宜昌", "YiChang", "/c", "c", 2));
17 allMenuList.add(new Menu(4, 2, "信阳", "XinYang", "/d", "d", 1));
18 allMenuList.add(new Menu(5, 1, "随州", "SuiZhou", "/e", "e", 1));
19 allMenuList.add(new Menu(6, 5, "随县", "SuiXian", "/f", "f", 2));
20 allMenuList.add(new Menu(7, 3, "枝江", "ZhiJiang", "/g", "g", 2));
21
22 // 1級メニュー
23 List<Menu> parentList = allMenuList.stream().filter(e->e.getPid()==0).sorted(Comparator.comparing(Menu::getSort)).collect(Collectors.toList());
24 // 递归呼び出しで、全ての1級メニューに子メニューを設定
25 for (Menu menu : parentList) {
26 menu.setChildren(getChild(menu.getId(), allMenuList));
27 }
28
29 ObjectMapper objectMapper = new ObjectMapper();
30 System.out.println(objectMapper.writeValueAsString(parentList));
31 }
32
33 /**
34 * 递归検索で子メニューを取得
35 * @param id 現在のメニューID
36 * @param allList 検索対象メニュー一覧
37 * @return
38 */
39 public static List<Menu> getChild(Integer id, List<Menu> allList) {
40 // 子メニュー
41 List<Menu> childList = new ArrayList<>();
42 for (Menu menu : allList) {
43 if (menu.getPid().equals(id)) {
44 childList.add(menu);
45 }
46 }
47
48 // 子メニューに子メニューを設定
49 for (Menu nav : childList) {
50 nav.setChildren(getChild(nav.getId(), allList));
51 }
52
53 // 順番を整える
54 childList = childList.stream().sorted(Comparator.comparing(Menu::getSort)).collect(Collectors.toList());
55
56 if (childList.size() == 0) {
57 // return null;
58 return new ArrayList<>();
59 }
60 return childList;
61 }
62 }
結果：
1 [
2 {
3 "id":2,
4 "pid":0,
5 "name":"河南",
6 "code":"HeNan",
7 "url":"/b",
8 "icon":"b",
9 "sort":2,
10 "children":[
11 {
12 "id":4,
13 "pid":2,
14 "name":"信阳",
15 "code":"XinYang",
16 "url":"/d",
17 "icon":"d",
18 "sort":1,
19 "children":[]
20 }
21 ]
22 },
23 {
24 "id":1,
25 "pid":0,
26 "name":"湖北",
27 "code":"HuBei",
28 "url":"/a",
29 "icon":"a",
30 "sort":3,
31 "children":[
32 {
33 "id":5,
34 "pid":1,
35 "name":"随州",
36 "code":"SuiZhou",
37 "url":"/e",
38 "icon":"e",
39 "sort":1,
40 "children":[
41 {
42 "id":6,
43 "pid":5,
44 "name":"随县",
45 "code":"SuiXian",
46 "url":"/f",
47 "icon":"f",
48 "sort":2,
49 "children":[]
50 }
51 ]
52 },
53 {
54 "id":3,
55 "pid":1,
56 "name":"宜昌",
57 "code":"YiChang",
58 "url":"/c",
59 "icon":"c",
60 "sort":2,
61 "children":[
62 {
63 "id":7,
64 "pid":3,
65 "name":"枝江",
66 "code":"ZhiJiang",
67 "url":"/g",
68 "icon":"g",
69 "sort":2,
70 "children":[]
71 }
72 ]
73 }
74 ]
75 }
76 ]
参考文献：
https://www.cnblogs.com/w2206/p/10490208.html
https://www.cnblogs.com/mokingone/p/9109021.html