B-trees en Factorio

 (razberry.substack.com)
4 puntos por GN⁺ 2023-11-17 | 1 comentarios | Compartir por WhatsApp
  • Tras leer el capítulo de B-Tree del club de lectura de Database Internals, se implementó la estructura de datos no en código sino como una fábrica en Factorio para validar visualmente el concepto
  • Un BST solo puede ramificarse a izquierda y derecha cuando las claves son ordenables, y si los valores se cargan hacia un solo lado, la eficiencia de búsqueda puede caer al nivel de una lista lineal
  • En almacenamiento basado en disco, el costo de reequilibrio del BST y la lectura de varias páginas resultan pesados; el B-Tree reduce este problema al guardar varias claves en un solo nodo
  • La implementación en Factorio representa nodos y operaciones de comparación con cofres de madera y brazos filtradores morados, y crea la ruta de búsqueda definiendo un orden arbitrario de clasificación para los ítems
  • La versión con B-Tree usa 3 claves y 4 punteros por nodo, por lo que en 2 niveles puede contener muchas más claves que un BST, aunque siguen quedando pendientes los problemas de representación de valores y ordenamiento manual

Diferencia entre BST y B-Tree

  • El árbol binario de búsqueda (BST) guarda una clave en cada nodo, y envía las claves menores al nodo izquierdo y las mayores al nodo derecho
    • El ejemplo empieza con la clave raíz 8, a la izquierda 3 y a la derecha 10
    • Solo funciona con valores ordenables en los que se puede comparar qué clave es mayor o menor
  • Si se agregan muchos valores solo de un lado, el BST pierde el equilibrio
    • En el peor caso, termina siendo casi igual a una lista lineal ordenada como 8 -> 10 -> 14
    • Ese desequilibrio puede corregirse poniendo 10 como raíz y ubicando 8 y 14 a cada lado
  • En almacenamiento en disco, el BST sale perdiendo
    • Si se reequilibra continuamente, hay que actualizar con frecuencia el disco y los punteros
    • Los nodos vecinos pueden quedar almacenados en páginas distintas, así que una sola búsqueda puede requerir leer varias páginas
  • Un B-Tree guarda varias claves en un mismo nodo y apunta a nodos hijos con número de claves + 1 punteros
    • En el ejemplo, el nodo [17 | 24] se divide en tres nodos hijo: claves menores que 17, claves entre 17 y 24, y claves mayores que 24

Árbol de búsqueda implementado dentro de Factorio

  • Factorio es un juego de construcción de fábricas, y en esta implementación cada nodo del árbol se representa con estructuras dentro del juego
  • Primero se construye un BST simple
    • Cada nodo tiene un cofre de madera que guarda una clave y dos rutas que conectan con otros nodos
    • Como no existe un método de comparación por defecto entre materiales, se define un criterio arbitrario de orden: wood, coal, stone, brick, copper, iron, steel
    • Los brazos filtradores morados se encargan de la comparación
      • En el primer nodo, un brazo verifica si el ítem es igual a brick
      • El segundo brazo revisa si es menor que brick, como wood, coal, stone
      • El tercer brazo filtra valores mayores, como copper, iron, steel
    • En la parte superior derecha también se coloca un recolector de basura para retirar los ítems que entraron por error a la cinta transportadora
  • La implementación del B-Tree necesita más estructuras por nodo
    • Cada nodo tiene 3 claves, 3 brazos filtradores, 3 cofres de madera y 4 punteros a hijos
    • Puede almacenar mucha más información a la misma profundidad
    • En 2 niveles, el BST guarda 2 claves, pero el B-Tree guarda 12
    • En 3 niveles, el B-Tree puede crecer hasta 48 claves
  • Como no había ganas de elegir y ordenar manualmente 48 ítems en Factorio, el B-Tree se dejó vacío hasta encontrar una mejor forma de representar los valores
  • Se comparan BST y B-Tree lado a lado, y también se incluye un video de YouTube

Lecturas relacionadas

1 comentarios

 
GN⁺ 2023-11-17
Comentarios de Hacker News

  • Es un diseño ineficiente, pero implementar teoría de la computación en Factorio también implica, por definición, jugar de una manera no óptima.
    Factorio no es un juego hecho para presumir un B-Tree; al final, sus herramientas están diseñadas para jugar Factorio.

    1. La esencia de los árboles autoequilibrados como los árboles 2-3, los árboles rojo-negro y los B-Tree no es la estructura única del árbol en sí, sino la parte en la que se equilibran solos; pero en Factorio no se puede hacer que el árbol se reconfigure a sí mismo, así que falta su característica más importante.
    2. Desde el punto de vista de la optimización, los insertadores son más lentos que las cintas. Incluso usando 4 insertadores por cinta, solo pueden mover unas 12 unidades por segundo, mientras que una cinta azul puede empujar 45 por segundo. Si quisieras un diseño óptimo usando solo cintas, necesitarías un divisor que opere a 45 por segundo.
    3. Por eso, el punto de encuentro entre los divisores y la informática en Factorio está en los divisores de Factorio y la red de Benes. Si quieres estudiar una red construida solo con crossbars de 2 entradas y 2 salidas, conviene empezar por https://en.wikipedia.org/wiki/Clos_network. Una red de Benes no es más que una red Clos de tamaño 2 entradas y 2 salidas, y una red Clos puede tener tamaños arbitrarios como 5 a 7.
      La meta que parece existir en Factorio sería el diseño de “cintas mixtas”.
    • En una forma más concreta, existe la sushi belt, donde una sola cinta lleva varios materiales en equilibrio y gira sobre sí misma.
      Algunos diseños solo aceptan nuevos ítems en una proporción fija, y otros realmente vuelven a equilibrarse cuando el flujo se desordena. Personalmente, este es el que más me gusta: https://www.youtube.com/watch?v=7Gt5Zx0bsOQ
      Este ejemplo usa lógica de circuitos del juego, pero en los foros de Factorio también hay una sección sin circuitos: https://forums.factorio.com/viewforum.php?f=202
      Lo curioso es que el objeto “fish” de Factorio es un ítem de broma inútil, pero justamente porque no se usa para nada, a veces se emplea como valor nulo, como bandera de que una cinta completó una vuelta, o como herramienta de depuración: https://forums.factorio.com/viewtopic.php?p=544302#p544302
    • Me pregunto cómo sería una extensión de Factorio como “Scriptorio”, que permitiera poner JSON sobre las cintas transportadoras, junto con fábricas de funciones JavaScript o Lua.
      Entonces no solo podrías mover por las cintas y los insertadores los objetos a insertar o buscar, sino también el propio B-Tree.
      Podrías escribir una función de búsqueda recursiva usando un bucle de cinta transportadora que atraviese la fábrica, quitando una capa del árbol en cada nivel hasta llegar a una hoja, romper el bucle y sacar el resultado.
      Es un modelo de ejecución interesante, más cercano al flujo de datos que a JavaScript estándar. ¿Habría que permitir “túnel cuántico” o “acción a distancia”, haciendo que distintas cintas transportadoras, insertadores y fábricas apunten por múltiples referencias al mismo objeto JSON base? Podría ser útil, pero como Factorio tradicionalmente trata cada ítem físico como si tuviera una identidad única, quizá sería más “realista” no admitir múltiples referencias. O tal vez, después de investigar la tecnología “Quantum Tunneling JSON”, solo se podrían crear múltiples referencias en una “JSON Reference Entangler Factory”.
    • Hojeando por encima el artículo sobre redes Clos, parece que si se pudiera construir una red así en Factorio, también serían posibles diseños simples de redes neuronales como el que se ve aquí: [1]
      También parecería posible cambiar la salida dando pesos a la densidad de recursos que llega a ciertas posiciones. Viendo el mecanismo que aparece aquí [2], da la impresión de que se podrían crear decisiones ponderadas por densidad usando combinación, separación y las tres velocidades de cinta.
      [1] https://www.asimovinstitute.org/wp-content/uploads/2019/04/N...
      [2] https://wiki.factorio.com/Belt_transport_system#Splitters
    • Me gustaría ver después si también se puede implementar el autoequilibrio. Pensé que los bots podrían ser útiles aquí, aunque no sé si se les puede hacer construir planos dinámicamente.
    • Por eso no juego Factorio. Ese nivel de recursos mentales se puede usar por el bien de la humanidad, y si muestras el resultado hasta puedes conseguir reacciones en redes sociales.
      Los juegos que te exigen cerebro a cambio de números en una pantalla están al final de mi lista. Yo quiero aprender algo nuevo.
      Puede haber un elemento de rompecabezas y podemos decidir que eso es divertido, pero ¿por qué no decidir también que estudiar es divertido?

  • Gran trabajo.
    Estoy leyendo “Database Internals” en un club de lectura, y esta semana tocó el capítulo 2, que trataba sobre B-Tree.
    Por cierto, las inscripciones ya cerraron, pero si quieres puedes conseguir Database Internals y seguir el calendario y las notas de aquí en modo “solo lectura”: https://eatonphil.com/2023-database-internals.html

  • Las razones por las que “los árboles de búsqueda binaria no son buenos para almacenamiento en disco” también aplican al almacenamiento en memoria
    Buscar un solo nodo de un B-Tree es más rápido que seguir la misma cantidad de punteros en un árbol binario. Claro, la complejidad de implementación sube, pero salvo que uses C, normalmente no vas a implementar tú mismo un mapa basado en árboles
    También son posibles variantes donde se ponen más elementos en los nodos internos y los valores se almacenan solo en las hojas. A menos que estés haciendo solo un conjunto y no un mapa. Si además conectas nodos vecinos, prácticamente se acerca a una skip list

  • No sé por qué justo aquí tenía que aparecer contenido de Factorio y darme otra vez ganas de perder unas 100 horas. Este año ya hay demasiados juegos buenos que valen la pena

    • Para finales del próximo año está prevista una gran reorganización y la expansión Space Age, así que quizá no está mal esperar hasta entonces

  • Todo esto también se podría hacer con divisores, y no parecería que hicieran falta cofres ni insertadores con filtro. La explicación está bien

    • No entiendo cómo
      No se trata simplemente de dividir la salida en varias líneas. Los cofres aquí representan los ítems almacenados en el “nodo” correspondiente de este B-Tree dispuesto en 2D
      No tuve tiempo de ver el video, pero por el texto y las capturas parece que hay lógica asociada a los insertadores para enviar los ítems por la ruta correcta de nodos hijos, manteniendo la propiedad “ordenada” del árbol
      Viendo la elección de claves del post original, dividirlo con divisores sí sería posible, pero si no recuerdo mal los divisores solo aceptan un filtro, así que harían falta varios en cada punto de ramificación. O sea, tantos como ítems haya en ese punto. Los insertadores con filtro permiten varios filtros, así que aquí encajan mejor, y se puede ver ya en la primera captura
      Claro, también podrías abandonar por completo el diseño de B-Tree y ordenar en n cofres con n divisores, pero eso no tendría gracia y no parece ser lo que buscaba el post original
    • Está asignando varios ítems a cada insertador
      El filtro de un divisor manda un solo ítem a un lado y todo lo demás al otro. Pero este ejemplo es distinto porque varios tipos van a un lado y varios tipos van al otro
    • Hay que ordenar y filtrar varios ítems. Por ejemplo, en el primer nodo habría que mandar madera, carbón y piedra a la izquierda, y metal a la derecha, pero el filtro del divisor solo puede filtrar un ítem

  • Me da curiosidad si Factorio es realmente tan buen juego. Todo el mundo dice que sí, pero el tema de construir fábricas se ve algo aburrido y me preocupa que el juego sea demasiado repetitivo

    • Antes de probarlo yo también era bastante escéptico y tenía la misma preocupación. Pero cuando me di cuenta ya le había metido más de 100 horas
    • Todos los jugadores de Factorio que conozco le han dedicado más de 1,000 horas

  • Está muy genial, pero como comentario entre gente que intenta escribir, se siente bastante distractor no usar mayúsculas al inicio de las oraciones

  • Pensé que lo iban a implementar con el sistema de circuitos de Factorio