The Gateway to Computer Science Excellence

+4 votes

Best answer

0

**Now for the leaf node **

minimum keys =(ceil of (p/2))

I Think It should be

**minimum keys =(ceil of (p/2)-1).**

Because while doing questions of deletion in B+ trees the underflow condition is checked using this formula only. **If the keys are less than (ceil of (p/2)-1) then underflow .**

0

here the order of leaf node is 4

so Ceil (4/2)=2

so the minimum no of keys in the leaf node is 2

and after deleting it become 1

so now they have to merge these with sibling

**now according to you**

If the keys are less than (ceil of (p/2)-1) then underflow .

ceil(4/2)-1=1

so **If the keys are less than 1 then underflow**

**that is wrong **

**right one is minimum key can be 2**

https://classes.engineering.wustl.edu/cse530/notes/CSE530A-23-B+-Trees.pdf

for good image you can go to page 25 of the link

0

**more information**

For a 𝑏 order B+ tree (max of 𝑏 children per node)

– Find, insert, and delete are all $O(log_{b}N)$

– Space is 𝑂 (n)

– Range queries can be done in $O(log_{b}N+K)$ for a range of 𝑘

• Range queries are queries that ask for all elements between two values – Elements in a range are already in order

+1 vote

Order for leaf node in B+ tree= **Block pointer + order of leaf node(record pointer + key )<= block size**

Order for non leaf node in B+ tree= **order * index pointer + (order-1)*keysize<=block size**

In the b+ tree there is no record pointer in internal node there is record pointer present at only leaf node so here n-1 i think it may help you.

- All categories
- General Aptitude 1.9k
- Engineering Mathematics 7.5k
- Digital Logic 2.9k
- Programming and DS 4.9k
- Algorithms 4.4k
- Theory of Computation 6.2k
- Compiler Design 2.1k
- Databases 4.1k
- CO and Architecture 3.4k
- Computer Networks 4.2k
- Non GATE 1.4k
- Others 1.4k
- Admissions 595
- Exam Queries 573
- Tier 1 Placement Questions 23
- Job Queries 72
- Projects 18

50,737 questions

57,357 answers

198,483 comments

105,254 users