b-trees in factorio

learning about B-Trees...in factorio

i've been reading Database Internals with a book club, and this week was chapter 2, about B-Trees.

but first, binary search trees

Each node contains a key, and a left node (with a lower key value) and right node (with a higher key value).

For example, the first node has the key 8, a left node 3, and right node 10.

Note: only works when keys are sortable, ie you can easily check if value is higher or lower.

        8       
       / \      
      3   10     
     / \    \    
    1   6    14       
       / \   /       
      4   7 13

BSTs can get off balanced if too many values are added to only one side, which reduces the effectiveness of the tree.

the worst case tree:

    8     
      \
      10
        \
         14

which basically becomes the same as a linear sorted list:

8 -> 10 -> 14

BSTs that are unbalanced can be fixed with a lil bit of pivoting, so:

    8     
      \
      10
        \
         14

becomes:     
  10   
 /  \  
8    14

BSTs however are not good for disk based storage.

- constantly rebalancing requires updating disk & pointers frequently

- neighboring nodes might be stored in different pages, meaning reading multiple pages for one search

B-Trees are basically thicc binary trees.

instead of each node having one key, each node can have multiple keys, and multiple plus one pointers to other nodes.

           [ 17 | 24 ]         
         /      |       \      
      [2|5]  [19|20]  [25|30]     
     /  |  \ /  |   \ /  |  \       
   [1] [3]   

in this example, each node has two keys (17 and 24), and three pointers - one to a node with keys that are less than 17, one to a node with keys in between 17 and 24, and one to a node with keys greater than 24.

---

now this is normally when i would try to implement a B-tree in some language or the other. and so of course, i decided to try doing so in Factorio.

(for the uninitiated, Factorio is a factory building game)

first, a simple binary search tree.

each “node” has a wooden chest that contains a singular type (the key), and then two paths (the pointers) to other nodes.

since there’s so inherent way to compare the value of different materials, I gave them an arbitrary order (wood, coal, stone, brick, copper, iron, steel - in that order). Each purple filter arm is comparison check. in the first node, for example, the firs arm first checks if the item is “equal to” brick, the second arm checks if the item is “less than” (ie is either wood, coal, or stone), and the third checks if item is “greater than” (ie equal to copper, iron, steel).

(there’s also a “garbage collector” at the top right, which picks up any faulty items that might have made their way to the conveyer belt.)

Creating the B-tree was slightly more complicated.

here, the tree is expanded, so each node contains three keys, with three filter arms and three wooden chests, along with four pointers to child nodes. as you can already see, the B-tree holds a-lot more information. In just the second level, the BST holds 2 keys, while the B-tree holds 12, with that number increasing to 48 in level 3.

I didn’t want to manually pick and sort 48 items in factorio, so for now I’ve left the tree empty, until i can come up with a better way to represent values.

here are both, side by side:

here’s the yt video:

if you have any ideas on how to improve the factory, pls hit me up!

<3