Tìm hiểu về thư viện baum tree

Bài toán

Chúng ta có 1 menu đa tầng kiều như sau :

root
  |_ Child 1
    |_ Child 1.1
    |_ Child 1.2
  |_ Child 2
    |_ Child 2.1
    |_ Child 2.2

Phân tích bài toán

  • Thiết kế một hệ thống menu đa tầng không giới hạn (chia làm nhiêu cấp ông , cha, con , cháu, chắt ...v.v..v..)
  • Cần phải quản lý truy xuất dữ liệu linh hoạt dễ dàng , lấy được dữ liệu theo từng cấp một cách linh hoạt

Khó khăn

  • Cấu trúc đa tầng làm việc quản lý rất khó khăn từ việc thêm mới , sửa xóa .

  • Việc sử dụng cấu trúc cha con cổ điển dùng parent_id thì :

  • Khi lưu trữ dữ liệu thì dễ dàng cho việc lưu trữ dữ liệu

  • Tuy nhiên, khi lấy dữ liệu ra thì vô cùng khó khăn vì chúng không giới hạn tầng, bạn sẽ không thể biết chúng có bao nhiêu tâng cha con ⇒ cần đệ qui để query dữ liệu, điều này thực sự sẽ ảnh hưởng đến performance của hệ thống khi mà phải query nhiều .

Giải pháp

  • Sử dụng thuật toán Nested Sets , còn về vấn đề thuật toán Nested Sets là gì thì mình xin phép không giới thiệu trong bài viết này. Nếu các bạn cần tìm hiều nó thì có thể vào đây để tìm hiểu rõ ràng .
  • Hôm nay mình xin giới thiệu với các bạn 1 thư viện dùng để quản lý các menu (hoặc category , topic, comment hay bất kì cái gì mà phân đa tầng). Đó là thư viện etrepat/baum. Thư viện này dành cho laravel sử dụng thuật toán Nested Sets để quản lý dữ liệu.
  • Vơi thư viện này, bài toán chúng ta nói ở trên sẽ được chuyển về dạng data như sau :
id | parent_id | lft  | rgt  | depth | data
 1 |           |    1 |   14 |     0 | root
 2 |         1 |    2 |    7 |     1 | Child 1
 3 |         2 |    3 |    4 |     2 | Child 1.1
 4 |         2 |    5 |    6 |     2 | Child 1.2
 5 |         1 |    8 |   13 |     1 | Child 2
 6 |         5 |    9 |   10 |     2 | Child 2.1
 7 |         5 |   11 |   12 |     2 | Child 2.2

Nhìn 1 cách tổng thể hơn thì nó sẽ như thế này :

 ___________________________________________________________________
|  Root                                                             |
|    ____________________________    ____________________________   |
|   |  Child 1                  |   |  Child 2                  |   |
|   |   __________   _________  |   |   __________   _________  |   |
|   |  |  C 1.1  |  |  C 1.2 |  |   |  |  C 2.1  |  |  C 2.2 |  |   |
1   2  3_________4  5________6  7   8  9_________10 11_______12 13  14
|   |___________________________|   |___________________________|   |
|___________________________________________________________________|

Nào, bắt tay vào làm nhé

I, Cài đặt

  • Dùng composer tất nhiên . Add thêm đoạn sau vào file composer.json :
	"baum/baum": "~1.1"
  • Chạy lênh composer install để kéo code về.
  • Với các phiên bản laravel 5 trở lên đương nhiên bạn cần vào file config/app.php và thêm vào mục provider dòng sau :
'Baum\Providers\BaumServiceProvider',

II, Khởi tạo migrate

  • Để chạy đúng cho thư viện , bạn cần chắc chắn rằng phải có những cột dữ liệu sau :

  • parent_id: Tham số cho biết id của cha bản ghi

  • lft: chỉ số left của bản ghi (int)

  • rgt: chỉ số rightcủa bản ghi (int)

  • depth: đây là độ sâu của bản ghi (int)

Dưới đây là 1 file migrate mẫu , các bạn có thể xem và follow theo :

class Menu extends Migration {

  public function up() {
    Schema::create('menu', function(Blueprint $table) {
      $table->increments('id');

      $table->integer('parent_id')->nullable();
      $table->integer('lft')->nullable();
      $table->integer('rgt')->nullable();
      $table->integer('depth')->nullable();

      $table->string('data', 255);

      $table->timestamps();
    });
  }

  public function down() {
    Schema::drop('menu');
  }

}

NOTE :

Bạn có thể tự do đổi tên cột nhưng phải đổi cả các config bên trong model.

III, Khởi tạo model

  • Nếu bạn đã cài đặt đúng thì cách đơn giản nhất để khởi tạo model là sử dụng lệnh

php artisan baum:install MODEL

  • Với lệnh này bạn đã có 1 model quản lý dữ liệu sử dụng thư viện. Model nó sẽ có dạng như sau :
class Dictionary extends Baum\Node {

  protected $table = 'dictionary';

  // 'parent_id' column name
  protected $parentColumn = 'parent_id';

  // 'lft' column name
  protected $leftColumn = 'lidx';

  // 'rgt' column name
  protected $rightColumn = 'ridx';

  // 'depth' column name
  protected $depthColumn = 'nesting';

  // guard attributes from mass-assignment
  protected $guarded = array('id', 'parent_id', 'lidx', 'ridx', 'nesting');
}

NOTE

Các bạn phải đảm bảo đúng cho các cột trong database và các cột khai báo trong model phải khớp nhau.

IV : Cách sử dụng. 1 , Tạo và xóa

  • Bạn cần phải có một node root trước khi làm tạo một bản ghi. Để tạo root, chúng ta chỉ cần :
$root = Menu::create(['data' => 'Root']);
  • Nếu bạn muốn chuyển một node nào đó thành root thì chỉ cần :
$node->makeRoot();
  • Hoặc chuyển parent_id của nó về null là xong :
$node->parent_id = null;
$node->save();

Ok, khi mà chúng ta đã có root thì việc tạo ra node khác thì quá đơn giản, chỉ trong vòng 1 nốt nhạc . Có 2 cách , cụ thể là :

// Xác định cha ngay trước khi tạo con
$child1 = $root->children()->create(['name' => 'Child 1']);

// Tạo con xong rồi dùng method makeChildOf để trỏ đến cha
$child2 = Category::create(['name' => 'Child 2']);
$child2->makeChildOf($root);

Nếu bạn muốn xóa 1 node đi thì cũng vô cùng đơn giản, chỉ cần :

$child1->delete();

NOTE:

Nên nhớ rằng , khi bạn xóa 1 node như thế này thì các node con của node bị xóa cũng sẽ bị xóa theo và các giá tri left và right của cây cũng sẽ bị đánh lại

2, Việc di chuyển các node Baum cung cấp một số phương pháp để di chuyển các nút đi sang các vị trí xung quanh. Cụ thể là :

  • moveLeft(): Di chuyên sang bên trái của node cùng cấp với bản thân nó
  • moveRight(): Di chuyên sang bên phải của node cùng cấp với nó
  • moveToLeftOf($otherNode): Di chuyên sang bên trái của node cùng cấp với nút đích truyền vào
  • moveToRightOf($otherNode): Di chuyên sang bên phải của node cùng cấp với nút đích truyền vào
  • makeChildOf($otherNode): Chuyển sang làm node con của node đích
  • makeFirstChildOf($otherNode): Chuyển thành con đầu tiên của node đích
  • makeLastChildOf($otherNode): Chuyển thành nút con cuối cùng của nút đích. (Tác dụng giống makeChildOf)
  • makeRoot(): Chuyển sang node root

Ví dụ :

$root = Creatures::create(['name' => 'The Root of All Evil']);

$dragons = Creatures::create(['name' => 'Here Be Dragons']);
$dragons->makeChildOf($root);

$monsters = new Creatures(['name' => 'Horrible Monsters']);
$monsters->save();

$monsters->makeSiblingOf($dragons);

$demons = Creatures::where('name', '=', 'demons')->first();
$demons->moveToLeftOf($dragons);

3, Các câu hỏi liên quan đến node. Baum cung cấp 1 số thuộc tính giúp bạn hiểu được node chọn là node như thế nào thông qua các phương thức sau :

  • isRoot(): Trả về true khi nút đó là node root
  • isLeaf(): Trả về true khi nút đó là node lá (nút cuối cùng của nhánh)
  • isChild(): Trả về true khi nút đó là một node con.
  • isDescendantOf($other): Trả về true khi nút đó là hậu duệ (tức con, cháu , chắt ..v..v..) của nút đích
  • isSelfOrDescendantOf($other): Trả về true khi nút đó là bản thân hoặc hậu duệ (tức con, cháu , chắt ..v..v..v.. =)) ) của nút đích
  • isAncestorOf($other): Trả về true khi nút đó là tổ tiên (cha, ông , cụ ..v..v...) của nút đích
  • isSelfOrAncestorOf($other): Trả về true khi nút đó là bản thân hoặc tổ tiên của nút đích.
  • equals($node): Trả về true khi nút ngang bằng với nút đích

Ví dụ :

$demons->isRoot(); // => false

$demons->isDescendantOf($root) // => true

4 , Relations

Baum cung cấp 2 mối quan hệ trong Eloquent relations cho mỗi node. Đó là parentchildren . Bạn có thể dùng chúng như sau :

$parent = $node->parent()->get();

$children = $node->children()->get();

Ok, vậy là mình đã nói một số phần cơ bản để các bạn hiểu cơ chế của thằng Baum này, hẹn gặp lại các bạn trong bài viết lần sau. Mình sẽ đi sâu hơn về các sự kiện cũng như cách làm việc của nó.

TÀI LIỆU THAM KHẢO