Computer Science Stack Exchange is a question and answer site for students, researchers and practitioners of computer science. It's 100% free, no registration required.

Sign up
Here's how it works:
  1. Anybody can ask a question
  2. Anybody can answer
  3. The best answers are voted up and rise to the top

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.

share|cite|improve this question

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.

share|cite|improve this answer

Your Answer


By posting your answer, you agree to the privacy policy and terms of service.

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