B-tree trong Factorio

Tìm hiểu về B-tree

• Cây tìm kiếm nhị phân (Binary Search Trees, BSTs): mỗi nút có một khóa; nút bên trái có giá trị khóa thấp hơn, còn nút bên phải có giá trị khóa cao hơn.

• BST chỉ hoạt động khi các khóa có thể sắp xếp được; nếu các giá trị chỉ được thêm về một phía thì cây sẽ mất cân bằng và hiệu quả giảm đi.

• BST bị mất cân bằng có thể được sửa bằng cách xoay trục (pivoting), nhưng không phù hợp với lưu trữ dựa trên đĩa (cần tái cân bằng thường xuyên và các nút kề nhau có thể được lưu ở những trang khác nhau).

• B-tree: gồm các nút có nhiều khóa và con trỏ hơn so với cây nhị phân.

• Mỗi nút có nhiều khóa và nhiều con trỏ tương ứng với từng khóa (ví dụ: một nút có khóa 17 và 24 sẽ có con trỏ đến các nút có khóa nhỏ hơn 17, các nút có khóa nằm giữa 17 và 24, và các nút có khóa lớn hơn 24).

Triển khai B-tree trong Factorio

• Cách triển khai cây tìm kiếm nhị phân đơn giản trong Factorio (trò chơi xây dựng nhà máy): mỗi nút gồm một rương gỗ (khóa) và hai tuyến đường (con trỏ).
• Vì không có cách nào để so sánh giá trị của các vật liệu, tác giả gán cho chúng một thứ tự tùy ý và dùng tay máy lọc để so sánh.
• Việc triển khai B-tree phức tạp hơn: mỗi nút có ba khóa và bốn con trỏ tới các nút con.
• B-tree có thể lưu nhiều thông tin hơn; thay vì sắp xếp vật phẩm thủ công, tác giả tạm để cây trống cho đến khi tìm ra cách biểu diễn tốt hơn sau này.

Ý kiến của GN⁺

• Điều quan trọng nhất trong bài viết này là hiểu được khái niệm B-tree và cách tiếp cận sáng tạo khi triển khai nó trong trò chơi Factorio.
• Điểm thú vị với độc giả là bài viết mang đến cơ hội hiểu các cấu trúc dữ liệu phức tạp của khoa học máy tính theo cách trực quan và dễ cảm nhận thông qua trò chơi.
• Cách tiếp cận này khiến việc học trở nên thú vị và hấp dẫn hơn, đồng thời gợi ra một phương thức mới để khám phá các khái niệm nền tảng của kỹ thuật phần mềm thông qua những phương tiện phi truyền thống như trò chơi.

[GN⁺]

Ý kiến trên Hacker News

• Thiết kế của game Factorio không phản ánh hoàn toàn lý thuyết khoa học máy tính, mà tập trung vào việc tận hưởng trò chơi hơn là lối chơi được tối ưu hóa về mặt lý thuyết.
• Trong Factorio, các cây nhị phân tự cân bằng (cây 2-3, cây đỏ-đen, cây B) không thể tái cấu trúc, nên thiếu đi chức năng quan trọng nhất là tự cân bằng.
• Xét từ góc độ tối ưu hóa, inserter trong Factorio chậm hơn belt; 4 inserter xử lý 12 item mỗi giây trên một belt, trong khi blue belt có thể xử lý 45 item mỗi giây, nên với thiết kế tối ưu chỉ dùng belt thì nên dùng splitter.
• Sự kết hợp giữa khoa học máy tính và splitter bao gồm khái niệm mạng Beneš (mạng chỉ gồm các crossbar 2 đầu vào 2 đầu ra), và cần nghiên cứu về nó để thiết kế nhà máy hiệu quả.
• Thiết kế mixed belt rất quan trọng trong Factorio, và việc đọc sách về cấu trúc nội bộ của cơ sở dữ liệu có thể hữu ích.
• Cây tìm kiếm nhị phân (BST) không phù hợp với lưu trữ trên đĩa, và việc tìm kiếm nút trong cây B nhanh hơn so với duyệt con trỏ của cây nhị phân. Độ phức tạp khi triển khai tăng lên, nhưng trừ khi dùng C, hiếm khi cần tự triển khai map dựa trên cây.
• Có ý kiến cho rằng việc không dùng chữ in hoa có thể gây cản trở khi đọc bài.
• Nội dung liên quan đến Factorio được chia sẻ đã khơi lại mong muốn đầu tư thêm hàng trăm giờ vào trò chơi.
• Mọi thứ đều có thể làm chỉ bằng splitter, không cần chest hay filter inserter.
• Có người chỉ ra rằng họ đã nghĩ bài viết sẽ được triển khai bằng circuit của Factorio, nhưng thực tế không phải vậy.