Nested set model - cây phân cấp trong database
Bài đăng này đã không được cập nhật trong 3 năm
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à id
củ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á khileft
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ây
parent-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ácinsert
hayupdate
đề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ườngleft
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
All rights reserved