Questions tagged [b-tree]

The tag has no usage guidance.

Filter by
Sorted by
Tagged with
0
votes
0answers
17 views

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

I was watching a lecture video and the Professor states that it would be very rare to see the order of a Btree to be even. I was hoping for an explanation but he cut it off there and moved on with the ...
0
votes
1answer
92 views

How to delete an element from a B-tree

There is a lot of information online on this specific topic, but I still don't quite understand how to delete elements from a B-tree. For example, given the following tree, how would we delete 26 and ...
1
vote
0answers
59 views

Calculating maximum number of splits that can occur during insertion of $n$ keys in B Tree of order $m$

I can calculate this by trying out manually inserting $n$ keys in $m$ order B Tree as follows: Assume median to be selected for split be left biased. That is $m/2$. For example, if $m=4$, then a ...
0
votes
0answers
107 views

Where can I find the algorithm in pseudocode for deleting a key from a B-Tree?

I am reading the chapter on B-Trees in Introduction to Algorithms (3rd edition) by Cormen and found the deletion procedure very confusing. I could understand the algorithm for insertion because it ...
1
vote
0answers
173 views

Maximum node splits in B-tree in terms of insertions and branching order

Is there any algorithm to calculate maximum number of node splits that can occur in given number of insertions and highest branching order? Lets say I want to insert 10 elements to an empty B-tree ...
0
votes
0answers
180 views

Time complexity of inorder run on B+ tree (without leavesa link)

I quite sure that it should be $O(n)$, but I didn't found any information about it and I'm not sure how to prove it. Maybe in 2-3 tree the max number of node (include the leaves) is $2n$ and in each ...
0
votes
0answers
19 views

Doubt regarding deletion from a B-tree

After deleting an element from a B-tree,I could rearrange the tree in several ways,that would still complies to the rules of B-trees.But,we are supposed to follow a certain set of rules for ...
1
vote
0answers
258 views

Deletion of record from B+ tree

I was going through the B+ tree deletion operation from the book Database System Concepts, 6th Edition by Henry F. Korth. One particular thing caught my attention. A B+ tree is given. We have to ...
0
votes
1answer
2k views

How many node does the final B-tree have?

I'm currently studying the B-Trees chapter of Introduction to Algorithms. One of the question from the chapter is: Suppose that we insert the keys $\{1,2,...,n\}$ into an empty B-tree with minimum ...
1
vote
1answer
129 views

Understanding B tree key deletion step from CLRS algorithm

CLRS explains B tree key deletion as follows: If the key $k$ is in node $x$ and $x$ is a leaf, delete the key $k$ from $x$. If the key $k$ is in node $x$ and $x$ is an internal node, do the ...
0
votes
1answer
286 views

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

I've been asked a question about B+ Tree. The question is: Suppose we have object of the following type: ...