proof

Question

how the b and b+ tree formulae computed can u explain with the proof

Answer 1

For B Tree, each node will contain 3 pointers - block pointer, record pointer and key pointer

Block pointer will point to the child of the B tree, Record pointer will point to the the actual data of the node and key pointer will point to the key of the actual data. All the nodes of a B-tree will have all 3 pointers.

For a k-way B-tree, there will be k pointers pointing to the child nodes(block pointer) and k-1 pointer holding the key along with the data(record pointer and key pointer)

So, any node of size N of a k-way tree will have the formula:

k*(block pointer) + k-1*(record pointer + key pointer) = N

 

For B+ tree, the internal nodes will contain only the block pointers to point to their children and key pointers to point to point to the keys. All the actual data in a B+ Tree is present on the leaf nodes so no record pointers will be there in the internal nodes. So the formula will be,

k*(block pointer) + k-1*(key pointer) = N

For any leaf node of a B+ tree, the formula will be same as that of a B-tree

Comments

For any leaf node of a B+ tree, the formula will be same as that of a B-tree

In $b^+$tree suppose leaf contains 

[(K1, pr1. K2,pr2 K3,pr3.....km ,prm) Pb]

Here k1...km are keys and pr1...prm are record pointers and Pb is block pointer pointing to next leaf node

So the farmula for it will be 

m(k+pr)+Pb= N 

Where N is size of block

Answer 2

see this ....