Questions tagged [b-tree]

The tag has no usage guidance.

Filter by
Sorted by
Tagged with
1 vote
1 answer
29 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-...
user avatar
0 votes
0 answers
58 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 ...
user avatar
0 votes
0 answers
24 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 ...
user avatar
0 votes
0 answers
32 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$...
user avatar
1 vote
1 answer
53 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 ...
user avatar
2 votes
1 answer
70 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 ...
user avatar
  • 121
0 votes
1 answer
146 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 ...
user avatar
3 votes
1 answer
162 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? ...
user avatar
1 vote
0 answers
24 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 ...
user avatar
  • 107
0 votes
1 answer
95 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 ...
user avatar
0 votes
1 answer
50 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 ...
user avatar
  • 125
1 vote
1 answer
3k 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 ...
user avatar
  • 121
1 vote
1 answer
589 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, ...
user avatar
  • 113
1 vote
1 answer
268 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 =...
user avatar
  • 317
1 vote
2 answers
360 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 ...
user avatar
  • 127
0 votes
2 answers
499 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 ...
user avatar
  • 115
1 vote
0 answers
700 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 ...
user avatar
  • 1,547
1 vote
0 answers
330 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 ...
user avatar
0 votes
1 answer
36 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 ...
user avatar
1 vote
1 answer
562 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 ...
user avatar
  • 217
1 vote
1 answer
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 ...
user avatar
1 vote
1 answer
504 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 ...
user avatar
  • 1,695
0 votes
1 answer
564 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: ...
user avatar
  • 135
8 votes
7 answers
57k 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 ...
user avatar