B-Bäume in Factorio

Lernen über B-Bäume

• Binäre Suchbäume (Binary Search Trees, BSTs): Jeder Knoten hat einen Schlüssel; der linke Knoten enthält kleinere Schlüsselwerte, der rechte größere.

• BSTs funktionieren nur, wenn Schlüssel sortierbar sind, und wenn Werte nur auf einer Seite hinzugefügt werden, gerät der Baum aus dem Gleichgewicht und wird ineffizient.

• Ein aus dem Gleichgewicht geratener BST kann durch Pivoting korrigiert werden, ist aber für festplattenbasierten Speicher ungeeignet (häufiges Rebalancing ist nötig, und benachbarte Knoten können auf unterschiedlichen Seiten gespeichert sein).

• B-Bäume (B-Trees): bestehen aus Knoten mit mehr Schlüsseln und Zeigern als binäre Bäume.

• Jeder Knoten besitzt mehrere Schlüssel und entsprechend mehrere Zeiger (z. B. verweist ein Knoten mit den Schlüsseln 17 und 24 auf Knoten mit Schlüsseln kleiner als 17, zwischen 17 und 24 sowie größer als 24).

Implementierung eines B-Baums in Factorio

• Einfache Implementierung eines binären Suchbaums in Factorio (dem Fabrik-Aufbauspiel): Jeder Knoten besteht aus einer Holzkiste (Schlüssel) und zwei Pfaden (Zeiger).
• Da es keine Möglichkeit gibt, den Wert von Materialien zu vergleichen, wird ihnen eine willkürliche Reihenfolge zugewiesen und der Vergleich mit Filterarmen durchgeführt.
• Die Implementierung eines B-Baums ist komplexer: Jeder Knoten hat drei Schlüssel und vier Zeiger auf Kindknoten.
• Ein B-Baum kann mehr Informationen speichern; statt Elemente manuell zu sortieren, bleibt der Baum vorerst leer, bis später eine bessere Darstellungsform gefunden wird.

Meinung von GN⁺

• Das Wichtigste an diesem Beitrag ist, das Konzept des B-Baums zu verstehen und den kreativen Ansatz zu sehen, es im Spiel Factorio umzusetzen.
• Für Leserinnen und Leser ist besonders interessant, dass komplexe Datenstrukturen der Informatik durch ein Spiel visuell und intuitiv verständlich werden.
• Ein solcher Ansatz macht Lernen unterhaltsamer und ansprechender und zeigt neue Wege, grundlegende Konzepte des Software Engineering über ein nicht traditionelles Medium wie ein Spiel zu erkunden.

[GN⁺]

Hacker-News-Kommentar

• Das Design des Spiels Factorio bildet informatiktheoretische Konzepte nicht perfekt ab und legt den Schwerpunkt eher auf Spielspaß als auf theoretisch optimiertes Spielen.
• In Factorio können selbstbalancierende Binärbäume (2-3-Bäume, Rot-Schwarz-Bäume, B-Bäume) nicht umstrukturiert werden, sodass die wichtigste Eigenschaft, die Selbstbalancierung, fehlt.
• Unter Optimierungsgesichtspunkten sind Inserter in Factorio langsamer als Förderbänder: Vier Inserter schaffen pro Band 12 Items pro Sekunde, während ein blaues Band 45 Items pro Sekunde transportieren kann. Für ein optimales bandbasiertes Design wird daher der Einsatz von Splittern empfohlen.
• Die Verbindung von Informatik und Splittern umfasst das Konzept des Benes-Netzwerks, also eines Netzwerks, das nur aus 2-Eingang-2-Ausgang-Crossbars besteht; für effizientes Fabrikdesign lohnt sich eine Beschäftigung damit.
• In Factorio ist das Design gemischter Bänder wichtig, und es kann hilfreich sein, ein Buch über die internen Strukturen von Datenbanken zu lesen.
• Binäre Suchbäume (BST) eignen sich nicht gut für plattengestützte Speicherung, und die Knotensuche in B-Bäumen ist schneller als das Traversieren von Zeigerstrukturen in Binärbäumen. Die Implementierung ist zwar komplexer, aber außer in C implementiert man baumbasierte Maps nur selten selbst.
• Es wird angemerkt, dass das Fehlen von Großbuchstaben das Lesen des Textes erschweren kann.
• Geteilte Factorio-Inhalte wecken erneut den Wunsch, wieder Hunderte Stunden in das Spiel zu investieren.
• Alles lässt sich allein mit Splittern erledigen; Kisten und Filter-Inserter sind nicht nötig.
• Es wird darauf hingewiesen, dass man eine Umsetzung mit den Schaltungen von Factorio erwartet hätte, dies aber nicht der Fall ist.