Hot answers tagged

5 votes

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 ...
Mr. Tao's user avatar
  • 163
4 votes

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: ...
Pseudonym's user avatar
  • 22k
4 votes

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 ...
Russel's user avatar
  • 2,735
3 votes
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 ...
Matthew Towers's user avatar
3 votes

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 ...
Pseudonym's user avatar
  • 22k
3 votes
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 ...
Lorenzo Tagliabue's user avatar
2 votes

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. ...
h8pathak's user avatar
  • 129
2 votes
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 ...
John Leidegren's user avatar
2 votes

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 ...
Pseudonym's user avatar
  • 22k
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 ...
Kenneth Kho's user avatar
1 vote

Confusion about B-Tree

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 ...
Nathaniel's user avatar
  • 13.9k
1 vote
Accepted

What order B-tree is this?

Good question. You have given the answer. A B-tree of order $4$ can also be a B-tree of order $5$ or $6$. So, "the order" of a B-tree may not be unique. Knuth, who gave the definition of B-...
John L.'s user avatar
  • 38.8k
1 vote

Do nodes represented as NIL contribute to the height of a 2-3-4 tree?

Citing from the Wikipedia article on B-tree Every node (leaf or internal) is a 2-node, 3-node or a 4-node, and holds one, two, or three data elements, respectively. Thus, since the squares in the ...
catalyst's user avatar
1 vote
Accepted

What does it mean that B-tree leaves carry no information?

So according to CLRS (quotations): Any "satellite information" associated with a key is stored in the same node as the key Leaf nodes have no children, so their ci fields [pointers to child ...
Nimrod Yonatan Ben-Nes's user avatar
1 vote

Databases and B-Trees: What are Keys and how are they related

There's an indeed a relation that maps the database keys to the B-trees keys $K_d \mapsto K_b, K_b \in \mathbb{Z}$ The B-Tree keys are not random though, they represent the physical location of data ...
Koenig Lear's user avatar
1 vote
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 $$
Sab's user avatar
  • 121
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 (...
Pseudonym's user avatar
  • 22k
1 vote

What is the minimal degree $d$ required for a B tree with $44*10^6 $ keys so that it's height is less than or equal to $5$

Having degree $d$ tree has $1$, $d$, $d^2$, $d^3$, $d^4$ nodes per level. So, we must have that: $$1+d+d^2+d^3+d^4 \ge 44\ 000\ 000$$ Let's consider just $d^4 = 44\ 000\ 000$. This has solution $d\...
Yola's user avatar
  • 169
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, ...
John Leidegren's user avatar
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 ...
John Leidegren's user avatar
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(...
Rahul's user avatar
  • 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 ...
D.W.'s user avatar
  • 158k
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 ...
Ritwik's user avatar
  • 205

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