------------
So I have to comments. #1 is about the Comp-Sci side, and #2 is about the optimization side. #3 combines both together for what I'd like to talk about.
1. Self-balancing trees (2-3 trees, Red-black Trees, and B-Trees) are about the self-balancing part. Not just the construction of a singular tree. You cannot recongfigure trees to rebuild themselves in Factorio, so the biggest feature is missing already.
2. From an optimization perspective: inserters are slower than belts. Even 4 inserters per belt only allows like 12-items per second, and blue-belts can push 45 items-per-second. You want to use splitters (which operate at full speed: 45 items per second) for the best belt-only design. (Bots obviously sort items fastest, but I am presuming this is some kind of belt-only challenge build).
3. The intersection of splitters + computer science is therefore: the Splitter (Factorio) and Benes Networks (creation of networks built off of only a 2-input to 2-output crossbar). If you really want to have a crazy good factory design, start studying this stuff: https://en.wikipedia.org/wiki/Clos_network (A Benes network is simply a Clos network of size 2-input and 2-outputs. Clos networks are of any size: like 5-to-7 and other such odd numbers)
--------
In Factorio, the meta you want to be searching for is "mixed belt" design, it seems.
A more specific case is the "sushi belt" where one belt balances multiple ingredients while looping around on itself.
Sometimes they just accept new items in a fixed ratio, sometimes they can actually rebalance if disturbed. This is my favorite https://www.youtube.com/watch?v=7Gt5Zx0bsOQ
While that one uses the in-game circuitry logic, the Factorio forum has a "circuit-free" section https://forums.factorio.com/viewforum.php?f=202
And my favorite fun fact: The "fish" object in Factorio is a useless joke item, but because it isn't used by anything, it's sometimes used as a null value, a flag for when a belt has completed a full loop, or a debugging tool. https://forums.factorio.com/viewtopic.php?p=544302#p544302
1. Fish is a crafting item for spidertron, it's not completely useless. 2. In multiplayer, the standard null-value item is the deconstruction planner (which is a big red square). I guess some people might use fish, but I've never seen it. It helps that deconstruction planners are free, nowadays, if you click the red button at the bottom-screen UI. 3. Fish is incredibly useful for fighting in early-game - if a nest won't stop bugging you, just go to the nearest pond, grab a few dozen fish, and you're basically invincible for a few minutes as long as you spam fish whenever you reach low health. Make sure to bring extra pistol ammo though, otherwise killing the nests will take ages (you can melee them to death but it deals even less damage than pistols).
Then you could pass the b-trees themselves around with conveyor belts and inserters, as well as the objects to insert and search.
And write a recursive search function with a loop of conveyor belts running through factories, that just loops the tree around peeling off a level at a time until it hits the leaf, breaking the loop and outputting the result.
It's an interesting execution model, not standard JavaScript, more data flow. Should you allow "quantum tunneling" and "action at a distance" by allowing multiple references to the same underlying JSON objects from different conveyor belts / inserters / factories? That could be useful, but Factorio itself traditionally treats each physical item having a unique identity, so maybe it would be more "realistic" not to support multiple references. Or you can only make multiple references once you research "Quantum Tunneling JSON" technology, with the "JSON Reference Entangler Factory"!
If it doesn't exist you can probably wedge it in fairly easily.
I suggest that it would be worth your time to give it a poke just to see what a thoroughly excellent example of software engineering they've made there.
[1] https://www.asimovinstitute.org/wp-content/uploads/2019/04/N...
[2] https://wiki.factorio.com/Belt_transport_system#Splitters
You can click on your logistic auto-fetch feature and just have robots search all the boxes for the items you want, and they'll automatically refill your inventory to 300-belts.
And then when you build a belt somewhere, you can either choose from your inventory, or shift-click and/or blueprint build to have robots search for those items in your entire logistic network and they just fly out, find the item, come back, and place it for you. Just in like 2 or 3 clicks (or less).
So for a lot of these challenges and demonstrations, Factorio players aim for "belts only" or other such constraints, to try and force ourselves into design constraints. Belts-only also uses zero-power (bots need power to function, and its rather substantial in practice). So there's power-benefits to going belt-only.
-----------------------
So what is your goal here? If its to build a tree in Factorio, I think we can say you succeeded.
But its not the optimal play or the "meta" factory design, lol. But I recognize that's not quite what you were going for. (Ex: the meta would be to just use bots in a bot-factory. Or keep items sorted in a belt factory, no reason to mix belts)
I think pushing players to think deeply about the "meta", including the deep thoughts upon how CLOS Networks apply to high-quality Belts/and/splitter designs, is very rewarding. Its not about trees though.
-----------
Mixed-belts are fun though. And I think I spent many good hours and weeks thinking about them back in my Factorio days. Lots of interesting problems to solve, but I think my problem was that these solutions weren't meta, nor did they demonstrate any beautiful mathematical concept.
Benes Networks / CLOS networks applied to belts however, were a perfect match. The best builds were those that matched the deep mathematical/comp. sci foundation of Benes Networks. So it was the "more fun" part of Factorio to me. Not only was I learning some deep Comp. Sci topic, but when I improved my designs based on CLOS Networks, they instantly led to improved belt-balance and throughput in my factory designs.
Not in the base game, but there's a mod for it. Nilaus recently did a short series of videos on YouTube where he used it to make an auto-expanding factory, so you should be able to find the mod name there if you want to mess with it.
Video games that ask me to provide brainpower in return for numbers on a screen are bottom of my list. I want to learn something new.
Sure there might be puzzle aspects, and yes we decide that it is fun... but can't you also decide your studies are fun too?
Pulling off a belt will be a notable slowdown, and picking items off of a wildly mixed belt will be a huge slowdown.
> i've been reading Database Internals with a book club, and this week was chapter 2, about B-Trees.
For the crowd: signups are closed. But if you want: grab a copy of Database Internals and follow along "read-only" with the schedule and notes here: https://eatonphil.com/2023-database-internals.html.
The listed reasons also apply to in-memory storage – searching a btree node is faster than doing the equivalent amount of pointer traversals for a binary tree. Of course this comes at the cost of increased implementation complexity, but unless you're using C, you're probably not implementing your own tree-based map.
You can then use different variants such as packing more entries into interior nodes by only storing values in the leafs (assuming you're making a map and not just a set, that is). If you then link neighboring nodes, you basically have a skip list.
[0] https://abseil.io/blog/20190812-btree
[1] https://opensource.googleblog.com/2013/01/c-containers-that-...
They're not just trying to split an output into multiple lanes. The boxes represent the item stored in that "node" of the B-Tree (laid out here in 2D).
I haven't had time to watch the video, but the prose & screenshots indicates there is associated logic on the inserters to maintain the "sorted" nature of the tree, by sending stuff down the appropriate path to child nodes.
Given the OP's choice of values for keys … you could use splitters to do the splitting, but IIRC splitters only accept a single filter, and so you'd need many of them at each junction (as many as items at that junction). Filter-serters permit several filters, which is a bit nicer here. (You can see that in first screenshot.)
(Unless you just forgo the entire B-Tree design and just n-splitters to sort into n boxes … but that's boring and I think isn't what the OP is going for.)
There's almost no reason to use inserters for belt-to-belt transfers for modern meta, aside from a few speed-running stats where you use red-inserters while skipping logistics2 or something.
But if you're trying to sort items on a belt by placing them onto another belt, the answer is a splitter. Item A splits off to another belt, while all other items loop back.
Splitter filters only filter one thing to one side, and everything else to the other side. That's not what is happening in this example though, where several things are going one way, and several things are going the other way.
