+24

Nested set model - cây phân cấp trong database

I. Giới thiệu về cây phân cấp trong database

Chắc hẳn mô hình cây không phải là xa lạ gì với các lập trình viên và ứng dụng của nó thì bạn có thể nhìn thấy rất nhiều như phân cấp thư mục, menu, phân cấp categories...

Mỗi cây sẽ có các node cha và các node con, mỗi node cha có thể không có hoặc có 1 hay nhiều con, mỗi con chỉ có 1 cha, mô hình cây như bên dưới:

2383101962_2883641c13.jpg

Mô hình cây thường được dùng khi muốn chèn một hệ thống phân cấp vào trong database, lưu trữ các mô hình quan hệ giữa các dữ liệu cùng loại và quan hệ giữa các node là quan hệ cha-con. Vậy làm thế nào để cài đặt mô hình này trong database chỉ trong 1 table?

II. Các phương pháp cài đặt

Một số phương pháp cài đặt cấu trúc dạng cây phổ biến:

1. Parent-child model

parent-child.png

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ó:

Untitled.png

2. 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,

path.png

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.

path2.png

3. Nested set model

  • Thế nào là nested set model?

    electrins.png

    Nested set là mô hình tập hợp nồng nhau, các node cha sẽ bao quanh các node con của nó.

    Như hình trên, ELECTRONICS là node lớn nhất nên nó bao trọn tất cả các node khác, các node sẽ phân cấp theo thứ tự từ ngoài vào trong.

  • Cách hoạt động:

    Với mỗi node sẽ được duyệt qua 2 lần và được đánh số theo thứ tự duyệt qua, từ trái sang phải, từ bên trái của node bên ngoài và tiếp tục sang bên phải.

    Dưới đây là thứ tự đánh số sau khi duyệt hết các node.

    newcatefor.png

    Để lưu cấu trúc trên, ta thêm 2 cột leftright để lưu thông tin mỗi node, dựa và đó, ta có thể query được vị trí của các node một cách dễ dàng.

    Ta sẽ biểu diễn dữ liệu dưới dạng bảng để dễ cho việc hình dung cách hoạt động của mô hình này, từ hình bên trên ta sẽ có:

    talbe.png

treelcetric.png

  • Một số thuật toán sử dụng:

    +) Tìm tất cả các node lá:

    Dựa vào 2 thông số leftright ta thấy các node là node lá khi leftright chỉ chênh lệch nhau 1 đơn vị.

    lá.png

    +) Tìm độ sâu của các node:

    Độ sâu của 1 node dựa vào số các node cha ở trên nó:

    pảent.png

    +) Thêm 1 node mới

    Thuật toán:

    ÍNERT.png

    Vì mỗi node lưu thông tin left right của nó nên nếu muốn thêm một node mới, ta phải tạo thêm không gian bộ nhớ cho nó với khoảng trống là 2 đơn vị.

    Để thêm khoảng trống cho node mới, trước tiên ta tăng các thông số leftright của các node bên phải node cần chèn vào 2 đơn vị, sau đó ta sẽ thêm node mới vào vị trí tương ứng.

    VD: Thêm node GAME CONSOLES vào giữa TELEVISIONS và PORTABLE ELECTRONICS

    Untitled (1).png

    B1: Tăng leftright của các node bên phải node TELEVISIONS lên 2 đơn vị:

    Untitled (2).png

    B2: Chèn node mới vào:

    Untitled (3).png

    +) Xóa một node

    Đối với thuật toán xóa 1 node, ta sẽ xóa node đó trước sau đó sẽ cập nhập lại các giá trị leftright của các node bên phải của node bị xóa.

    el2.png

    Nếu node bị xóa không phải là node lá thì khi xóa node đó, tất cả các node con của nó cũng sẽ bị xóa theo.

    VD: Xóa node MP3 PLAYERS có 1 node con

    deletenode.png

    B1: Xóa node đã chọn đồng thời xóa tất cả các node con của nó

    deletenode1.png

    B2: Cập nhập các giá trị leftright của các node bên phải node bị xóa, giảm xuống một khoảng (right-left +1) đơn vị ( rightleft này là của node bị xóa).

    deleteall.png

III. Áp dụng

  • Cấu trúc câyparent-child là mô hình dễ hiểu nhất, rất dễ để cài đặt nhưng nó là 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ả.

  • Cách cài đặt materialized pathnested set model đều là cách cài đặt phức tạp, các thao tác insert hay update đều tốn thời gian và phức tạp, nhưng lại rất thuận lợi cho việc truy xuất dữ liệu.

    Tuy nhiên, Nested set thì khó để giải thích và có logic phức tạp khi muốn thay đổi dữ liệu, nhưng nó lại giúp cho người dùng truy xuất dữ liệu một cách nhanh chóng hơn chỉ cần dựa vào các giá trị của 2 trường leftright của các node.

Tùy vào yêu cầu và độ phức tạp của bài toán mà lựa chọn cách cài đặt cho phù hợp, nếu bạn làm việc với các dữ liệu đơn giản, số tầng ít và không cần truy xuất nhanh thì bạn nên dùngparent-child. Còn nếu dữ liệu của bạn có nhiều tầng, độ sâu lớn và muốn nhanh chóng lấy ra dữ liệu thì bạn nên dùng materialized path hoặc nested set model.

Link tham khảo:

http://mikehillyer.com/articles/managing-hierarchical-data-in-mysql/

http://techtalk.vn/nested-set-model-goc-nhin-khac-cho-mo-hinh-category-da-cap.html


All rights reserved

Viblo
Hãy đăng ký một tài khoản Viblo để nhận được nhiều bài viết thú vị hơn.
Đăng kí