Xây dựng cấu trúc cây cho ứng dụng Ruby với Awesome Nested Set
Bài đăng này đã không được cập nhật trong 5 năm
Khi phát triển một ứng dụng Rails thì bạn sẽ rất hay gặp phải bài toán xây dựng cấu trúc cây cho dữ liệu. Bạn hoàn toàn có thể làm thủ công với trường parent_id
kết hợp với đệ quy và các câu query để thực hiện công việc. Tuy nhiên với những cấu trúc cây phức tạp, việc thực hiện sẽ rất phức tạp và tốn thời gian, hiệu suất công việc thấp.
Bài viết này mình xin giới thiệu đến các bạn gem Awesome Nested Set dùng để xây dựng cấu trúc cây (vote 2116 star trên github tại thời điểm viết bài).
Link github: Awesome Nested Set
Bản chất
Được thiết kế dưới mô hình thiết kế Nested Sets
Về cơ bản cấu trúc cây khá đơn giản, ít nhất có 3 thông tin sau cần có cho một node:
parent_id
là id của node cha của node hiện tại.lft
,rgt
lưu trọng số của 1 node; phải đảm bảo là các node con phải có:- Trọng số bên trái
lft
lớn hơn trọng số bên tráilft
của node cha - Trọng số bên phải
rgt
phải nhỏ hơn trọng số bên phảirgt
của node hiện cha.
- Trọng số bên trái
Hãy xem ví dụ về một cây sau đây.
Chuyển cây thành sơ đồ ven quen thuộc.
Ta sẽ có cách đánh trọng số rgt
và lft
như sau là thỏa mãn.
Ưu điểm:
- Select nhanh.
- Mô hình đơn giản, dễ sử dụng.
Nhược điểm
- Update chậm (hoặc có thể không update được vì phải cập nhật lại chỉ số của những node khác trong cây)
Cài đặt
Thêm vào Gemfile dòng:
gem 'awesome_nested_set'
Và tiến hành bundle install.
Sử dụng
Thiết lập
Để sử dụng gem awesome_nested_set
cho model nào thì bắt buộc bảng tương ứng phải có ít nhất 3 trường: parent_id
, lft
, rgt
. Ngoài ra bạn còn thể thêm 2 trường depth
và children_count
(trường này nếu có thì bắt buộc phải set null: false
và default: 0
). Ví dụ với việc tạo bảng categories
như sau:
class CreateCategories < ActiveRecord::Migration
def self.up
create_table :categories do |t|
t.string :name
# required fields
t.integer :parent_id, null: true, index: true
t.integer :lft, null: false, index: true
t.integer :rgt, null: false, index: true
# optional fields
t.integer :depth, null: false, default: 0
t.integer :children_count, null: false, default: 0
end
end
def self.down
drop_table :categories
end
end
Nếu muốn áp dụng cấu trúc cây cho model đã có sẵn từ trước, ta cần migrate để thêm các trường cần thiết vào, sau đó thì bạn cần build lại model đó để điền thông tin của cây vào, có thể thêm luôn vào file migration như sau:
Category.reset_column_information
Category.rebuild!
Bạn cần khai báo thêm acts_as_nested_set
trong model như sau:
class Category < ActiveRecord::Base
acts_as_nested_set
end
Tất cả những trường được thêm vào bảng phục vụ cho gem đều có thể thay đổi tên tùy thuộc vào bạn config, có thể thay đổi parent_column
, left_column
, right_column
, depth_column
. Bạn có thể tham khảo thêm ở đây.
Đến đây thì model Category
đã sẵn sàng.
Chú ý Bạn nên thêm index cho các trường của awesome_nested_set
để có thể tìm kiếm nhanh chóng hơn.
Cách sử dụng cơ bản.
Bạn có thể tham khảo các hàm cơ bản ở đây.
- Tạo node root thì rất đơn giản:
science = Category.create!(name: 'Science')
- Thêm node con:
physics = Category.create!(:name => 'Physics')
physics.move_to_child_of(science)
Một số hàm
Class method
root
node root đầu tiênroots
tất cả các node root, cây có thể có nhiều root, lệnh này khá đơn giản và nó hoạt động tương tựCategory.where(parent_id: nil)
Instance method
root
node gốc của node hiện tại, root của note f thì lệnh này tương tự nhưCategory.where(parent_id: nil).where("lft < ? and rgt > ?", f.lft, f.rgt)
parent
node cha trực tiếp.children
mảng các node con trực tiếp (chỉ ở level kế tiếp).ancestors
mảng các node tổ tiên (từ node gốc), ngoại trừ chính nó. Ngoài ra còn cóself_and_ancestors
.siblings
mảng tất cả các node có cùng node cha (cùng level), ngoại trừ chính nó. Ngoài ra còn cóself_and_siblings
.descendants
mảng tất cả node con cháu, ngoại trừ chính nó. Ngoài ra còn cóself_and_descendants
.leaves
mảng tất cả các node lá (hậu duệ mà không có con).
Một số instance method mà không cần phải thao tác đến DB.
root?
trả về true
nếu là node gốc (không có cha).
child?
trả về true
nếu là node con (có cha).
is_ancestor_of?(obj)
trả về true
nếu là tổ tiên của obj
.
is_descendant_of?(obj)
trả về true
nếu là hậu duệ của obj
.
leaf?
trả về true
nếu là node lá (không có node con).
Kết
Trên đây mình đã giới thiệu những khái niệm cũng như cách sử dụng cơ bản của gem Awesome Nested Set để xây dựng cấu trúc cây. Hi vọng bài viết sẽ này sẽ hữu ích với bạn.
Bài viết sau mình sẽ giới thiệu một gem khác tương tự được xây dựng trên mô hình Path Enumeration cho cấu trúc cây.
Tham khảo
All rights reserved