# Questions tagged [b-tree]

The tag has no usage guidance.

26 questions
Filter by
Sorted by
Tagged with
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 ...
104 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 ...
96 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 ...
89 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 ...
68 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 ...
100 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 ...
1 vote
146 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-...
61k 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 ...
193 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 ...
1k 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
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 ...
1 vote
44 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$...
1 vote
120 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 ...
1 vote
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 ...