search

PhuongNamCorpsIntern / workspace

Phuong Nam Corps Internship Workspace
3 stars 8 forks source link

Nested Set Model #4

Open khanhicetea opened 9 years ago

khanhicetea commented 9 years ago

Nested Set Model

Giới thiệu

nested_set_model_1

Bạn đang thiết kế 1 website hay 1 software có các chuyên mục đa cấp (có chuyên mục cha, con, cháu, chắt, chút, chít, v.v..). Làm sao để thiết kế CSDL để đạt sự tối ưu trong lưu trữ, truy vấn, chỉnh sửa đây ? Bài viết sẽ đưa ra 1 giải pháp hoàn toàn mới, và bạn sẽ thấy được tầm quan trọng của Cấu Trúc Dữ Liệu.

Các giải pháp truyền thống

Giải pháp mới này sử dụng cấu trúc cây dữ liệu như sau :

nested_set_model_2

Cây dữ liệu sẽ có những thuộc tính như sau :

  1. Mỗi node ngoài giá trị value sẽ 2 giá trị là left và right ( right > left ). Ví dụ node A ( có left là 1, right là 8).
  2. Một node con cháu thuộc 1 node cha khi và chỉ khi left con > left cha AND right con < right cha. Ví dụ C là con của A ( 2 > 1 AND 5 < 8 ) và F là con của B ( 10 > 9 AND 11 < 12 ).
  3. Node ông tổ root có left = 0 và đường đi tăng dần sẽ theo "từ trên xuống dưới, từ trái qua phải". Xem hình minh họa bên dưới để hiểu rõ hơn đường đi.

nested_set_model_3

  1. Các giá trị left và right của tất cả các node tạo thành 1 dãy số tự nhiên liên tục từ 0 đến (N*2 + 1) với N là tổng số node của cây ( không tính node root).

Các bạn có thể giúp mình viết tiếp :

huynhtrucquyen0812 commented 9 years ago

Mị đã viết xong, mọi người test thử nhé :smile_cat: https://github.com/huynhtrucquyen0812/nested-set-model-with-sifoni

khanhicetea commented 9 years ago

Nên remove $child_name ra khỏi addNode($child_name, $parent_id, $position). Nói chung là những hàm xử lý NSM thì không nên care vào data của node làm gì :D

P/s : implement thử vào 1 trang nhé

huynhtrucquyen0812 commented 9 years ago

Âu mai gót, ghi sai tên biến mất tiêu.. :sweat: Đã sửa Cơ mà cái $child_name chỉ là cái tên node của user nhập vào thôi mà a. Không cung cấp thì lấy gì add dữ liệu :sweat_smile:

khanhicetea commented 9 years ago

à, thường thì sau khi set data xong thi nguoi ta sẽ chạy $node->addNode($parent_id, $postion) lúc này các hàm NSM sẽ không còn dạng static nữa

huynhtrucquyen0812 commented 8 years ago

Update 18/11/15: Thêm các function mới theo yêu cầu ở mục cuối 'Thêm function' https://github.com/huynhtrucquyen0812/nested-set-model-with-sifoni

khanhicetea commented 8 years ago

Chưa test nhưng có cố gắng đó :+1: