Questions tagged [b-tree]
The b-tree tag has no usage guidance.
8
questions with no upvoted or accepted answers
2
votes
0
answers
69
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 ...
2
votes
1
answer
96
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 ...
- 121
1
vote
0
answers
45
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$...
- 231
1
vote
0
answers
38
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 ...
- 117
1
vote
0
answers
1k
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 ...
- 1,637
1
vote
0
answers
459
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
0
answers
93
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 ...
0
votes
1
answer
107
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 ...
