Questions tagged [b-tree]

The tag has no usage guidance.

12 questions with no upvoted or accepted answers
Filter by
Sorted by
Tagged with
1
vote
1answer
51 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
0answers
145 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
224 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 ...
1
vote
1answer
298 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
0answers
9 views

Inserting numbers into B-Tree

I need to insert these numbers from left to right into a B-Tree where $t=2$ Am I right? I am not sure as $t=2$ means you can hold at most 3 keys per node, and here I have only 2. I used this site: ...
0
votes
0answers
15 views

Finding minimal degree for a B-Tree

We are given 44,000,000 elements. We want to store them in a B-Tree so that his height is 5 (no more than 5). We are asked: "What is the minimal t we can choose?" ($t$ is the minimal degree, in ...
0
votes
1answer
22 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 ...
0
votes
0answers
8 views

Minimal t needed in B tree for the lowest reading time

I've got an assignment, which I was asked to calculate the minimal t needed in a B tree, to have the optimal searching time. So here it is: We've been told that in a specific B tree, with unknown t, ...
0
votes
0answers
17 views

Why do b*trees partition 2 nodes into 3?

I'm writing a b*tree library in Rust. I'm thinking it might be better to make the purposeful decision to only implement half of the b* optimizations. (And not because it is easier, although it is.) ...
0
votes
0answers
16 views

In the right-rotation case for red-black trees, there is a less efficient way to recolor it, why is it not O(log(n)) anymore?

So the first time I tried to recolor this insertion case from memory, I ended up with the right-hand side recoloring; of course the left recoloring is more efficient as the loop ends at this point. If ...
0
votes
1answer
138 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 ...
0
votes
0answers
253 views

Time complexity of inorder run on B+ tree (without leavesa link)

I quite sure that it should be $O(n)$, but I didn't found any information about it and I'm not sure how to prove it. Maybe in 2-3 tree the max number of node (include the leaves) is $2n$ and in each ...