# Questions tagged [b-tree]

The tag has no usage guidance.

24 questions
Filter by
Sorted by
Tagged with
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 ...
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 ...
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$...
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$ ...
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 ...
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 ...
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 ...
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. ...
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? ...
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 ...
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 ...
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 ...
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 ...
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, ...