# Questions tagged [b-tree]

The tag has no usage guidance.

27 questions
Filter by
Sorted by
Tagged with
1 vote
77 views

### How to decide between pre-emptive split or non pre-emptive split and pre-emptive or non pre-emptive merge for a BTree?

I am trying to implement a BTree. As far as I understand the lower the height of the Tree the faster the search (This could be wrong, please correct me if it is). Is pre-emptive split with non-pre-...
111 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 ...
106 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 ...
• 123
79 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 ...
113 views

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
185 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-...
1 vote
48 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
149 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 ...
98 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
199 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 ...
258 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
46 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
116 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 ...
• 223
112 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
6k 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
1k 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
355 views

• 1,745