b-tree

BTree Visualization Tool


I want a Visualization of BTree operations to learn the operations thoroughly. I found this Website which helped me: https://www.cs.usfca.edu/~galles/visualization/BTree.html

Now I want to recreate a given BTree with this Tool but I can't figure out the right order to insert the elements. For example, in which order should I insert the elements if I wanted to recreate following BTree with this tool above?: Example BTree

My attempts lead to BTrees like this: What the tool creates

But I want the exact BTree-Structure as the first image shows.

Also, is the fact that I write order M=4 but the Website sees my Interpreation of M=4 as M=5 just a different convention?

I hope this question is not too niche.

I tried different orders of Insertion but nothing worked.


Solution

  • There are indeed different conventions for describing the size limit of B-tree nodes.

    That visualisation tool uses the concept of maximum degree. Wikipedia defines degree as "For a given node, its number of children.". For a B-tree this means a node has a number of keys that is at most one less than that degree.

    The tree you want to build has a root node with 5 children, so you should choose option "Max. Degree = 5".

    There are many ways to achieve the desired result. One is to insert the keys from low to high, but skipping a key when a leaf node has 3 keys. So enter 2 and 4, but skip 6, then continue with 10, ...etc.

    When you reach the greatest value, enter the few remaining values you have skipped. Here is the total insert sequence:

    2 4 10 15 27 33 35 38 55 62 70 79 81 87   6 74 93
    

    The result (screenshot):

    enter image description here