4
$\begingroup$

A BTree has a $k$ value that determines that every node has $k$ to $2k$ children. When a node has $2k$ keys it needs to be split into two nodes.

Let's say I want to create a $k/(2k-x)$ tree. (like a 2-3 tree that follows the BTree rules, but isnt $k/2k$)

What is the possible range of $x$? The tree must follow the behavior of a BTree, meaning it needs to hold keys and split accordingly.

$\endgroup$

1 Answer 1

3
$\begingroup$

More exactly, a B tree has an $m$ value such that the number of children is between $\lceil\frac m2\rceil$ and $m$ children. That differs from your numbers for odd $m$. For $m=3$ the bounds are $2$ and $3$, which is the 2-3-tree you refer to.

As far as I know (I tried this several years ago) these numbers are the smallest interval for which the split and merge operations can work. You can try yourself. If a node has $m$ children, I can add $1$ and the node must be halved. Thus this satisfy the $\lceil\frac m2\rceil$ bound? Check for $m$ odd and even separately.

$\endgroup$

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.