0
$\begingroup$

In a B-Tree, one of the rules is:

Every node (except the root) is at least half full

But then, in a 4-way B-Tree, we have the following case. Suppose we want to insert $10,20,30,40$ to the tree.

After inserting the 3 first element we get the following root:

  [10  20  30]

After adding the 40, we split as follows:

        [30]
[10 20]       [40]

For a node to be half full in a m-way B-Tree there must be in that node $\lceil \frac{m}{2} \rceil$ elements. So there must be 2 elements in every node, but the node $[40]$ clearly breaks this rule! So why is this allowed and what should we do?

B-Tree is seriously confusing me and i couldn't find any answers online.

Improve this question
$\endgroup$
1
  • $\begingroup$ Why would you split when adding $40$ ? $\endgroup$
    – user16034
    Commented Nov 17, 2022 at 8:19

1 Answer 1

Reset to default
1
$\begingroup$

According to wikipedia, the condition of being half-full only applies on internal nodes, and it concerns the number of children, not the number of keys (which is always one less than the number of children, except for leaves).

In your example, the node [40] is a leaf, therefore the half-full property does not apply.

Improve this answer
$\endgroup$
5
  • $\begingroup$ What do you mean by the number of children and not the number of keys? Does it mean that in a node there's no minimum on how many keys (elements) must be in it? Like it is legal for any node to have any number of elements ranging from 1 to m-1? $\endgroup$
    – Denis
    Commented Nov 16, 2022 at 22:22
  • 1
    $\begingroup$ @ShinobiSan As I said, the number of keys is always one less than the number of children, so no, you do not have complete freedom. $\endgroup$
    – Nathaniel
    Commented Nov 16, 2022 at 22:24
  • $\begingroup$ You mean the maximum number of keys that a node can contain is one less than the number of children, but how about the minimum? $\endgroup$
    – Denis
    Commented Nov 16, 2022 at 22:26
  • 1
    $\begingroup$ No, I mean that if $k$ is the number of children of a node, then the EXACT number of keys that node contains is ALWAYS $k-1$. Not any more or any less. $\endgroup$
    – Nathaniel
    Commented Nov 16, 2022 at 22:37
  • $\begingroup$ Please at least read the wikipedia article, it is well done so you will learn things about B-trees. $\endgroup$
    – Nathaniel
    Commented Nov 16, 2022 at 22:38

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service and acknowledge you have read our privacy policy.

Not the answer you're looking for? Browse other questions tagged or ask your own question.