Mở đầu

Cách đây 1 tháng dự án tôi đang làm có thêm chức năng lưu trữ file theo cấu trúc thư mục, do chưa có kinh nghiệm nên lúc thiết kế database tôi cũng nghĩ chắc chỉ cần parent_id là đủ.

Lúc đầu thì các yêu cầu không quá khó khăn với thiết kế database như trên thì có thể giải quyết ổn cả, như với việc lấy ra đường dẫn của thư mục đó thì tôi lấy theo parent_id cho đến khi nào gặp root (parent_id bằng nil), việc này mặc dù không tối ưu nhưng cũng không chậm quá nên tôi ậm ừ cho qua

  def recursive_parent
    temp_parent_id = self.parent_id
    recursive_folder = []
    while temp_parent_id != nil
      folder = Folder.find_by id: temp_parent_id
      if folder
        recursive_folder.unshift folder.as_json({only: [:id, :name]})
        temp_parent_id = folder.parent_id
      else
        temp_parent_id = nil
      end
    end
    recursive_folder
  end

Không được bao lâu thì tôi lại gặp vấn đề về search khi yêu cầu là tìm kiếm những file và folder trong thư mục bất kỳ, lúc đó tôi nghĩ nếu dùng đệ quy lấy hết file và folder trong trong từng folder thì không ổn vì chắc chắn hiệu năng rất thấp.

Tôi lên mạng tìm kiếm một số phương pháp về cách sử dụng một câu query để truy vấn nhưng khá phức tạp và khó hiểu. Và tôi tìm ra được một cách khá hay là sử dụng gem Awesome Nested Set.

Cài đặt và sử dụng

Để cài đặt đơn giản ta chỉ cần thêm vào Gemfile

gem "awesome_nested_set"

Để có thể sử dụng awesome_nested_set, ở trong database của bảng đó phải có 3 trường, mặc định là lft, rgt và parent_id. Tên của những trường này tất nhiên có thể được thay đổi tùy theo mình.

class AddTreeToFolders < ActiveRecord::Migration[5.0]
  def change
    add_column :folders, :lft, :integer
    add_column :folders, :rgt, :integer
    add_column :folders, :parent_id, :integer

    Folder.rebuild!
  end
end

Sau đó ta cần cho phép các chức năng của nested set có thể chạy được, bằng cách thêm vào model

class Folder < ActiveRecord::Base
  acts_as_nested_set
end

Sau khi thêm các phần trên ta cần chạy rails db:migrate để thêm các trường cần thiết, cũng như xây dựng cấu trúc cây từ dữ liệu có sẵn.

Giải thích một số hàm

Việc cài đặt và sử dụng gem này thì khá đơn giản, giờ ta sẽ đi sâu vào một số hàm cơ bản, bên trong nó làm những gì.

Về cơ bản cấu trúc cây khá đơn giản, ta cần lưu parent_id là id của node cha của node hiện tại, và lft, rgt lưu trọng số của 1 node, nó phải đảm bảo là các node con phải có trọng số bên trái lft phải lớn hơn trọng số bên trái lft của node hiện tại và trọng số bên phải rgt phải nhỏ hơn trọng số bên phải rgt của node hiện tại. Ví dụ như cây dưới đây thỏa mãn điều kiện.

Ta có thể viết lại truy vấn bằng Rails, giả sử nếu ta không dùng gem này thì ta sẽ làm như thế nào, giả sử ta đã thêm 3 trường là lft, rgt và parent_id. Let's do it.

1. Các hàm cơ bản

Roots

Hàm này lấy hết tất cả node gốc của cây, vì cây này có thể cho phép nhiều node gốc, cái này thì khá đơn giản ta chỉ cần:

# Folder.roots
Folder.where "parent_id IS NULL"

Ancestors

Đây là hàm lấy ra những node cha ông, cụ kị của node hiện tại, nếu duyệt từng node đến khi node là root thì có vẻ hơi lâu và mất nhiều câu truy vấn. Với việc thêm 3 trường phía trên đánh trọng số cho nó thì việc truy vấn đơn giản hơn rất nhiều:

# f.ancestors
Folder.where "lft < ? and rgt > ?", f.lft, f.rgt

Do cấu trúc cây được đánh trọng số cho nên việc lấy những node con chỉ cần lấy những node có trọng số lft nhỏ hơn lft của node hiện tại và trọng số rgt lớn hơn rgt của node hiện tại.

Descendants

Đây là hàm lấy ra những node con của node hiện tại, trái ngược với việc lấy ancestors, ta cần lấy những node có trọng số lft lớn hơn lft của node hiện tại và trọng số rgt nhỏ hơn rgt của node hiện tại.

# f.descendants
Folder.where "lft > ? and rgt < ?", f.lft, f.rgt

Leaves

Nhiều khi ta chỉ cần lấy lá của một node (lá là một node nhưng không có cây con), thì việc truy vấn gần giống với descendants nhưng ta cần thêm 1 điều kiện là rgt - lft = 1

# f.leaves
Folder.where "lft > ? and rgt < ? and rgt - lft = 1", f.lft, f.rgt

2. Các thao tác cơ bản

Thêm node

Ví dụ ta cần thêm 1 lá ở trong node Databases, ta cần thực hiện 2 bước:

• Tạo khoảng trống để chứa lá cần thêm vào và tạo lá, vì mỗi lá cần trọng số lft, rgt hơn nhau 1 đơn vị nên ta cần update rgt của node cha lên 2 đơn vị.

f.update_column :rgt, f.rgt + 2
Folder.create name: "MySQL", lft: 10, rgt: 11

• Cập nhật những node có lft hoặc rgt lớn hơn 11 (rgt của lá vừa được tạo)

folders = {}
Folder.where("lft >= ? OR rgt >= ?", 11, 11).each do |f|
    tmp_hash = {}
    tmp_hash[:lft] = f.lft + 2 if f.lft >= 11
    tmp_hash[:rgt] = f.rgt + 2 if f.rgt >= 11
    folders[f.id] = tmp_hash
end
Folder.update(folders.keys, folders.values)

Xóa node

Ví dụ ta cần xóa node Databases và ta cũng cần thực hiện 2 bước:

• Xóa node và những node con của nó (dependent: :destroy)

f.destroy 

• Cập nhật lại lft và rgt cho những node còn lại, ta cần cập nhật lft và rgt cho những node nào lớn hơn rgt của node mà mình muốn xóa (trong trường hợp này là 10), và lượng trừ đi bằng số node đã xóa đi * 2 hoặc tính bằng công thức rgt node hiện tại - lft node hiện tại + 1

folders = {}
Folder.where("lft > ? OR rgt > ?", 10, 10).each do |f|
    tmp_hash = {}
    tmp_hash[:lft] = f.lft - 6 if f.lft > 10
    tmp_hash[:rgt] = f.rgt - 6 if f.rgt > 10
    folders[f.id] = tmp_hash
end
Folder.update(folders.keys, folders.values)

Tổng kết

Awesome nested set là một gem rất hay ứng dụng kỹ thuật Nested set model, giúp ta tiết kiệm rất nhiều thời gian trong việc implement kỹ thật cũng như việc giảm thời gian truy vấn dữ liệu đối với dạng dữ liệu phân cấp. ###Tài liệu tham khảo:

• https://github.com/collectiveidea/awesome_nested_set
• https://en.wikipedia.org/wiki/Nested_set_model