Khám phá Thuật toán Nested Set Model trong Quản lý Cây dữ liệu

Trong lĩnh vực quản lý dữ liệu, việc tổ chức và truy xuất thông tin theo cấu trúc cây đòi hỏi những giải pháp hiệu quả. Một trong những thuật toán nổi bật được sử dụng để giải quyết vấn đề này là Nested Set Model. Thuật toán này không chỉ giúp cải thiện hiệu suất truy vấn mà còn đơn giản hóa quá trình quản lý cây dữ liệu.

  Kiến thức   Dec 23, 2023  Add to Reading List
Khám phá Thuật toán Nested Set Model trong Quản lý Cây dữ liệu

Thuật toán Nested Set Model thường được sử dụng trong các hệ thống quản lý dữ liệu có cấu trúc cây, nơi mà việc tổ chức và truy vấn dữ liệu theo hình thức cây là quan trọng. Dưới đây là mô tả một vài ứng dụng phổ biến của thuật toán này:

  1. Quản lý Danh Mục Sản Phẩm trong Cửa Hàng Online:

    • Nested Set Model thường được áp dụng để quản lý các danh mục sản phẩm trong các cửa hàng trực tuyến. Việc này giúp nhanh chóng truy xuất và hiển thị các danh mục con của một danh mục cụ thể, cũng như xác định vị trí của mỗi danh mục trong cây.

  2. Quản lý Đặc Quyền (Permission Management):

    • Trong hệ thống quản lý đặc quyền, Nested Set Model được sử dụng để biểu diễn cấu trúc phân quyền. Điều này giúp dễ dàng xác định tất cả các quyền con của một quyền cụ thể và quản lý việc gán quyền.

  3. Dự Án Quản lý Công Việc và Dự Án:

    • Nested Set Model có thể được sử dụng để tổ chức và theo dõi các công việc trong một dự án. Điều này giúp xác định mức độ ưu tiên, quản lý các công việc con của một công việc, và hiển thị cấu trúc cây của dự án.

  4. Diễn Đàn và Hệ Thống Bình Luận:

    • Trong các diễn đàn trực tuyến hoặc hệ thống bình luận, Nested Set Model có thể được sử dụng để tổ chức cấu trúc cây của các bài viết hoặc bình luận. Điều này giúp dễ dàng truy xuất các bình luận con của một bình luận cụ thể.

  5. Quản lý Cây Phân Loại và Dữ Liệu Phân Cấp:

    • Trong các ứng dụng quản lý cây phân loại hoặc dữ liệu phân cấp như cây genealogical, Nested Set Model cung cấp một cách hiệu quả để tổ chức và truy vấn cấu trúc dữ liệu.

  6. Hệ Thống E-commerce và Quản Lý Thể Loại Sản Phẩm:

    • Nested Set Model thường được sử dụng để quản lý cấu trúc thể loại sản phẩm trong hệ thống E-commerce. Điều này giúp dễ dàng thêm, xóa, và truy vấn các loại sản phẩm và loại sản phẩm con.

Tùy thuộc vào yêu cầu cụ thể của ứng dụng, Nested Set Model mang lại hiệu suất và khả năng linh hoạt trong việc quản lý cấu trúc cây dữ liệu.



Cơ bản về Nested Set Model
Nested Set Model là một phương pháp biểu diễn cây dữ liệu trong cơ sở dữ liệu quan hệ. Thay vì sử dụng các phương pháp như Adjacency List hay Path Enumeration, Nested Set Model biểu diễn mỗi nút trong cây dữ liệu bằng cách sử dụng hai số thực (left và right) để xác định vị trí của nút trong cây.

  • left: Số thực đại diện cho thứ tự bắt đầu của nút trong cây.
  • right: Số thực đại diện cho thứ tự kết thúc của nút trong cây.

Sự phổ biến của Nested Set Model đến từ khả năng truy xuất dữ liệu với hiệu suất cao. Với cấu trúc này, việc xác định tất cả các con của một nút hay tìm kiếm mức độ sâu của một nút trở nên đơn giản và nhanh chóng.

Ưu điểm của Nested Set Model

  1. Hiệu suất truy vấn cao: Do cấu trúc cây được biểu diễn dưới dạng khoảng liên tục bằng các số thực left và right, việc truy xuất dữ liệu trở nên rất nhanh chóng và dễ dàng.

  2. Dễ dàng duyệt cây: Nested Set Model làm cho việc duyệt cây trở nên đơn giản vì không cần phải thực hiện nhiều truy vấn phức tạp như các phương pháp khác.

  3. Thêm, sửa, xóa hiệu quả: Việc thêm, sửa, hay xóa một nút trong cây dữ liệu dễ dàng hơn và không ảnh hưởng nhiều đến cấu trúc tổng thể.

Ứng dụng của Nested Set Model

  1. Hệ thống quản lý danh mục sản phẩm: Nested Set Model thường được sử dụng để xây dựng các hệ thống quản lý danh mục sản phẩm nhanh chóng và hiệu quả.

  2. Quản lý đặc quyền (Permission Management): Việc tổ chức cấu trúc quyền dựa trên cây dữ liệu có thể được thực hiện một cách linh hoạt và dễ dàng.

Cách tạo bảng sử dụng Nested Set Model trong MySQL.

Trong ví dụ này, chúng ta sẽ tạo một bảng để lưu trữ thông tin về các loại sản phẩm trong một cửa hàng sử dụng Nested Set Model. 

-- Tạo bảng ProductCategories
CREATE TABLE ProductCategories (
    category_id INT AUTO_INCREMENT PRIMARY KEY,
    category_name VARCHAR(255) NOT NULL,
    lft INT NOT NULL,
    rgt INT NOT NULL
);

-- Thêm constraint UNIQUE để đảm bảo tính duy nhất của các giá trị left và right
ALTER TABLE ProductCategories ADD CONSTRAINT unique_lft_rgt UNIQUE (lft, rgt);

Trong mô hình Nested Set, cột lft và rgt sẽ chứa các giá trị số nguyên để biểu diễn vị trí của nút trong cây dữ liệu. Mỗi nút sẽ có một khoảng (range) giữa lft và rgt, và các nút con sẽ có khoảng nằm hoàn toàn trong khoảng của nút cha.

Sau đây là cách thêm dữ liệu vào bảng để biểu diễn một cây đơn giản: 

-- Thêm dữ liệu vào bảng
INSERT INTO ProductCategories (category_name, lft, rgt) VALUES ('Electronics', 1, 12);
INSERT INTO ProductCategories (category_name, lft, rgt) VALUES ('Computers', 2, 5);
INSERT INTO ProductCategories (category_name, lft, rgt) VALUES ('Laptops', 3, 4);
INSERT INTO ProductCategories (category_name, lft, rgt) VALUES ('Desktops', 6, 7);
INSERT INTO ProductCategories (category_name, lft, rgt) VALUES ('Appliances', 8, 11);
INSERT INTO ProductCategories (category_name, lft, rgt) VALUES ('Refrigerators', 9, 10);

Trong ví dụ này, chúng ta đã tạo một cây có cấu trúc như sau: 

- Electronics (1-12)
  - Computers (2-5)
    - Laptops (3-4)
  - Desktops (6-7)
  - Appliances (8-11)
    - Refrigerators (9-10)

Các truy vấn để truy xuất cây dữ liệu và các thao tác thêm/sửa/xóa nút trong Nested Set Model có thể được xây dựng sử dụng các phép toán BETWEEN và ORDER BY để truy xuất dữ liệu một cách hiệu quả.

Tạo mới dữ liệu theo thuật toán bằng PHP
Khi bạn muốn tạo mới một dòng trong Nested Set Model, bạn cần thực hiện các bước để chèn dữ liệu mới và duy trì cấu trúc cây. Dưới đây là một ví dụ về cách thêm dữ liệu mới trong Nested Set Model trong MySQL sử dụng PHP PDO:
 

<?php
// Thông tin kết nối đến cơ sở dữ liệu
$servername = "tên_server";
$username = "tên_người_dùng";
$password = "mật_khẩu";
$dbname = "tên_cơ_sở_dữ_liệu";

try {
    // Kết nối đến cơ sở dữ liệu
    $conn = new PDO("mysql:host=$servername;dbname=$dbname", $username, $password);

    // Thiết lập chế độ báo lỗi
    $conn->setAttribute(PDO::ATTR_ERRMODE, PDO::ERRMODE_EXCEPTION);

    // Dữ liệu mới cần thêm
    $newData = array('category_name' => 'New Category', 'lft' => 13, 'rgt' => 14);

    // Thêm dữ liệu mới
    $stmt = $conn->prepare("INSERT INTO ProductCategories (category_name, lft, rgt) VALUES (:category_name, :lft, :rgt)");
    $stmt->execute($newData);

    echo "Dữ liệu đã được thêm thành công!";
} catch (PDOException $e) {
    echo "Lỗi: " . $e->getMessage();
}

// Đóng kết nối
$conn = null;
?>


Cập nhật lại dữ liệu trong thuật toán Nested set Model
Khi bạn muốn cập nhật một dòng dữ liệu trong Nested Set Model, điều quan trọng là bạn phải xác định được các giá trị lft và rgt mới cho nút cần cập nhật, sao cho cấu trúc cây không bị thay đổi.
Dưới đây là một ví dụ về cách cập nhật dữ liệu trong Nested Set Model trong MySQL sử dụng PHP PDO: 

<?php
// Thông tin kết nối đến cơ sở dữ liệu
$servername = "tên_server";
$username = "tên_người_dùng";
$password = "mật_khẩu";
$dbname = "tên_cơ_sở_dữ_liệu";

try {
    // Kết nối đến cơ sở dữ liệu
    $conn = new PDO("mysql:host=$servername;dbname=$dbname", $username, $password);

    // Thiết lập chế độ báo lỗi
    $conn->setAttribute(PDO::ATTR_ERRMODE, PDO::ERRMODE_EXCEPTION);

    // Dữ liệu mới cần cập nhật
    $newData = array('category_name' => 'New Category', 'lft' => 13, 'rgt' => 14);

    // ID của nút cần cập nhật
    $categoryId = 1; // Thay thế bằng ID thực tế của nút cần cập nhật

    // Lấy giá trị `lft` và `rgt` hiện tại của nút
    $currentData = $conn->query("SELECT lft, rgt FROM ProductCategories WHERE category_id = $categoryId")->fetch(PDO::FETCH_ASSOC);

    // Tính toán sự chênh lệch giữa giá trị mới và giá trị hiện tại
    $delta = $newData['lft'] - $currentData['lft'];

    // Cập nhật các giá trị lft và rgt của các nút còn lại trong cây
    $conn->exec("UPDATE ProductCategories SET lft = lft + $delta, rgt = rgt + $delta WHERE lft >= {$currentData['lft']} AND rgt <= {$currentData['rgt']}");

    // Cập nhật dữ liệu cho nút cần cập nhật
    $stmt = $conn->prepare("UPDATE ProductCategories SET category_name = :category_name, lft = :lft, rgt = :rgt WHERE category_id = :category_id");
    $stmt->execute(array_merge($newData, array('category_id' => $categoryId)));

    echo "Dữ liệu đã được cập nhật thành công!";
} catch (PDOException $e) {
    echo "Lỗi: " . $e->getMessage();
}

// Đóng kết nối
$conn = null;
?>

Lưu ý rằng việc cập nhật dữ liệu trong Nested Set Model liên quan đến việc điều chỉnh giá trị lft và rgt của các nút trong cây để duy trì cấu trúc Nested Set.

Xoá dữ liệu trong thuật toán Nested set Model
Khi bạn muốn xóa một dòng trong Nested Set Model, bạn cần thực hiện các bước để duy trì cấu trúc cây và tránh làm hỏng dữ liệu. Dưới đây là một ví dụ về cách xóa dữ liệu trong Nested Set Model trong MySQL sử dụng PHP PDO:
 

<?php
// Thông tin kết nối đến cơ sở dữ liệu
$servername = "tên_server";
$username = "tên_người_dùng";
$password = "mật_khẩu";
$dbname = "tên_cơ_sở_dữ_liệu";

try {
    // Kết nối đến cơ sở dữ liệu
    $conn = new PDO("mysql:host=$servername;dbname=$dbname", $username, $password);

    // Thiết lập chế độ báo lỗi
    $conn->setAttribute(PDO::ATTR_ERRMODE, PDO::ERRMODE_EXCEPTION);

    // ID của nút cần xóa
    $categoryId = 1; // Thay thế bằng ID thực tế của nút cần xóa

    // Lấy giá trị `lft` và `rgt` của nút cần xóa
    $nodeToDelete = $conn->query("SELECT lft, rgt FROM ProductCategories WHERE category_id = $categoryId")->fetch(PDO::FETCH_ASSOC);

    // Tính toán chiều rộng của nút cần xóa
    $width = $nodeToDelete['rgt'] - $nodeToDelete['lft'] + 1;

    // Xóa nút và các nút con của nó
    $conn->exec("DELETE FROM ProductCategories WHERE lft >= {$nodeToDelete['lft']} AND rgt <= {$nodeToDelete['rgt']}");

    // Cập nhật giá trị `lft` và `rgt` của các nút còn lại
    $conn->exec("UPDATE ProductCategories SET lft = lft - $width WHERE lft > {$nodeToDelete['rgt']}");
    $conn->exec("UPDATE ProductCategories SET rgt = rgt - $width WHERE rgt > {$nodeToDelete['rgt']}");

    echo "Dữ liệu đã được xóa thành công!";
} catch (PDOException $e) {
    echo "Lỗi: " . $e->getMessage();
}

// Đóng kết nối
$conn = null;
?>

Trong ví dụ này, chúng ta sử dụng chiều rộng (width) của nút cần xóa để điều chỉnh giá trị lft và rgt của các nút còn lại trong cây. Điều này giúp duy trì cấu trúc Nested Set và tránh tình trạng hỏng dữ liệu. Hãy nhớ thay thế giá trị $categoryId bằng ID thực tế của nút bạn muốn xóa.

Kết luận

Nested Set Model không chỉ là một phương pháp biểu diễn cây dữ liệu mạnh mẽ trong cơ sở dữ liệu quan hệ mà còn mang lại những lợi ích về hiệu suất và quản lý dữ liệu. Sự đơn giản và khả năng truy xuất dữ liệu nhanh chóng đã làm cho thuật toán này trở thành một lựa chọn phổ biến trong nhiều ứng dụng khác nhau.