How to effectively build a B + tree from this list?

Question

I want to build a B + tree from a given list of unordered elements of size N

I know that the optimal border for this is Θ(N / B * logM / B(N / B)) block transfers, which is also optimal for sorting; therefore, I can’t just select an element and make an insert in the tree individually, since it will give me the O(N logB(N)) block transfer.

So, I decided that the best way to build a tree is to sort the elements first, since the leaves are ordered anyway. Because of this, I am at a loss.

I thought of something like this:

• Take items B from the list.
• Write them like they are somewhere (this is a sheet of three)
• Take the last element of the block (the largest); this will be the routing key for the sheet parent
• Repeat step 1 for the following items until there are no B-1 routing keys in the parent key.
• When there are routing keys B-1 in the parent, it means that it is full. Thus, a new routing key will go instead of "grandfather" (therefore, the tree grows one level), and all new leaves will have a new parent
• Continue driving until the N/B tags are read.

Basically, the problem is that I am not considering the minimum number of children that an internal node can have. This may happen, for example, that a node ends with only one child, which is clearly wrong.

I looked everywhere but couldn't find an algorithm that actually explains how to build a tree in Θ(N / B * logM / B(N / B)) . All I find are algorithms with simple tree inserts for each item in the list without using coefficient B.

Can you help me, maybe point me in the right direction?

Answer 1

Instead of creating all levels at the same time, which can use more than a constant number of RAM blocks, I think that I would build levels from the very beginning to the very extreme (that is, first with a width, not with depth). Given the list, greedily cut it into blocks of size B. If there is only one block, then this is the root. Otherwise, if there are too few elements in the last block, then it is necessary to balance its elements with the elements of the second last block as evenly as possible; both will now have enough elements. The following list consists of the last element in each block of this level.