patternMinor
B-tree branching factor boundaries
Viewed 0 times
boundariesbranchingtreefactor
Problem
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.
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.
Solution
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.
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.
Context
StackExchange Computer Science Q#7428, answer score: 3
Revisions (0)
No revisions yet.