# Tag Info

### Are degree and order the same thing when referring to a B-Tree?

I have seen three ways to characterize B-tree so far: With degree of the B-tree $t$ (either minimum, as in CLRS Algorithms book, or maximum as in B-tree Visualizer). The simplest B-tree occurs ...
• 163

### How do XFast and Y Fast Tries compare to B trees in performance?

On top of the other answer, the reason why any data structure tends to be preferred by databases over any other data structure (e.g. B+-trees over anything else) usually boils down to two factors: ...
• 22.1k

### How do XFast and Y Fast Tries compare to B trees in performance?

Apart from their more complex structure, Y-fast and X-fast trie assumes that data to be stored are integers, while balanced BSTs only assumes that data be from some ordered universe, not necessarily ...
• 2,745
Accepted

### How B Tree guarantees self balancing property?

That's not how insertion into a full B-tree works. You can read about this in detail in CLRS chapter 18, section 18.2. In brief, when you want to insert you start at the root and work your way down ...

### Why is it that Btrees most of the times have a degree that is odd? What happens if they are even?

One thing that distinguishes real-world B-trees from "lecture B-trees" is that real B-trees tend to have nodes and leaves where the size in bytes is fixed. So the "degree" of a B-tree is determined by ...
• 22.1k
Accepted

### How many node does the final B-tree have?

Every node contains between $\lceil(m/2)\rceil-1$ and $m-1$ keys (where m is the degree), so we can say that every node has between $\lceil(m/2)\rceil$ and $m$ children. If we imagine to construct a ...

### Are degree and order the same thing when referring to a B-Tree?

Degree represents the lower bound on the number of children a node in the B Tree can have (except for the root). i.e the minimum number of children possible. ...
• 129
Accepted

### Why is it that Btrees most of the times have a degree that is odd? What happens if they are even?

I don't think there's a right answer to this but you could argue for a preference either way. Let's define B-tree order m like this max children/values ...

### How to delete an element from a B-tree

B-tree deletion tends to be explained very badly in most textbooks, because the algorithm has one particular case which is complicated. When inserting a leaf element in a B-tree, if a node becomes ...
• 22.1k
Accepted

### Max no. of keys of B-Tree of height h

Found it (using geometric serie for the sum) $$\sum_{i=0}^h (2t)^i(2t-1) = (2t-1) \sum_{i=0}^h (2t)^i = (2t-1) \frac{(2t^{h+1}-1)}{(2t-1)} = (2t)^{h+1}-1$$
• 141
1 vote
Accepted

### How to decide between pre-emptive split or non pre-emptive split and pre-emptive or non pre-emptive merge for a BTree?

The reason it is not debated is because it is obvious, the reason that B-tree was invented, and subsequently B* tree is to reduce the frequency of rebalancing. Splitting and merging both involve ...
• 656
1 vote
Accepted

### Splitting a node in B+ tree with odd number of keys

There is no advantage to choosing one over the other. "Real" B+-tree implementations will often rebalance if they can, rather than splitting. When a node becomes overfull, if there is a sibling (...
• 22.1k
1 vote

• 649
1 vote

### Doubt regarding deletion from a B-tree

Because it keeps the B-tree balanced? In essence, what you are asking is why the algorithm is the way it is. The algorithm we use has been around long enough that if there was a better way to do it, ...
1 vote
Accepted

### Deletion of record from B+ tree

Yes and yes. Any key that doesn't mess up the sort order can be used. Typically (in my experience), this is the minimum value from the right subtree. However, I'm not aware of any specific scenario ...
1 vote

### Understanding B tree key deletion step from CLRS algorithm

You are probably overthinking it by thinking in terms of predecessor/successor nodes. The rule just says, if the key to be deleted has both children at least capacity, you cannot take a predecessor(...
• 51
1 vote

### return a key of a node with maximum value within a range of keys in B+ tree

Augment each node to contain the key of the node with maximum value, among all nodes that are underneath it (among all of its descendants). You can easily maintain/update this augmented information ...
• 159k
1 vote

### Are degree and order the same thing when referring to a B-Tree?

B-trees terminologies are not uniformly defined wherever I read, however the ambiguous question is what is the order of a B-Tree? and not much about degree of a B-Tree. Degree comes from the graph ...
• 205

Only top scored, non community-wiki answers of a minimum length are eligible