Questions tagged [b-tree]
The b-tree tag has no usage guidance.
26
questions
0
votes
0
answers
21
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 ...
- 11
3
votes
2
answers
81
views
How do XFast and Y Fast Tries compare to B trees in performance?
I learned that Y fast tries support amortized loglog(u) time insertions , deletions. and loglog(u) time membership, successor and predecessor operations with O(n) space. So when n is closer to U in ...
- 113
2
votes
0
answers
50
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 ...
0
votes
1
answer
29
views
Confusion about B-Tree
In a B-Tree, one of the rules is:
Every node (except the root) is at least half full
But then, in a 4-way B-Tree, we have the following case. Suppose we want to insert $10,20,30,40$ to the tree.
After ...
- 111
1
vote
1
answer
52
views
What order B-tree is this?
I am studying B-trees and reading Introduction to Algorithms by Cormen et al.
Unfortunately, they have this diagram Figure 18.1 and they do not list the order of the tree.
I understand that for a B-...
- 135
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$...
- 221
1
vote
1
answer
71
views
How B Tree guarantees self balancing property?
Let's say we have a b tree of order 4 and it has 3 levels. All nodes are completely filled. Now if we want to insert a key with maximum value ( than all keys present in the tree). For this, we have to ...
- 195
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 ...
- 121
0
votes
1
answer
181
views
Do nodes represented as NIL contribute to the height of a 2-3-4 tree?
Does the following 2-3-4 tree have a height of 3 or 2?
If I count from the external nodes i.e. the ones with the square boxes then height should be 3.
Not sure if they are to be included in the ...
- 23
3
votes
1
answer
204
views
What does it mean that B-tree leaves carry no information?
According to Wikipedia B-tree page, Knuth's definition fifth property is "All leaves appear in the same level and carry no information.".
What does it mean that they carry no information?
...
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 ...
- 117
0
votes
1
answer
99
views
Databases and B-Trees: What are Keys and how are they related
I confused about the description & definition of "key" occuring as terminology for databases and b-trees.
In first case dealing with theory of databases a key is defined as a choice for ...
- 213
0
votes
1
answer
69
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 ...
1
vote
1
answer
5k
views
Max no. of keys of B-Tree of height h
I am reading about B-Tree through CLRS. One of the exercise problem is to express maximum number of keys in a BTree of height $h$ and minimum degree $t$.
Properties of BTree of $t$:
$t\ge 2$
Min. no ...
- 121
1
vote
1
answer
776
views
Splitting a node in B+ tree with odd number of keys
This and several other resources suggest to "Always a node that gets the middle key from bottom splits, should drop one item for a new middle key".
To illustrate with an example.
For 5-way B+-tree,
...
- 113
1
vote
1
answer
310
views
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$
What is the minimal degree $d$ required so a B - tree with $44*10^6$ keys will have a height $h$, such that $h\leq 5$
My attempt was to build the tallest tree possible with minimum degree $d$ and $n =...
- 317
1
vote
2
answers
475
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 ...
- 127
0
votes
2
answers
651
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 ...
- 115
1
vote
0
answers
911
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,587
1
vote
0
answers
381
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
1
answer
37
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
1
answer
619
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 ...
- 217
1
vote
1
answer
6k
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 ...
user83753
1
vote
1
answer
558
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 ...
- 1,745
0
votes
1
answer
621
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:
...
- 135
8
votes
7
answers
59k
views
Are degree and order the same thing when referring to a B-Tree?
I know the term order of a B-tree. Recently I heard a new term: B tree with minimum degree of 2.
We know that the degree is related to a node but what is the degree of a tree?
Does degree impose any ...
- 359