Árboles B en Factorio

Aprendiendo sobre los árboles B

• Árboles binarios de búsqueda (Binary Search Trees, BSTs): cada nodo tiene una clave; el nodo izquierdo tiene valores de clave más bajos y el nodo derecho, valores de clave más altos.

• Los BST solo funcionan cuando las claves se pueden ordenar, y si los valores se agregan solo hacia un lado, se pierde el equilibrio y baja la eficiencia.

• Un BST desequilibrado puede corregirse mediante pivoteo, pero no es adecuado para almacenamiento en disco (requiere reequilibrado frecuente y los nodos adyacentes pueden almacenarse en páginas distintas).

• Árboles B (B-Trees): están compuestos por nodos con más claves y punteros que un árbol binario.

• Cada nodo tiene varias claves y varios punteros según cada clave (por ejemplo, un nodo con claves 17 y 24 tiene punteros a nodos con claves menores que 17, entre 17 y 24, y mayores que 24).

Implementación de árboles B en Factorio

• Implementación simple de un árbol binario de búsqueda en Factorio (juego de construcción de fábricas): cada nodo está compuesto por un cofre de madera (clave) y dos rutas (punteros).
• Como no hay una forma de comparar el valor de los materiales, se les asigna un orden arbitrario y se comparan usando brazos con filtro.
• La implementación de un árbol B es más compleja: cada nodo tiene tres claves y punteros a cuatro nodos hijo.
• Un árbol B puede almacenar más información y, en lugar de ordenar manualmente los ítems, el árbol se deja vacío hasta encontrar después una mejor forma de representación.

La opinión de GN⁺

• Lo más importante de este artículo es entender el concepto de los árboles B y el enfoque creativo de implementarlos dentro del juego Factorio.
• Lo interesante para los lectores es que ofrece una oportunidad de comprender de forma visual e intuitiva estructuras de datos complejas de la informática a través de un juego.
• Este enfoque hace que el aprendizaje sea más divertido y atractivo, y propone una nueva manera de explorar conceptos básicos de ingeniería de software mediante un medio no tradicional como los juegos.

[GN⁺]

Comentarios en Hacker News

• El diseño del juego Factorio no refleja perfectamente la teoría de ciencias de la computación, y se enfoca en disfrutar el juego más que en una forma de jugar teóricamente optimizada.
• En Factorio, los árboles binarios autoequilibrados (árboles 2-3, árboles rojo-negro, árboles B) no pueden reestructurarse, por lo que falta su función más importante: el autoequilibrado.
• Desde la perspectiva de la optimización, los insertadores en Factorio son más lentos que las cintas; mientras 4 insertadores procesan 12 ítems por segundo por cinta, una cinta azul puede procesar 45 ítems por segundo, así que para un diseño óptimo basado solo en cintas se recomienda usar divisores.
• La combinación de ciencias de la computación y divisores incluye el concepto de red de Beneš (una red compuesta solo por crossbars de 2 entradas y 2 salidas), y vale la pena estudiarla para diseñar fábricas eficientes.
• En Factorio, el diseño de cintas mezcladas es importante, y puede ser útil leer un libro sobre estructuras internas de bases de datos.
• Los árboles de búsqueda binaria (BST) no son adecuados para almacenamiento en disco, y buscar nodos en un árbol B es más rápido que recorrer punteros en un árbol binario. Aunque la complejidad de implementación aumenta, salvo que uses C, rara vez tendrás que implementar tú mismo un mapa basado en árboles.
• Se señala que la ausencia de mayúsculas puede dificultar la lectura del texto.
• Compartir contenido relacionado con Factorio despierta de nuevo las ganas de invertir cientos de horas en el juego.
• Todo puede hacerse solo con divisores, y no se necesitan cofres ni insertadores con filtro.
• Se comenta que se esperaba una implementación usando los circuitos de Factorio, pero no fue así.