The Gateway to Computer Science Excellence

First time here? Checkout the FAQ!

x

+24 votes

The order of a leaf node in a B$^+$ - tree is the maximum number of (value, data record pointer) pairs it can hold. Given that the block size is $1K$ $bytes$, data record pointer is $7$ $bytes$ long, the value field is $9$ $bytes$ long and a block pointer is $6$ $bytes$ long, what is the order of the leaf node?

- $63$
- $64$
- $67$
- $68$

+42 votes

Best answer

Why did you add the value of block pointer(i.e. 6) .. B± tree leaf contain only key and record pointer?

I know the equation to calculate

n*p + (n-1)*(k+q) <= Block Size

where n=order

p= block pointer

k=key size

q=record pointer

Then why are we multiplying 6 by 1 and not by n?

n*p + (n-1)*(k+q) <= Block Size

where n=order

p= block pointer

k=key size

q=record pointer

Then why are we multiplying 6 by 1 and not by n?

@ Jhunjhunuwala

You should have a look at the structure of a leaf node of the B+ tree. It has a block pointer pointing to the next leaf node.

You should have a look at the structure of a leaf node of the B+ tree. It has a block pointer pointing to the next leaf node.

How can key be multiplied with P. If P is the order then it shud be

(P-1)*keysize + P*recordPointerSize +Bp<= block size

(P-1)*keysize + P*recordPointerSize +Bp<= block size

@ harveen singh the formula you are saying is for B tree.

The order of a leaf node in a B++ - tree is the maximum number of (value, data record pointer) pairs

it totally depends on person to person as some one can define order as max keys in any node or max block pointer in inter nal node or max(keys, block pointer) etc

but universal fact is that in any node max if max key can be stored is k then max record pointer must be one more than that,

here in this question p=data record pointer so max key can be atmost p-1

@sresta one doubt for me is

Is it because of

The order of a leaf node in a B++ - tree is the maximum number of (value, data record pointer) pairs it can hold.

Here in question it self order means max number of value, data pointer

As per question we considered it as P

But if nothing mentioned we just consider P-1 keys

Is my understanding is meaningful

Is it because of

The order of a leaf node in a B++ - tree is the maximum number of (value, data record pointer) pairs it can hold.

Here in question it self order means max number of value, data pointer

As per question we considered it as P

But if nothing mentioned we just consider P-1 keys

Is my understanding is meaningful

@student2018 is correct @srestha , even I too have same doubt as @student2018 ,

for leaf node

(p-1)(key+record PTR)+1block PTR <=blocksize

and

for other than leaf node

P.blockptr+(P-1)keys<=block PTR

for leaf node

(p-1)(key+record PTR)+1block PTR <=blocksize

and

for other than leaf node

P.blockptr+(P-1)keys<=block PTR

There was a comment I had read under on of the answer to a question here on GO stating that if it's 'K' then we have to consider 1000 and if it's 'k' we must consider 1024. Why didn't we apply the same logic here? If the option had 62 and 63 both, what could have been the solution?

@Warlock lord 1KiloByte = 1024 Bytes

1Kilogram= 1000 grams

Kilo in decimal and binary are different. Here it is binary 'Kilo'.

@junk I am aware. But in a lot of solutions in Compute Networks they have considered 1000 and not 1024 .. of course to get away with the easy calculation but this creates a confusion when to use what. And what I posted earlier was mentioned by one of the 'Boss' so I wanted to confirm.

@Warlock lord you might have seen them in bandwidth calculations. please note that when we say 1K**b**ps , it is kilo in SI units standard and we are saying 1000 bits per second. when we say 1K**B**ps , it is kilo in JEDEC units standard and it is defined to be $2^{10}$ or 1024Bytes per second.

if anyone used 1K**B**ps to be 1000**B**ps, it is wrong, but we can use to approximate the answers quickly to save time.

- All categories
- General Aptitude 1.2k
- Engineering Mathematics 4.7k
- Digital Logic 1.9k
- Programming & DS 3.5k
- Algorithms 3k
- Theory of Computation 3.7k
- Compiler Design 1.5k
- Databases 2.8k
- CO & Architecture 2.5k
- Computer Networks 2.9k
- Non GATE 837
- Others 1.2k
- Admissions 278
- Exam Queries 396
- Tier 1 Placement Questions 17
- Job Queries 50
- Projects 7

33,687 questions

40,230 answers

114,269 comments

38,799 users