Thông thường khi phải lưu dữ liệu có quan hệ cha con vào database ta hay thêm 1 trường parent_id vào trong bảng (cách này gọi là Adjacency List Model). Tuy nhiên nếu muốn lấy ra toàn bộ những bản ghi cha hoặc toàn bộ những bản ghi con của nó ta phải đệ quy trong code và query nhiều lần vào database hoặc đệ quy trong sql như mình đã giới thiệu trong bài trước.
Cách này sử dụng tốt khi quan hệ cha con đơn giản - 1 cha có từ 1 tới 2 con và quan hệ cha con không quá sâu (khoảng từ 1 - 3 tầng). Nếu gặp phải những bài toán cần lưu dữ liệu cha con phức tạp hơn thì có thể tham khảo Nested Set Model.

1. Nested Set Model tổng quan.

Nested Set Model là một kĩ thuật để lưu dữ liệu dạng cây trong cơ sở dữ liệu quan hệ.
Nguyên lý hoạt động: Bạn tưởng tượng một biểu đồ cây được lưu như những vòng tròn lồng nhau. Các vòng tròn con sẽ nằm trong vòng tròn cha của nó và cứ như vậy. Sau đó ta đánh số (theo kiểu tịnh tiến) cho các vòng tròn theo thứ tự từ trái sang phải.
Chẳng hạn ta có 1 gia phả như này:

Thì khi đánh số ta sẽ đánh theo thứ tự sau:

- Dữ liệu sẽ được lưu trong database theo dạng:

name          count_left  count_right group_id
Lưu Thiện     2           7           1
Lưu Bị        1           14          1
Lưu Duệ       3           4           1
Lưu Dao       5           6           1
Lưu Phong     8           9           1
Lưu Vĩnh      10          11          1
Lưu Lý        12          13          1

count_left và count_right là 2 chỉ số được đánh số theo hình trên, group_id để phân biệt gia phả của Lưu Bị với gia phả của các nhà khác, mình đặt giá trị này = id của node gốc trong vd trên thì sẽ là id của Lưu Bị để tiện cho việc truy vấn sau này.

2. Sử dụng Nested Set Model.

Trong đây có 1 vài đoạn code có sử dụng trường parent_id trong db tuy nhiên hãy hiểu parent_id là id nút cha mà người dùng truyền lên các bạn nhé. Thực tế là có thể bỏ hẳn trường này, nhưng lúc viết source mình đã migrate từ cách sử dụng quan hệ parent_id thông thường. Để có thể so sánh 2 cách mình vẫn để lại trường này.
Khi dùng nested set model sẽ làm tăng thời gian tạo mới bản ghi (khi thêm vào cây có sẵn ít nhất 1 node) do phải duyệt các node của cây có sẵn và đánh lại số cho 1 hoặc nhiều node trong cây. Cụ thể như sau.

def update_left_and_right
  parent_member = Member.find(parent_id)
  need_shift_members = Member.by_group_id(parent_member.group_id)
                             .where("count_right >= #{parent_member.count_right} OR count_left >= #{parent_member.count_right}")
  upsert_member_attributes = need_shift_members.map do |member|
                               member.count_left += 2 if member.count_left >= parent_member.count_right
                               member.count_right += 2 if member.count_right >= parent_member.count_right
                               member.attributes
                             end

  Member.upsert_all(upsert_member_attributes) if upsert_member_attributes.present?
end

cụ thể hơn có thể tham khảo source code mình gắn link ở cuối mục 3. Tổng kết
Ngược lại với tạo mới khi truy vấn sử dụng nested set model thì đơn giản và performance cao hơn nhiều do không phải truy vấn nhiều lần hoặc đệ quy sql (bản chất là join và merge bảng rất nhiều lần).

def ancestor_nested_set
  return unless nested_set?

  Member.by_group_id(group_id)
        .where("count_left < #{count_left} AND count_right > #{count_right}")
        .order_by_left
end

def descendant_nested_set
  return unless nested_set?

  Member.by_group_id(group_id)
        .where("count_left > #{count_left} AND count_right < #{count_right}")
        .order_by_left
end

Một vài truy vấn khác thì tham khảo trong link sau nha.

3. Tổng kết.

Nested Set Model dùng để lưu các dữ liệu dạng cây.
Nested Set Model có truy vấn dữ liệu nhanh hơn tuy nhiên thời gian tạo mới, xóa các node khỏi cây có sẵn sẽ lâu hơn cách dùng parent_id.
Hiện có rất nhiều thư viện sử dụng Nested Set Model như trong rails có act_as_tree.
Source code: https://github.com/LuuDai-bit/family-tree/blob/main/app/models/member.rb

4. Tham khảo

Viblo
MikeHillyer