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?:

My attempts lead to BTrees like this:

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):

- How is the insert operation in a B-Tree O(log n), should it not be O( log 2d -1 ) where d is the degree of the B-Tree
- Is there a correlation between Index INLINE_SIZE and Index Column Data(String Type) in Apache Ignite?
- Oracle index use b-tree or b+tree by default?
- Make a B+ Tree concurrent thread safe
- Understanding Disk Reads and Cache Misses for B-tree and BST Queries
- Advantage of B+ trees over BSTs?
- B-tree insertion problem, error: vector subscript out of range
- Rust BTreeSet insert unique values with duplicate ranking field
- Order of B+ Tree
- Why do some btree diagrams have multiple nodes at the same level?
- Is there a B-Tree Database or framework in Python?
- Is innoDB clustered index always bigger than data size?
- C# generic B+tree
- Conditional index and trigger in postgres
- Keeping an AVL tree balanced without rotations
- How is B tree created in Mongo DB
- Is there a way to evaluate the number of leaves needed by a B+ tree?
- How much do B-trees reduce disk accesses?
- BTree Visualization Tool
- How to delete a key from a B+ Tree such that this key exist in an internal node and has another copy from it in a leaf node?
- Write a formula which calculates the number of elements in B tree root after every i-th insertion
- B+ Tree order of 1 & 2
- What is satellite information in data structures?
- How to lay out B-Tree data on disk?
- What are the differences between B-tree and B*-tree, except the requirement for fullness?
- Suggest an algorithm to traverse a B+ tree
- What is the time complexity of MySql SELECT to find an interval that contains a number?
- Why are skip lists not preferred over B+-trees for databases?
- Lower bound from the right in a B-tree
- Tree data structure