Giới thiệu gem Awesome Nested Set - Thích hợp cho quản lý model cấu trúc cây
This post hasn't been updated for 3 years
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 updatergt
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ặcrgt
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ậtlft
vàrgt
cho những node nào lớn hơnrgt
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:
All Rights Reserved