Questions tagged [b-tree]

The tag has no usage guidance.

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

Merging two B trees in O(h)

Given two B - trees A, B (from order of m) such thats: for each a in A and b in B: a > b and also the number of elements in A is larger than the number of elements in B. How can I merge them into ...
0
votes
0answers
10 views

Full analyses of the number of nodes/keys and height of B-Trees

If I'm given a tree with "$k$" keys, or "$n$" nodes and I need to find the minimal / maximal height of the tree, I know that I have to split it into two cases: $i$. The tree is ...
0
votes
0answers
24 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$...
0
votes
0answers
10 views

$B-Trees$ $fuse$ and $split$ mechanics

I would like to do an amortized analysis on general $B-Trees$, i.e. any $a$ and $b$ with $a \geq 2$ and $b \geq 2a$. For this, I am kind of stuck at the following mechanic: Let's say we have a $a=3$ ...
1
vote
1answer
36 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 ...
2
votes
1answer
49 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 ...
0
votes
0answers
34 views

Number of order 4 B-trees possible with 6 distinct keys

To avoid any confusion the order of B tree is the maximum number of children it can have. Suppose we create a B tree of order 4 by inserting 6 distinct keys (1, 2, 3, 4, 5, 6) in any permutation, how ...
0
votes
1answer
66 views

Height of a 2-3-4 tree

Consider the following 2-3-4 tree. Does this have a height of 3 or 2 ? Code for searching a min heap If I count from the external nodes ie. the ones with the square boxes then height should be 3. ...
2
votes
1answer
118 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
0answers
21 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 ...
0
votes
1answer
93 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 ...
0
votes
1answer
41 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
1answer
2k 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 ...
1
vote
1answer
396 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, ...
1
vote
1answer
193 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 =...
1
vote
2answers
212 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
2answers
363 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
452 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
vote
0answers
289 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
1answer
35 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
1answer
480 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 ...
1
vote
1answer
5k 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
451 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
447 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: ...