844 views

2 Answers

Best answer
2 votes
2 votes

suppose MODI goverment asked the family planning commission of india to put limit on having child's (due to rise in the population). assume the planning commssion announced
that a family can have maximum  'N' child.. (it does not means that every1 should have 'N' child's they can have less also //rules for that r mentioned below)now they also posted a 

ban that there must  be a gap of 1 year between every child(having twin childs & tetra(3) packs are strictly banned ).  

child1 gap1 child2 gap2 child3 gap3 child4


            CONSIDER N= 4  to have four child their must be 3 gaps of 1-1-1 year
They also mentioned some rules for various persons that how many childrens they can have..
1) head of family(assume head as 1st person on earth & it should be female ) can have minimum 2 child's and maximum 'N'(i.e   4 child's as we considered N=4)  
2) successors(children' s of head)  can have minimum ceil  N/2(i.e ceil  4/2 = 2)  & maximum N (i.e   4 child's )
3)tail enders(last generation of head) decided they don't want to marry they want to acquire celibacy(bramcharya)....so they don't have any child's

now the time between the two child's  of 1 year also called here GAP...in that gap  family decided to donate money(may be they want 2 thank god  for giving them child) 
they have deposited the money in the  bank ...the money is saved in box  as bundels of 100 rs..then 500 ...then 1000 etc....(order is important )
now in gaps family provides the INFORMATION of first bundulls of notes in the box (here 100) and also the PATH to them...so that they can access...if they can access 100 rupee.....note then they can also access 500 rupee note...etc sequentially..in same box


now rules for having information and path ....
note:-any node  can  have  path///
1) head of family can have minimum one information &  0 PATH and maximum N-1 information and N-1 path 
2) successors can have minimum ceil N/2-1 (i.e 4/2-1=1) & 0 path  and  maximum N-1 information  & N-1 Path
3)tail enders  can have minimum ceil (m-1)/2 (i.e (4-1)/2=1.5=>2) information & 0 path & maximim N-1 path N-1 information

child1 info, path child2 info2,path2 child3 info3,path3 child4

one more rule tail enders should be at same level....
now consider b-tree  

here 'N' is the order*(max child)of b-tree the & it will be given in question...as planning commission fixed the number child a family can have i.e 'N'

1) ROOT whch is earlier called (head) can have minimum 2 child's and maximum 'N'(i.e   4 child's as we considered N=4)  
2)INTErNAL NODES  which is earlier successors(children' s of head)  can have minimum ceil  N/2(i.e ceil  4/2 = 2)  & maximum N (i.e   4 child's )
3)LEAF NODES tail enders(last generation of head)  zero child's 
INFORAMTION= KEYS ....PATH== DATA RECORD POINTERS ////keys & data record pointers are different 

         

child1 key1,record pointe1 child2  key2,recordpointer    child3  key3,recordpointer4   child4

anybody can  give path/// means anybody can have record data pointers...it does not means every should have record pointers..

money stored in the bank  is same  data stored in memory.. and saved box is as same record saved in blocks ...100 rs notes is same as the first record of the block which is considered as KEY in the b-tree ...and sequentially they can access next record..of same block....

.one thing must be noted here 
1) ROOT (head)  can have minimum one KEY (INFORMATION)  and zero (DATA RECORD POINTERS) PATH and maximum N-1 KEYS i(nformation) and N-1 DATA RECORD POINTERS ( path) 

2) successors can have minimum ceil N/2-1 (i.e 4/2-1=1)KEYS  zero  DATA RECORD POINTERS  and  maximum N-1 KEYS  & N-1 DATA RECORD POINTERS
 

3)tail enders  can have minimum ceil (m-1)/2 (i.e (4-1)/2=1.5=>2) KEYS &  zero DATA RECORD POINTERS & maximim N-1 KEYS &  N-1 DATA RECORD POINTERS

1)if we have INFORAMTION then only we can have PATH...i.e if we have keys...then only we can have data record pointers ....
2)we  can also have keys alone in the node ...
3) data record pointers are not allowed alone..keys must be there with them...
leaf nodes should be at same level....

edited by
3 votes
3 votes

B-Tree is a self-balancing search tree. In most of the other self-balancing search trees (like AVL and Red Black Trees), it is assumed that everything is in main memory. To understand use of B-Trees, we must think of huge amount of data that cannot fit in main memory. When the number of keys is high, the data is read from disk in the form of blocks. Disk access time is very high compared to main memory access time. The main idea of using B-Trees is to reduce the number of disk accesses. Most of the tree operations (search, insert, delete, max, min, ..etc ) require O(h) disk accesses where h is height of the tree. B-tree is a fat tree. Height of B-Trees is kept low by putting maximum possible keys in a B-Tree node. Generally, a B-Tree node size is kept equal to the disk block size. Since h is low for B-Tree, total disk accesses for most of the operations are reduced significantly compared to balanced Binary Search Trees like AVL Tree, Red Black Tree, ..etc.

You can Refer this for Properties , Internal Node ,Insertion Into B+Tree and Deletion from B+Tree : http://www.tutorialspoint.com/dbms/dbms_indexing.htm   (Look at the Bottom of the page )

Related questions

0 votes
0 votes
1 answer
1
gauravkumawat asked Jun 13, 2023
880 views
please solve in paper formet Explain the properties of B-Tree Also Construct B+ tree with order P=410,5,30,40,20,17,90,45,93,60,20,50,29
0 votes
0 votes
0 answers
2
0 votes
0 votes
1 answer
3
Crackcer asked Jan 10, 2022
235 views
1. Suppose there is a B-tree, such that internal node with order 86 and leaf node with order 103.2. A B+ tree with internal order is 171 and leaf node with order 103.In b...
2 votes
2 votes
2 answers
4