As of May 31, 2023, we have updated our Code of Conduct.

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
56 views

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
80 views

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
25 views

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
946 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 ...
RajS's user avatar
  • 1,607
1 vote
0 answers
391 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 ...
Amit Nachimovitz's user avatar
0 votes
0 answers
31 views

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
0 answers
39 views

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
0 votes
1 answer
76 views

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