Nested set model và ứng dụng của nó trong quản lý folder phân cấp

Nested set model và ứng dụng của nó trong quản lý folder phân cấp

1. Giới thiệu

Trong nhiều tình huống, ví dụ như đối với web ecomerce ta thường có một hệ thống category phân cấp, như điện tử, thời trang, đời sống,... trong thời trang thì có áo, quần, trong category quần thì lại có 2 loại category con nữa là quần ngắn, quần dài,...

Cấu trúc như vậy gọi là cấu trúc cây phân cấp, vậy để xây dựng một cấu trúc cây phân cấp hiệu quả trong database ta phải làm thế nào?

Đáp án: có rất nhiều cách để xây dựng cấu trúc này trong database, trong đó có thể kể đến:

Parent child model:

Với cách cài đặt này, ta sẽ thêm một trường parent_id để lưu thông tin của node cha của node đó.

VD: ELECTRONICS có parent_id là NULL -> nó là node cha và không có cha, TELEVISIONS và PORTABLE ELECTRONICS đều có parent_id là 1, là id của ELECTRONICS nên 2 node trên là con của ELECTRONICS. Tương tự như thế đối với các node còn lại, biểu diễn hình cây ta sẽ có:

Một cách khác để xây dựng cây phân cấp là: Materialized Path

Cách cài đặt này tương tự như cách cài đặt của parent-child nhưng thay vì thêm cột parent_id trong model, ta sẽ thêm cột path để lưu đường dẫn từ node root tới node hiện tại:

Như vậy,path của mỗi node sẽ là idcủa các node bắt đầu từ root nối với nhau và kết thúc bằng id của node hiện tại:

Tuy nhiên, những cách trên lại có những nhược điểm như:

+ Đối với parent-child model: chậm khi truy xuất, đặc biệt khi dữ liệu có độ sâu nhiều hơn 2 level bởi vì ta không thể hoàn thành việc đó chỉ bởi 1 câu lệnh query. Nếu cây có độ sâu là 5 level thì muốn lấy node ở trên cùng, ta phải mất 4 lần query mới có được kết quả.

+ Đối với Materialized Path: Truy vấn toàn bộ cây hoặc một nhánh yêu cầu sử dụng các phép so sánh chuỗi (ví dụ: LIKE hoặc REGEXP) trên cột lưu trữ đường dẫn (path), với cây phân cấp lớn và sâu, việc duyệt qua từng node để kiểm tra chuỗi sẽ chậm và tốn tài nguyên.

Vì vậy, có một giải pháp giải quyết các nhược điểm trên đó là Nested set model:

Quay trở lại với category phân cấp ở đầu bài:

Category này ta có thể biểu diễn theo một mô hình lồng nhau như sau:

Việc biểu diễn thành mô hình lồng nhau (nested set) như trên cũng chính là ý tưởng của nested set model.

Tiếp đến, ta sẽ đánh số từ trái sang phải, theo nguyên tắc là tăng dần, gặp viền nào là sẽ đánh số ngay viền đó:

Lấy các con số tìm được ở trên áp vào mô hình cây ban đầu, ta được như sau:

Như hình trên là ta đã xây dựng xong một nested set model chuẩn.

Bây giờ giả sử :

+ Nếu muốn lấy các node lá (là node cấp thấp nhất), ta chỉ cần tìm các node có left (số ở viền trái) hơn right (số ở viền phải) một đơn vị.

+ Nếu muốn tìm độ sâu (cấp của node) nào đó, ta chỉ cần đếm số node cha ở trên nó bằng cách tìm và đếm số node có left < leff của node đang xét và right > right của node đang xét:

Ví dụ ở hình trên nếu muốn tìm độ sâu của node “Quần dài", ta tìm các node có left < 13 và right > 14, vậy là có “Quần" và “Thời trang". Vậy độ sâu của node này là 2 do tìm được 2 node cha ở trên nó.

+ Nếu muốn thêm một node mới: ta thực hiện tăng left và right của tất cả các node nằm bên phải vị trí thêm node mới lên 2 đơn vị. Sở dĩ tăng 2 đơn vị là vì 1 node (chưa có con) sẽ chiếm 2 đơn vị, vì vậy ý tưởng là ta sẽ dịch chuyển tất cả các node sang phải một đơn vị để chừa chỗ chèn node mới vào.

Giả sử muốn chèn thêm một node “Giày dép” vào giữa 2 node “Áo" và “Quần":

Ta thực hiện “di dời" các node bên phải vị trí muốn chèn đi 2 đơn vị (tức là cộng 2 vào left, right của các node di dời):

Cuối cùng, thực hiện chèn node “Giày dép":

+ Nếu muốn xóa một node: ta thực hiện xóa node đó (đồng thời xóa tất cả các con của node đó), sau đó cập nhật lại vị trị của tất cả các node bên phải node bị xóa.

Thuật toán cập nhật lại vị trí của các node bên phải node bị xóa là: (right-left +1) đơn vị ( right và left này là của node bị xóa). Giải thích dễ hiểu thì right - left + 1 này chính là độ rộng (width) của node bị xóa, vậy sau khi xóa node đó ta phải thực hiện “di dời" các node bên phải nó qua trái để lấp đi khoảng trống mà node bị xóa để lại.

Giả sử muốn xóa node “Dụng cụ nhà bếp":

Ta sẽ thực hiện xóa node “Dụng cụ nhà bếp" và tất cả các con của nó bao gồm “Chén đĩa" và “Nồi chảo":

Vậy ta cần phải di dời các node bên phải vị trí vừa bị xóa để lấp lại khoảng trống mà node bị xóa tạo ra, với width của node bị xóa là (right - left + 1) = 23 - 18 + 1 = 6, vậy ta sẽ di dời các node bên phải qua trái 6 đơn vị:

1. Ý tưởng triển khai

Nested set model là một mô hình rất phù hợp để triển khai cho việc quản lý folder phân cấp, ví dụ quản lý hệ thống tài liệu của một công ty nhu sau:

Ở đây có các dạng folder:

• Tài liệu chung: trong folder này thì tất cả mọi người đều có quyền truy cập, bên trong nó là 2 folder con “Tài liệu quy định" và “Tài liệu huớng dẫn"
• Kế toán: folder này chỉ có nhân viên kế toán mới được quyền truy cập.
• Lễ tân: folder này chỉ có nhân viên lễ tân mới được quyền truy cập.
• Cá nhân: folder này chứa các folder con, là các folder của từng nhân viên, ví folder của “Nguyễn Văn A" thì chỉ có Nguyễn V ăn A mới xem được.

Ta sẽ áp dụng Nested set model để đánh số cho các folder như sau:

Việc còn lại chỉ là xây dựng triển khai nó trong database thế nào, đầu tiên ta cần xây bảng folder_nested như sau:

create table folder_nested
(
id serial
primary key,
name varchar(255) not null,
"leftKey" integer not null,
"rightKey" integer not null,
"roleAccess" varchar(255),
path varchar(255) not null,
"ownerId" varchar(20)
);

Trong đó:

+ name: tên folder

+ leftKey: left của node

+ rightKey: right của node

+ roleAccess: role được quyền truy cập folder, nếu là folder chung giá trị sẽ là “PUBLIC", nếu là folder cá nhân giá trị sẽ là “PERSONAL", còn lại nếu thuộc sở hữu role nào giá trị sẽ là role đó, ví dụ “ACCOUNTANT" là dành cho kế toán.

+ path: đường dẫn tới thư mục

+ ownerId: userId của chủ sở hữu thư mục

Bảng folder_nested sau khi insert (với NV001 là userId của Nguyễn Văn A và NV002 là userId của Nguyễn Văn B):

id	name	leftKey	rightKey	roleAccess	ownerId
1	Tài liệu	1	19	PUBLIC
2	Tài liệu chung	3	8	PUBLIC
3	Tài liệu quy định	4	5	PUBLIC
4	Tài liệu hướng dẫn	6	7	PUBLIC
5	Kế toán	9	10	ACCOUNTANT
6	Lễ tân	11	12	RECEPTIONIST
7	Cá nhân	13	18	PUBLIC
8	Nguyễn Văn A	14	15	PERSONAL	NV001
9	Nguyễn Văn B	16	17	PERSONAL	NV002

3. Triển khai

Sử dụng NodeJS + TypeORM + PostgreSQL, thực hiện xây dựng hệ thống quản lý folder như trên:

+ Model Folder:

import { Entity, Column, PrimaryGeneratedColumn, BaseEntity } from "typeorm";

@Entity("folders")
export class Folder extends BaseEntity {
  @PrimaryGeneratedColumn()
  id!: number;

  @Column({ type: "varchar", length: 255 })
  name!: string;

  @Column({ type: "int" })
  leftKey!: number;

  @Column({ type: "int" })
  rightKey!: number;

  @Column({ type: "varchar", length: 255, nullable: true })
  roleAccess!: string | null;

  @Column({ type: "varchar", length: 20, nullable: true })
  ownerId!: string | null;

  @Column({ type: "varchar", length: 255 })
  path!: string;
}

+ Hàm kiểm tra quyền truy cập một folder nào đó:

  async checkAccess(userId: string, userRole: string, folderId: number): Promise<Folder> {
    const folder = await Folder.findOne({ where: { id: folderId } });
    if (!folder) {
      throw new Error('Folder not found');
    }

    // Kiểm tra quyền
    if (
      !folder.roleAccess ||
      folder.roleAccess === userRole ||
      folder.ownerId === userId ||
      folder.roleAccess === 'PUBLIC'
    ) {
      return folder;
    }

    throw new Error('Access denied');
  }

+ Hàm tạo một folder mới:

 async createFolder(
    userId: string,
    userRole: string,
    parentId: number,
    name: string,
    roleAccess: string
  ): Promise<Folder> {
    let parentFolder: Folder | null = null;

    if (parentId) {
      // Kiểm tra quyền truy cập vào thư mục cha
      parentFolder = await this.checkAccess(userId, userRole, parentId);

      // Cập nhật cây Nested Set
      await Folder.createQueryBuilder()
        .update(Folder)
        .set({ rightKey: () => '"rightKey" + 2' })
        .where('rightKey >= :rightKey', { rightKey: parentFolder.rightKey })
        .execute();

      await Folder.createQueryBuilder()
        .update(Folder)
        .set({ leftKey: () => '"leftKey" + 2' })
        .where('leftKey > :rightKey', { rightKey: parentFolder.rightKey })
        .execute();
    }

    // Xác định đường dẫn và giá trị Nested Set cho thư mục mới
    const folderPath = parentFolder ? `${parentFolder.path}/${name}` : name;
    const leftKey = parentFolder ? parentFolder.rightKey : 1;
    const rightKey = parentFolder ? parentFolder.rightKey + 1 : 2;

    // Tạo thư mục thực trên máy
    await fs.ensureDir(`${this.ROOT_FOLDER}/${folderPath}`);

    // Lưu thư mục mới vào database
    const newFolder = Folder.create({
      name,
      leftKey,
      rightKey,
      roleAccess: roleAccess,
      ownerId: userId,
      path: folderPath
    });
    await newFolder.save();

    return newFolder;
  }

+ Xóa folder:

 async deleteFolder(userId: string, userRole: string, folderId: number): Promise<void> {
    const folder = await this.checkAccess(userId, userRole, folderId);

    const width = folder.rightKey - folder.leftKey + 1;

    // Xóa thư mục thực
    await fs.remove(`${this.ROOT_FOLDER}/${folder.path}`);

    // Xóa thư mục trong database

    await Folder.delete({ leftKey: And(MoreThanOrEqual(folder.leftKey), LessThanOrEqual(folder.rightKey)) });

    // Cập nhật lại cây
    await Folder.createQueryBuilder()
      .update(Folder)
      .set({ leftKey: () => `"leftKey" - ${width}` })
      .where('leftKey > :rightKey', { rightKey: folder.rightKey })
      .execute();

    await Folder.createQueryBuilder()
      .update(Folder)
      .set({ rightKey: () => `"rightKey" - ${width}` })
      .where('rightKey > :rightKey', { rightKey: folder.rightKey })
      .execute();
  }

Ví dụ muốn lấy danh sách các folder mà user có id NV001 - Nguyễn Văn A , role là kế toán có thể truy cập, kết quả API trả về như sau:

GET /folder/accessible?userId=NV001&userRole=ACCOUNTANT

Response:

{
  "status": "OK",
  "code": 200,
  "success": true,
  "message": "Get accessible folders successfully",
  "data": [
    {
      "id": 1,
      "name": "Tài liệu",
      "leftKey": 1,
      "rightKey": 19,
      "roleAccess": "PUBLIC",
      "ownerId": null,
      "path": "_",
      "children": [
        {
          "id": 2,
          "name": "Tài liệu chung",
          "leftKey": 3,
          "rightKey": 8,
          "roleAccess": "PUBLIC",
          "ownerId": null,
          "path": "_",
          "children": [
            {
              "id": 3,
              "name": "Tài liệu quy định",
              "leftKey": 4,
              "rightKey": 5,
              "roleAccess": "PUBLIC",
              "ownerId": null,
              "path": "_",
              "children": []
            },
            {
              "id": 4,
              "name": "Tài liệu hướng dẫn",
              "leftKey": 6,
              "rightKey": 7,
              "roleAccess": "PUBLIC",
              "ownerId": null,
              "path": "_",
              "children": []
            }
          ]
        },
        {
          "id": 5,
          "name": "Kế toán",
          "leftKey": 9,
          "rightKey": 10,
          "roleAccess": "ACCOUNTANT",
          "ownerId": null,
          "path": "_",
          "children": []
        },
        {
          "id": 7,
          "name": "Cá nhân",
          "leftKey": 13,
          "rightKey": 18,
          "roleAccess": "PUBLIC",
          "ownerId": null,
          "path": "_",
          "children": [
            {
              "id": 8,
              "name": "Nguyễn Văn A",
              "leftKey": 14,
              "rightKey": 15,
              "roleAccess": "PERSONAL",
              "ownerId": "NV001",
              "path": "_",
              "children": []
            }
          ]
        }
      ]
    }
  ],
  "errors": null
}

Đối với một user mới, với ID là NV005, role là kỹ thuật viên - TECHINICIAN, kết quả trả về:

{
    "status": "OK",
    "code": 200,
    "success": true,
    "message": "Get accessible folders successfully",
    "data": [
        {
            "id": 1,
            "name": "Tài liệu",
            "leftKey": 1,
            "rightKey": 19,
            "roleAccess": "PUBLIC",
            "ownerId": null,
            "path": "_",
            "children": [
                {
                    "id": 2,
                    "name": "Tài liệu chung",
                    "leftKey": 3,
                    "rightKey": 8,
                    "roleAccess": "PUBLIC",
                    "ownerId": null,
                    "path": "_",
                    "children": [
                        {
                            "id": 3,
                            "name": "Tài liệu quy định",
                            "leftKey": 4,
                            "rightKey": 5,
                            "roleAccess": "PUBLIC",
                            "ownerId": null,
                            "path": "_",
                            "children": []
                        },
                        {
                            "id": 4,
                            "name": "Tài liệu hướng dẫn",
                            "leftKey": 6,
                            "rightKey": 7,
                            "roleAccess": "PUBLIC",
                            "ownerId": null,
                            "path": "_",
                            "children": []
                        }
                    ]
                },
                {
                    "id": 7,
                    "name": "Cá nhân",
                    "leftKey": 13,
                    "rightKey": 18,
                    "roleAccess": "PUBLIC",
                    "ownerId": null,
                    "path": "_",
                    "children": []
                }
            ]
        }
    ],
    "errors": null
}

4. So sánh với các mô hình khác

Với Nested model, để lấy ra danh sách các node và độ sâu tương ứng của chúng, query sẽ là:

EXPLAIN ANALYZE SELECT
child.id,
child.name,
COUNT(parent.id) - 1 AS depth
FROM
folders AS child
LEFT JOIN
folders AS parent
ON
child."leftKey" BETWEEN parent."leftKey" AND parent."rightKey"
GROUP BY
child.id, child.name, child."leftKey"
ORDER BY
child."leftKey";

Kết quả performence:

Với parent-child model:

Tạo bảng:

CREATE TABLE folder_parent_child (

id SERIAL PRIMARY KEY,

name VARCHAR(255) NOT NULL,

parent_id INT NULL,

roleAccess VARCHAR(255),

ownerId VARCHAR(20),

FOREIGN KEY (parent_id) REFERENCES folder_parent_child(id) ON DELETE CASCADE

);

Insert dữ liệu:

INSERT INTO folder_parent_child (id, name, parent_id, roleAccess, ownerId) VALUES

(1, 'Tài liệu', NULL, 'PUBLIC', NULL),

(2, 'Tài liệu chung', 1, 'PUBLIC', NULL),

(3, 'Tài liệu quy định', 2, 'PUBLIC', NULL),

(4, 'Tài liệu hướng dẫn', 2, 'PUBLIC', NULL),

(5, 'Kế toán', 1, 'ACCOUNTANT', NULL),

(6, 'Lễ tân', 1, 'RECEPTIONIST', NULL),

(7, 'Cá nhân', 1, 'PUBLIC', NULL),

(8, 'Nguyễn Văn A', 7, 'PERSONAL', 'NV001'),

(9, 'Nguyễn Văn B', 7, 'PERSONAL', 'NV002');

Query lấy danh sách node và độ sâu:

WITH RECURSIVE folder_tree AS (

SELECT

id,

name,

parent_id,

0 AS depth

FROM

folder_parent_child

WHERE

parent_id IS NULL

UNION ALL

SELECT

child.id,

child.name,

child.parent_id,

parent.depth + 1

FROM

folder_parent_child AS child

INNER JOIN

folder_tree AS parent

ON

child.parent_id = parent.id

)

SELECT id, name, depth

FROM folder_tree

ORDER BY id;

Kết quả:

Đối với materialize path:

CREATE TABLE folder_materialized_path (

id SERIAL PRIMARY KEY,

name VARCHAR(255) NOT NULL,

path TEXT NOT NULL UNIQUE, -- Materialized path

roleAccess VARCHAR(255),

ownerId VARCHAR(20)

);

INSERT INTO folder_materialized_path (id, name, path, roleAccess, ownerId) VALUES

(1, 'Tài liệu', '/1', 'PUBLIC', NULL),

(2, 'Tài liệu chung', '/1/2', 'PUBLIC', NULL),

(3, 'Tài liệu quy định', '/1/2/3', 'PUBLIC', NULL),

(4, 'Tài liệu hướng dẫn', '/1/2/4', 'PUBLIC', NULL),

(5, 'Kế toán', '/1/5', 'ACCOUNTANT', NULL),

(6, 'Lễ tân', '/1/6', 'RECEPTIONIST', NULL),

(7, 'Cá nhân', '/1/7', 'PUBLIC', NULL),

(8, 'Nguyễn Văn A', '/1/7/8', 'PERSONAL', 'NV001'),

(9, 'Nguyễn Văn B', '/1/7/9', 'PERSONAL', 'NV002');

Query lấy danh sách node và độ sâu:

Độ sâu trong Materialized Path là số lượng dấu / trừ đi 1.

SELECT

id,

name,

LENGTH(path) - LENGTH(REPLACE(path, '/', '')) - 1 AS depth

FROM

folder_materialized_path

ORDER BY

path;

Kết quả: