B-Tree no Factorio

Aprendendo sobre B-Trees

• Árvores binárias de busca (Binary Search Trees, BSTs): cada nó tem uma chave; os nós à esquerda têm valores de chave menores, e os nós à direita têm valores de chave maiores.

• BSTs só funcionam quando as chaves podem ser ordenadas, e se os valores forem adicionados apenas de um lado, o balanceamento se perde e a eficiência cai.

• BSTs desbalanceadas podem ser corrigidas por meio de pivotamento, mas isso não é adequado para armazenamento em disco (exige rebalanceamento frequente, e nós adjacentes podem ficar armazenados em páginas diferentes).

• B-Trees: são compostas por nós com mais chaves e ponteiros do que uma árvore binária.

• Cada nó tem várias chaves e vários ponteiros de acordo com essas chaves (por exemplo: um nó com as chaves 17 e 24 teria ponteiros para nós com chaves menores que 17, entre 17 e 24, e maiores que 24).

Implementação de B-Tree no Factorio

• Implementação simples de uma árvore binária de busca no Factorio (jogo de construção de fábricas): cada nó é composto por um baú de madeira (chave) e dois caminhos (ponteiros).
• Como não há uma forma de comparar o valor dos materiais, é atribuída uma ordem arbitrária, e a comparação é feita usando braços filtradores.
• A implementação de B-Tree é mais complexa: cada nó tem três chaves e ponteiros para quatro nós filhos.
• A B-Tree pode armazenar mais informações e, em vez de ordenar itens manualmente, a árvore é deixada vazia por enquanto até que se encontre uma forma melhor de representá-la depois.

Opinião do GN⁺

• O ponto mais importante deste texto é entender o conceito de B-Tree e a abordagem criativa de implementá-la no jogo Factorio.
• O aspecto mais interessante para os leitores é que isso oferece uma oportunidade de compreender estruturas de dados complexas da ciência da computação de forma visual e intuitiva por meio de um jogo.
• Essa abordagem torna o aprendizado mais divertido e envolvente, além de sugerir uma nova forma de explorar conceitos fundamentais de engenharia de software por meio de um meio não tradicional como os jogos.

[GN⁺]

Comentários do Hacker News

• O design do jogo Factorio não reflete perfeitamente a teoria da ciência da computação e prioriza a diversão em vez de uma jogabilidade teoricamente otimizada.
• No Factorio, árvores binárias autoequilibradas (árvores 2-3, árvores rubro-negras, árvores B) não podem ser reestruturadas, então falta a funcionalidade mais importante: o autoequilíbrio.
• Do ponto de vista da otimização, os inserters do Factorio são mais lentos que as correias; enquanto 4 inserters processam 12 itens por segundo por correia, uma blue belt pode processar 45 itens por segundo, então recomenda-se usar splitters para um design ideal baseado apenas em correias.
• A combinação de ciência da computação e splitters inclui o conceito de rede de Benes (uma rede composta apenas por crossbars 2x2 de entrada e saída), e estudá-la é necessário para um projeto de fábrica eficiente.
• O design de correias mistas é importante no Factorio, e ler um livro sobre estruturas internas de bancos de dados pode ajudar.
• Árvores binárias de busca (BST) não são adequadas para armazenamento em disco, e a busca em nós de árvore B é mais rápida do que percorrer ponteiros de árvore binária. A complexidade de implementação aumenta, mas, a menos que se use C, é raro precisar implementar diretamente um map baseado em árvore.
• Aponta-se que a ausência de letras maiúsculas pode atrapalhar a leitura do texto.
• Compartilhar conteúdo relacionado a Factorio desperta novamente a vontade de investir centenas de horas no jogo.
• Tudo pode ser feito apenas com splitters, sem necessidade de caixas nem filter inserters.
• Observa-se que se esperava uma implementação usando os circuitos do Factorio, mas não foi o caso.