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:

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

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

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,

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.

3. Nested set model

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

  

  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.

  

  Để lưu cấu trúc trên, ta thêm 2 cột left và right để 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ó:

  

• 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ố left và right ta thấy các node là node lá khi left và right chỉ chênh lệch nhau 1 đơn vị.

  

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

  

  +) Thêm 1 node mới

  Thuật toán:

  

  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ố left và right 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

  

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

  

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

  

  +) 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ị left và right của các node bên phải của node bị xóa.

  

  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

  

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

  

  B2: Cập nhập các giá trị left và right 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ị ( right và left này là của node bị xóa).

  

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 path vànested 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 left và right 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