Questions tagged [b-tree]

The tag has no usage guidance.

8 questions with no upvoted or accepted answers
Filter by
Sorted by
Tagged with
2 votes
0 answers

Questions about the Dancing Tree data structure

I would be very grateful if someone can clarify a little bit about the Dancing tree data structure that the Reiser4 filesystem uses. It's a presentation topic that I picked, however, there seems to be ...
Huy Đỗ Nguyễn An's user avatar
2 votes
1 answer

Why does CLRS refer to the disk parts as pages rather than blocks?

I recently decided to review the B-tree chapter (chapter 18, p 486 in 3ed) in Introduction Algorithms, and found that they call pages what I always referred to as blocks or clusters: In order to ...
2xMax's user avatar
  • 121
1 vote
0 answers

Deletion in B Trees

Given a B-Tree that contains the keys $k$ and $2k$, we know the height of the tree will be reduced if we delete the key $k$. Prove or disprove: The height of the tree will also reduce if we remove $2k$...
MathCurious's user avatar
1 vote
0 answers

Is deletion and insertion easier in B+ trees compared to B trees?

I saw this question in test. It says that insertion and deletion is easier in B+ tree compared to B tree. The given reason for this was the key to be deleted must be present in leaf node in B+ tree ...
Ayush's user avatar
  • 117
1 vote
0 answers

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 ...
RajS's user avatar
  • 1,637
1 vote
0 answers

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 ...
Amit Nachimovitz's user avatar
0 votes
0 answers

minimum and maximum TOTAL keys in a B-tree

so' given a B tree of height $h$ and order $t\ge2$, i would like to know what is the formula for minimum and maximum total keys in the tree. I've stumbled upon the maximum formula: $2t^{h+1}-1$ cant ...
WalaWizon's user avatar
0 votes
1 answer

Enhance B-Tree with find(k) function

I have a question to enhance a B-Tree and add a function called find(k) which gets a key - k and returns the index of it in the sorted keys of the tree, using $O(N)$ space complexity, and it needs to ...
CSch of x's user avatar