b-tree# Write a formula which calculates the number of elements in B tree root after every i-th insertion

Insert 1,2,..,20 numbers to the empty B tree sequentially. Write a formula which calculates the number of elements in B tree root after every i-th insertion. The first part I did, but I'm having trouble in the second part.

Here's what I did.

Let N be the maximum number of elements in the root of the B-tree.
If i ≤ N, the formula is: `R(i) = i`

.
If N < i ≤ 2N, the formula is: `R(i) = N`

.
If 2N < i ≤ 3N, the formula is: `R(i) = N + 1`

and so on.
But by checking against the answer key, it seems I've done something wrong. Can you revise my solution and correct if it's wrong?

Solution

There are different insertion algorithms for B-trees, and the results you are looking for depend on them. I will here assume there is no pre-emptive splitting, and when a node is full there is no attempt to delay splitting by moving keys to sibling nodes.

Let's look at your statements:

If i ≤ N, the formula is:

`R(i) = i`

.

Correct.

If N < i ≤ 2N, the formula is: R(i) = N.

Not correct. When 𝑁+1 is inserted, the root node splits into two nodes with each 𝑁/2 keys, and one value is pushed up to become the only key in a new root node. So at that time `R(𝑁+1) = 1`

. For example, if 𝑁=4, then before inserting 5 we have:

```
root:
┌───┬───┬───┬───┐
│ 1 │ 2 │ 3 │ 4 │
└───┴───┴───┴───┘
```

Then after adding 5, we get:

```
root:
┌───┬───┬───┬───┐
│ 3 │ - │ - │ - │
├───┼───┴───┴───┘
┌─────┘ └─────────┐
┌───┬─┴─┬───┬───┐ ┌───┬─┴─┬───┬───┐
│ 1 │ 2 │ - │ - │ │ 4 │ 5 │ - │ - │
└───┴───┴───┴───┘ └───┴───┴───┴───┘
```

If 2N < i ≤ 3N, the formula is:

`R(i) = N + 1`

That should have raised an alarm: a node could never have more than 𝑁 elements, so obviously 𝑁+1 is wrong.

After the tree has received its second level (so when 𝑁+1 has been inserted), there is a sequence where the left side leaf node is filled, splits into two, adding one key in the root, and again the left side leaf node is filled, ...etc. At a certain moment the root gets full and splits into two, to get a tree with 3 levels and only one key in the root.

You may want to draw this on paper and see the logic.

- 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