Đã có nhiều bài nói về vấn đề này, mình xin tổng kết lại chức năng nhiệm vụ của Nested Set Model để các bạn có cái nhìn trực quan và minh bạch hơn qua ví dụ cụ thể.
Demo | Mã nguồn
Tóm tắt nội dung
Phải rồi, nói đến mô hình này, chắc các bạn không lạ lẫm gì. Trên đây là hình mình chụp lại từ dự án mình áp dụng thực tế, lát nữa mình sẽ hướng dẫn bạn tạo 1 mô hình giống như vậy.
Trước đây chúng ta hay sử dụng cách làm đệ quy để tạo, nhưng cách làm này khá tốn kém tài nguyên. Và mô hình bên dưới chắc chắn sẽ hữu ích cho bạn.
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:
Nested set model cho menu, category đa cấp 
Nested set model cho menu, category đa cấp
1. Cách làm thông thường: Parent-child model
Với cách này ta sẽ có thêm 1 field là parent_id để lưu thông tin của node cha. Như vậy, ta có thể biết được một node có những node con nào (dưới 1 cấp) và ngược lại, một node sẽ thuộc một node cha (trên 1 cấp) nào đó.
Nhưng giả sử bây giờ, yêu cầu của bài toán phức tạp hơn. Bạn cần select các category là cha của 1 category bất kì. Hay đơn giản hơn là liệt kê các category con của 1 category cha bất kì nào đó. Để truy xuất chúng, thông thường bạn sẽ áp dụng kĩ thuật đệ quy để duyệt cây – một kĩ thuật đơn giản và dễ viết. Tuy nhiên, cái nào cũng có hạn chế của nó, bởi lẽ nếu dữ liệu của bạn càng lớn thì tốc độ duyệt cây sẽ càng chậm.
2. Cách làm thứ hai: 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.
Cách làm này đã được cải tiến dữ liệu đi một chút thì vấn đề trên được giải quyết dễ dàng. Ta chỉ cần thêm vào một trường là path để chứa đường dẫn phân cấp của một nút. Path là sự kết hợp của các id dẫn tới nút đó, cách nhau bằng dấu gạch, bạn có thể dùng cái dấu khác như / nhưng nó sẽ nhầm lẫn khi để trên URL. Ví dụ với bảng trên sau khi thêm path:
3. Thuật toán Nested Set Model
Nested sets model là một kỹ thuật dùng để thể hiện nested sets (các tập hợp lồng nhau) trong cơ sở dữ liệu. Thuật toán Nested Set Model sẽ chuyển cây thành một danh sách (list) các category và lưu xuống data storage. Nếu bạn muốn truy xuất các category con của 1 category nào đó, bạn chỉ cần biết được left và right của category cha và bạn dễ dàng truy suất nhanh chóng các category con đó mà không cần phải đệ quy.
Dữ liệu thực tế cho ví dụ trên sẽ là:
Lưu trữ dữ liệu với cấu trúc như trên trong database rất tiện lợi cho việc truy vấn, vì ta dễ dàng tìm được tập hợp các nút thuộc vùng bất kỳ. Ví dụ ta muốn lấy tất cả các nút thuộc về nút Men’s:
SELECT * FROM category WHERE left>2 AND right<9;hoặc lấy các category cha của nó
SELECT * FROM category WHERE left<2 AND right>9;với phương pháp này có thể tiết kiệm 1 lượng lớn truy vấn với các ứng dụng như breadcrum, danh sách category con.
a. Thêm category mới
Giả sử cần category cà vạt thuộc category Suits ta sẽ phải cập nhật lại dữ liệu như hình bên dưới. Tổng quát, ta cần làm 2 thao tác:
1. Tạo ra vùng trống mới trong category Suit tăng từ [3, 8] => [3, 10]
2. Thêm category cà vạt [8, 9] vào category Suit. Giá trị của category cà vạt sẽ có left = right category cha( Suit) và right = right category cha + 1. Sau đó ta tăng giá trị left, right phía sau lên 2 đơn vị (chính là vùng trống dành cho category mới) bằng điều kiện:
UPDATE categories SET Left = Left + 2 WHERE Left >= 9
UPDATE categories SET Right = Right + 2 WHERE Right >= 9
b. Xóa category
Ở đây mình sẽ trình bày trong trường hợp là khi xóa category, các category bên trong nó cũng sẽ bị xóa theo. Ở đây mình sẽ thực hiện xóa category Suit (và các category con của nó).
Tổng quát ta sẽ làm hai thao tác:
1. Xóa category và những category con của nó. 2. Cập nhật lại left, right cho các category bằng điều kiện:
UPDATE categories SET Left = Left – 6 WHERE Left > 8
UPDATE categories SET Right = Right – 6 WHERE Right > 8
6 được tính bằng số category con + cha bị xóa có thể tính bằng công thức = right – left + 1
c. Move Category
Trong Ví dụ này mình sẽ thực hiện move category dress[15,20] thành con của category Suit[3,8]
Tổng quát ta sẽ làm hai thao tác:
1. update left, right cho các category bị move
2. Cập nhật lại left, right cho các category nằm trên suit
UPDATE categories SET Left = Left – 7 WHERE Left >=15 AND Right <= 20
UPDATE categories SET Right = Right – 7 WHERE Left >=15 AND Right <= 20
UPDATE categories SET Right = Right + 6 WHERE Left <=3 AND Right >= 8
UPDATE categories SET Right = Right + 6 WHERE Right >15 AND Right <20
UPDATE categories SET Left = Left + 6 WHERE Left >15 AND Left <20
Ví dụ:
Dù dữ liệu được lưu ở dạng nào thì nếu ta xây dựng một cấu trúc dạng html list ul li, thì ta có thể dễ dàng có thể áp dụng một plugin javascript như superfish để tạo ra menu.
$category = array(
array('id'=>1,'name'=>'Clothing','left'=>1, 'right'=>22),
array('id'=>2,'name'=>'Men\'s','left'=>2, 'right'=>9),
array('id'=>3,'name'=>'Women\'s','left'=>10, 'right'=>21),
array('id'=>4,'name'=>'Suits','left'=>3, 'right'=>8),
array('id'=>5,'name'=>'Slacks','left'=>4, 'right'=>5),
array('id'=>6,'name'=>'Jackets','left'=>6, 'right'=>7),
array('id'=>7,'name'=>'Dresses','left'=>11, 'right'=>16),
array('id'=>8,'name'=>'Skirts','left'=>17, 'right'=>18),
array('id'=>9,'name'=>'Blouses','left'=>19, 'right'=>20),
array('id'=>10,'name'=>'Evening Gorws','left'=>12, 'right'=>13),
array('id'=>11,'name'=>'Sun Dresses','left'=>14, 'right'=>15),
);
function createTree($category, $left = 0, $right = null) {
$tree = array();
foreach ($category as $cat => $range) {
if ($range['left'] == $left + 1 && (is_null($right) || $range['right'] < $right)) {
$tree[$cat] = createTree($category, $range['left'], $range['right']);
$left = $range['right'];
}
}
return $tree;
}
$tree = createTree($category);
function createList($keys, $category)
{
$list = "<ul>";
foreach($keys as $key => $row)
{
if(count($row)){
$list.='<li>'. $category[$key]['name'].createList($row, $category) . '</li>';
} else {
$list.='<li>'. $category[$key]['name'] . '</li>';
}
}
$list .= "</ul>";
if ( strpos($list, '<li>')===false){
$list = '';
}
return $list;
}
$list = createList($tree, $category);
print $list;Kết quả
<ul>
<li>Clothing
<ul>
<li>Men's
<ul>
<li>Suits
<ul>
<li>Slacks</li>
<li>Jackets</li>
</ul>
</li>
</ul>
</li>
<li>Women's
<ul>
<li>Dresses
<ul>
<li>Evening Gorws</li>
<li>Sun Dresses</li>
</ul>
</li>
<li>Skirts</li>
<li>Blouses</li>
</ul>
</li>
</ul>
</li>
</ul>MR386, chúc các bạn thành công!
