Cấu trúc dữ liệu đệ quy trong Rails

1. Tổng quan

Đôi khi bạn cần xây dựng một cấu trúc dữ liệu phân cấp/phân cấp trong Rails. Vì vậy hôm nay tôi sẽ giới thiệu cho các bạn một vài thiết kế đồng thời phân tích điểm mạnh và điểm yếu của mỗi thiết kế. Dưới đây là danh sách 4 mô hình thiết kế cấu trúc dữ liệu đệ quy/phân cấp:

• Adjacency List
• Nested Sets
• Path Enumeration
• Closure Table

Giờ ta có một ví dụ đơn giản để so sánh sự khác nhau của những mô hình trên

    Graph                 Table

       A                  node, parent
      /                   A,
     B   E                 B,     A
    /                     C,     B
   C  D                    D,     B
                           E,     A

2. Adjacency List

Đây là mô hình đơn giản nhất và là lựa chọn của đa phần lập trình viên.

Create table:

CREATE TABLE nodes( id SERIAL PRIMARY KEY, parent_id BIGINT NOT NULL, text varchar(10) NOT NULL);

Insert:

INSERT INTO nodes(id, parent_id, text)
  VALUES
    (1, 1, 'A'), -- Root.
    (2, 1, 'B'),
    (3, 2, 'C'),
    (4, 2, 'D'),
    (5, 1, 'E');

Select:

SELECT * FROM nodes where parent_id = 1;

id  | parent_id | text
----+-----------+------
  1 |         1 | A
  2 |         1 | B
  5 |         1 | E

Trong trường hợp này chúng ta chỉ có thể lấy được con gần gốc nhất chứ không lấy được toàn bộ cây. Vấn đề này xảy ra ở cả câu lệnh UPDATE và DELETE

• Ưu điểm :

  Model đơn giản

• Nhược điểm :

  Truy vấn nặng (Trừ khi DB hỗ trợ truy vấn đệ quy)

Adjacency List model là mô hình đệ quy đầu đủ nhưng việc cần yêu cầu DB phải hỗ trợ truy vấn đệ quy đẫn đến việc truy vấn phức tạp nên chưa đủ để trở thành một giải pháp hoàn thiện

3. Nested Sets

Đây là mô hình phổ biến thứ 2

Biểu diễn dạng đồ thị:

  +---------------------------+
  |             A             |
  |                           |
  | +-----------------+ +----+|
  | |       B         | | E  ||
  | |                 | |    ||
  | | +----+  +----+  | +----+|
  | | | C  |  | D  |  |       |
  | | |    |  |    |  |       |
  | | +----+  +----+  |       |
  | +-----------------+       |
  +---------------------------+
  1 2 3    4  5    6 7 8   9  10

Biểu diễn dữ liệu trong table:

id, text, lft, rgt
 1, A,    1,   10
 2, B,    2,   7
 3, C,    3,   4
 4, D,    5,   6
 5, E,    8,   9

Insert:

INSERT INTO nodes(id, text, lft, rgt)
VALUES
  (1, 'A', 1, 10),
  (2, 'B', 2, 7 ),
  (3, 'C', 3, 4 ),
  (4, 'D', 5, 6 ),
  (5, 'E', 8, 9 );

Select:

SELECT c.id, c.text, c.lft, c.rgt FROM nodes c, nodes p WHERE p.lft < c.lft AND p.rgt > c.rgt AND p.id = 2;

id, text, lft, rgt
3,  'C',  3,   4
4,  'D',  5,   6

Việc insert một bản ghi có thể không thành công hoặc rất chậm vì nó yêu cầu update những bản ghi cũ dựa trên vẩn ghi mới được insert vào. Đây cũng là một trong những nhược điểm của mô hình Nested Set.

• Ưu điểm:

  Select nhanh

  Model tương đối đơn giản

• Nhược điểm:

  Update chậm

4. Path Enumeration

Mô hình này thay vì lưu lại chỉ một parent_id mà nó sẽ lưu lại tất cả các id từ gốc đến cha chứa nó.

Create:

CREATE TABLE nodes(
    id        SERIAL PRIMARY KEY,
    path      VARCHAR(1000) NOT NULL, -- 1000 may become a limitation in case of very deep hierarchies
    text      TEXT NOT NULL
    -- make sure to index path for faster lookups
);

Insert:

INSERT INTO nodes(id, path, text) VALUES
    (1, '1/'    , 'A'), -- Root.
    (2, '1/2/'  , 'B'),
    (3, '1/2/3/', 'C'),
    (4, '1/2/4/', 'D'),
    (5, '1/5/'  , 'E');

Chú ý: Khi insert id của node sẽ chưa được xác định tại thời điểm insert. Vì vậy để phù hợp cần phải thêm một bước update để lấy được id nối vào mảng ids tương ứng

Select:

Việc select dữ liệu của hộ hình này thì tương đối đơn giản

Lấy ra những bản ghi có gốc id = 2

SELECT * FROM nodes WHERE path LIKE '1/2/' || '%';

2 | 1/2/   | B
3 | 1/2/3/ | C
4 | 1/2/4/ | D

Lấy ra toàn bộ tổ tiên của bản ghi với id = 4 bao gôm chính nó

SELECT * FROM nodes WHERE '1/2/4/' like path || '%';

  1 | 1/     | A
  2 | 1/2/   | B
  4 | 1/2/4/ | D

• Ưu điểm:

  Model đơn giản

• Nhược điểm:

  Khó tham chiếu trực tiếp Bị giới hạn chiều dài của path

5. Closure Table

Closure Table cũng giống với Path Enumeration ngoại trừ các path được lưu trữ ở một bảng riêng

Mô hình dữ liệu:

  Nodes                 Paths
  id, text              ancestor, descendant
   1, A                  1,       1
   2, B                  1,       2
   3, C                  1,       3
   4, D                  1,       4
   5, E                  1,       5
                         2,       2
                         2,       3
                         2,       4
                         3,       3
                         4,       4
                         5,       5

Create table:

CREATE TABLE nodes(id SERIAL, text VARCHAR(10));
CREATE TABLE paths(ancestor_id INTEGER, descendant_id INTEGER, PRIMARY KEY(ancestor_id, descendant_id));

Insert:

Yêu cầu ít nhất phải có 2 bản ghi để tạo thành 1 tree và node, path được lưu ở 2 bảng khác nhau

-- nodes
INSERT INTO nodes(id, text)
  VALUES
    (1, 'A'),
    (2, 'B'),
    (3, 'C'),
    (4, 'D'),
    (5, 'E');

-- paths
INSERT INTO paths(ancestor_id, descendant_id)
  VALUES
    (1, 1), (1, 2), (1, 3), (1, 4), (1, 5),
    (2, 2), (2, 3), (2, 4),
    (3, 3),
    (4, 4),
    (5, 5);

Select:

Lấy những nhánh có gốc với id = 2

SELECT nodes.*, paths.ancestor_id as parent_id
  FROM nodes
  JOIN paths on (nodes.id = paths.descendant_id)
  WHERE paths.ancestor_id = 2

id, text, parent_id
 2,  B,    2
 3,  C,    2
 4,  D,    2

Closure Table có một điểm khác với những mô hình còn lại là nó cho phép một node có thể có nhiều cha

• Ưu điểm: Mô hình tương đối đơn giản Cho phép một node có nhiều bố mẹ Dễ dàng tham chiếu

• Nhược điểm: Yêu cầu phải có 2 table Lưu trữ path chưa tối ưu (bị thừa)

6. Gem hỗ trợ

Dưới đây tôi sẽ giới thiệu một số gem hỗ trợ cho từng mô hình trên.

Adjacency List

• amerine/acts_as_tree

Path Enumeration

• Ancestry

• mdub/arboreal

Nested Sets

• Awesome Nested Set

• Nested Set

• Simple Nested Set

• Make Like a Tree

Closure Tree

• Closure Tree