b-trees in factorio – rants by razberry
i have been studying Database Internals with a e book membership, and this week was chapter 2, about B-Timber.
however first, binary search timber
Every node accommodates a key, and a left node (with a decrease key worth) and proper node (with a better key worth).
For instance, the primary node has the important thing 8, a left node 3, and proper node 10.
Be aware: solely works when keys are sortable, ie you’ll be able to simply test if worth is greater or decrease.
8
/
3 10
/
1 6 14
/ /
4 7 13
BSTs can get off balanced if too many values are added to just one facet, which reduces the effectiveness of the tree.
the worst case tree:
8
10
14
which principally turns into the identical as a linear sorted listing:
8 -> 10 -> 14
BSTs which might be unbalanced may be mounted with a lil little bit of pivoting, so:
8
10
14
turns into:
10
/
8 14
BSTs nonetheless aren’t good for disk based mostly storage.
– continually rebalancing requires updating disk & pointers often
– neighboring nodes is likely to be saved in several pages, that means studying a number of pages for one search
B-Timber are principally thicc binary timber.
as a substitute of every node having one key, every node can have a number of keys, and a number of plus one tips to different nodes.
[ 17 | 24 ]
/ |
[2|5] [19|20] [25|30]
/ | / | / |
[1] [3]
on this instance, every node has two keys (17 and 24), and three pointers – one to a node with keys which might be lower than 17, one to a node with keys in between 17 and 24, and one to a node with keys better than 24.
now that is usually when i might attempt to implement a B-tree in some language or the opposite. and so in fact, i made a decision to strive doing so in Factorio.
(for the uninitiated, Factorio is a manufacturing facility constructing sport)
first, a easy binary search tree.
every “node” has a wood chest that accommodates a singular kind (the important thing), after which two paths (the pointers) to different nodes.
since there’s so inherent method to evaluate the worth of various supplies, I gave them an arbitrary order (wooden, coal, stone, brick, copper, iron, metal – in that order). Every purple filter arm is comparability test. within the first node, for instance, the firs arm first checks if the merchandise is “equal to” brick, the second arm checks if the merchandise is “lower than” (ie is both wooden, coal, or stone), and the third checks if merchandise is “better than” (ie equal to copper, iron, metal).
(there’s additionally a “rubbish collector” on the prime proper, which picks up any defective objects which may have made their method to the conveyer belt.)
Creating the B-tree was barely extra sophisticated.
right here, the tree is expanded, so every node accommodates three keys, with three filter arms and three wood chests, together with 4 tips to youngster nodes. as you’ll be able to already see, the B-tree holds a-lot extra info. In simply the second stage, the BST holds 2 keys, whereas the B-tree holds 12, with that quantity rising to 48 in stage 3.
I didn’t need to manually choose and kind 48 objects in factorio, so for now I’ve left the tree empty, till i can provide you with a greater method to symbolize values.
listed below are each, facet by facet:
right here’s the yt video:
when you have any concepts on how you can enhance the manufacturing facility, pls hit me up!
<3