B-TREE PREPARED BY M V BRAHMANANDA REDDY
Download as PPT, PDF0 likes491 views
![33
BB++ -- TTrreeee SSttrruuccttuurree
AA BB++ -- TTrreeee iiss iinn tthhee ffoorrmm ooff aa bbaallaanncceedd ttrreeee iinn
wwhhiicchh eevveerryy ppaatthh ffrroomm tthhee rroooott ooff tthhee ttrreeee ttoo aa
lleeaaff ooff tthhee ttrreeee iiss tthhee ssaammee lleennggtthh..
EEaacchh nnoonnlleeaaff nnooddee iinn tthhee ttrreeee hhaass bbeettwweeeenn [[nn//22]]
aanndd nn cchhiillddrreenn,, wwhheerree nn iiss ffiixxeedd..
BB++ -- TTrreeeess aarree ggoooodd ffoorr sseeaarrcchheess,, bbuutt ccaauussee
ssoommee oovveerrhheeaadd iissssuueess iinn wwaasstteedd ssppaaccee..](https://image.slidesharecdn.com/mvbreddybtree-140917023844-phpapp01/85/B-TREE-PREPARED-BY-M-V-BRAHMANANDA-REDDY-3-320.jpg)
![66
Each leaf can hhoolldd uupp ttoo nn 11 vvaalluueess aanndd mmuusstt
ccoonnttaaiinn aatt lleeaasstt [[((nn 11)) // 22]] vvaalluueess..
NNoonnlleeaaff nnooddee ppooiinntteerrss ppooiinntt ttoo ttrreeee nnooddeess ((lleeaaff
nnooddeess)).. NNoonnlleeaaff nnooddeess ccaann hhoolldd uupp ttoo nn ppooiinntteerrss
aanndd mmuusstt hhoolldd aatt lleeaasstt [[nn//22]] ppooiinntteerrss..
ii..ee.. nn == 33
Perryridge
Mianus Redwood
Brighton Downtown Mianus Redwood Round Hill
Perryridge](https://image.slidesharecdn.com/mvbreddybtree-140917023844-phpapp01/85/B-TREE-PREPARED-BY-M-V-BRAHMANANDA-REDDY-6-320.jpg)
More Related Content
What's hot (17)
Viewers also liked (7)
Similar to B-TREE PREPARED BY M V BRAHMANANDA REDDY (20)
More from Malikireddy Bramhananda Reddy (20)
B-TREE PREPARED BY M V BRAHMANANDA REDDY
- 1. 11 BB++ -- TTrreeee && BB -- TTrreeee MM VV BB RREEDDDDYY GGIITTAAMM UUNNIIVVEERRSSIITTYY BBEENNGGAALLUURRUU
- 2. 22 AAggeennddaa BB++ -- TTrreeee SSttrruuccttuurree BB++ -- TTrreeee UUppddaatteess BB++ -- TTrreeee FFiillee OOrrggaanniizzaattiioonn BB -- TTrreeee IInnddeexx FFiilleess
- 3. 33 BB++ -- TTrreeee SSttrruuccttuurree AA BB++ -- TTrreeee iiss iinn tthhee ffoorrmm ooff aa bbaallaanncceedd ttrreeee iinn wwhhiicchh eevveerryy ppaatthh ffrroomm tthhee rroooott ooff tthhee ttrreeee ttoo aa lleeaaff ooff tthhee ttrreeee iiss tthhee ssaammee lleennggtthh.. EEaacchh nnoonnlleeaaff nnooddee iinn tthhee ttrreeee hhaass bbeettwweeeenn [[nn//22]] aanndd nn cchhiillddrreenn,, wwhheerree nn iiss ffiixxeedd.. BB++ -- TTrreeeess aarree ggoooodd ffoorr sseeaarrcchheess,, bbuutt ccaauussee ssoommee oovveerrhheeaadd iissssuueess iinn wwaasstteedd ssppaaccee..
- 4. A typical node ccoonnttaaiinnss uupp ttoo nn 11 sseeaarrcchh kkeeyy vvaalluueess KK11,, KK22,,,, KKnn--11,, aanndd nn ppooiinntteerrss PP11,, PP22,, ,, PPnn.. TThhee sseeaarrcchh kkeeyy vvaalluueess aarree kkeepptt iinn ssoorrtteedd oorrddeerr.. 44 P1 K1 P2 Pn-1 Kn-1 Pn
- 5. 55 The pointer Pi can point ttoo eeiitthheerr aa ffiillee rreeccoorrdd oorr aa bbuucckkeett ooff ppooiinntteerrss wwhhiicchh eeaacchh ppooiinntt ttoo aa ffiillee rreeccoorrdd.. lleeaaff nnooddee,, nn == 33 Brighton Downtown A 212 Brighton 750 A 101 Brighton 750 A 212 Brighton 750 ...
- 6. 66 Each leaf can hhoolldd uupp ttoo nn 11 vvaalluueess aanndd mmuusstt ccoonnttaaiinn aatt lleeaasstt [[((nn 11)) // 22]] vvaalluueess.. NNoonnlleeaaff nnooddee ppooiinntteerrss ppooiinntt ttoo ttrreeee nnooddeess ((lleeaaff nnooddeess)).. NNoonnlleeaaff nnooddeess ccaann hhoolldd uupp ttoo nn ppooiinntteerrss aanndd mmuusstt hhoolldd aatt lleeaasstt [[nn//22]] ppooiinntteerrss.. ii..ee.. nn == 33 Perryridge Mianus Redwood Brighton Downtown Mianus Redwood Round Hill Perryridge
- 7. 77 BB++ -- TTrreeee UUppddaatteess IInnsseerrttiioonn IIff tthhee nneeww nnooddee hhaass aa sseeaarrcchh kkeeyy tthhaatt aallrreeaaddyy eexxiissttss iinn aannootthheerr lleeaaff nnooddee,, tthheenn iitt aaddddss tthhee nneeww rreeccoorrdd ttoo tthhee ffiillee aanndd aa ppooiinntteerr ttoo tthhee bbuucckkeett ooff ppooiinntteerrss.. IIff tthhee sseeaarrcchh kkeeyy iiss ddiiffffeerreenntt ffrroomm aallll ootthheerrss,, iitt iiss iinnsseerrtteedd iinn oorrddeerr.. DDeelleettiioonn IItt rreemmoovveess tthhee sseeaarrcchh kkeeyy vvaalluuee ffrroomm tthhee nnooddee..
- 8. 88 i.e. we are ggooiinngg ttoo iinnsseerrtt aa nnooddee wwiitthh aa sseeaarrcchh kkeeyy vvaalluuee CClleeaarrvviieeww.. WWee ffiinndd tthhaatt CClleeaarrvviieeww sshhoouulldd bbee iinn tthhee nnooddee wwiitthh BBrriigghhttoonn aanndd DDoowwnnttoowwnn,, ssoo wwee mmuusstt sspplliitt tthhee nnooddee.. ii..ee.. nn == 33 Perryridge Downtown Mianus Redwood Brighton Clearview Mianus Redwood Round Hill Perryridge Downtown
- 9. 99 i.e. Deletion ooff DDoowwnnttoowwnn ffrroomm sslliiddee ##88.. Perryridge Mianus Redwood Brighton Clearview Mianus Redwood Round Hill Perryridge
- 10. 1100 ii..ee.. DDeelleettiioonn ooff PPeerrrryyrriiddggee ffrroomm sslliiddee ##88 Mianus Downtown Redwood Brighton Clearview Mianus Redwood Round Hill Downtown
- 11. BB++ -- TTrreeee FFiillee OOrrggaanniizzaattiioonn IInn aa BB++ -- TTrreeee ffiillee oorrggaanniizzaattiioonn,, tthhee lleeaaff nnooddeess ooff tthhee ttrreeee ssttoorreess tthhee aaccttuuaall rreeccoorrdd rraatthheerr tthhaann ssttoorriinngg ppooiinntteerrss ttoo rreeccoorrddss.. DDuurriinngg iinnsseerrttiioonn,, tthhee ssyysstteemm llooccaatteess tthhee bblloocckk tthhaatt sshhoouulldd ccoonnttaaiinn tthhee rreeccoorrdd.. IIff tthheerree iiss eennoouugghh ffrreeee ssppaaccee iinn tthhee nnooddee tthheenn tthhee ssyysstteemm ssttoorreess iitt.. OOtthheerrwwiissee tthhee ssyysstteemm sspplliittss tthhee rreeccoorrdd iinn ttwwoo aanndd ddiissttrriibbuutteess tthhee rreeccoorrddss.. DDuurriinngg ddeelleettiioonn,, tthhee ssyysstteemm ffiirrsstt rreemmoovveess tthhee rreeccoorrdd ffrroomm tthhee bblloocckk ccoonnttaaiinniinngg iitt.. IIff tthhee bblloocckk bbeeccoommeess lleessss tthhaann hhaallff ffuullll aass aa rreessuulltt,, tthhee rreeccoorrddss iinn tthhee bblloocckk aarree rreeddiissttrriibbuutteedd.. 1111
- 12. 1122 BB++ -- TTrreeee FFiillee OOrrggaanniizzaattiioonn
- 13. 1133 BB -- TTrreeee IInnddeexx FFiilleess Similar to B+-tree, but B-tree allows search-key values to appear only once; eliminates redundant storage of search keys. Search keys in nonleaf nodes appear nowhere else in the B-tree; an additional pointer field for each search key in a nonleaf node must be included. NNoonnlleeaaff nnooddee ppooiinntteerrss BBii aarree tthhee bbuucckkeett oorr ffiillee rreeccoorrdd ppooiinntteerrss..
- 14. 1144 BB TTrreeee IInnddeexx FFiilleess AAddvvaannttaaggeess ooff BB--TTrreeee iinnddiicceess:: MMaayy uussee lleessss ttrreeee nnooddeess tthhaann aa ccoorrrreessppoonnddiinngg BB++--TTrreeee.. SSoommeettiimmeess ppoossssiibbllee ttoo ffiinndd sseeaarrcchh--kkeeyy vvaalluuee bbeeffoorree rreeaacchhiinngg lleeaaff nnooddee.. DDiissaaddvvaannttaaggeess ooff BB--TTrreeee iinnddiicceess:: OOnnllyy ssmmaallll ffrraaccttiioonn ooff aallll sseeaarrcchh--kkeeyy vvaalluueess aarree ffoouunndd eeaarrllyy NNoonn--lleeaaff nnooddeess aarree llaarrggeerr,, ssoo ffaann--oouutt iiss rreedduucceedd.. TThhuuss BB--TTrreeeess ttyyppiiccaallllyy hhaavvee ggrreeaatteerr ddeepptthh tthhaann ccoorrrreessppoonnddiinngg BB++--TTrreeee IInnsseerrttiioonn aanndd ddeelleettiioonn mmoorree ccoommpplliiccaatteedd tthhaann iinn BB++--TTrreeeess IImmpplleemmeennttaattiioonn iiss hhaarrddeerr tthhaann BB++--TTrreeeess..
- 15. 1155 EExxaammppllee ooff BB TTrreeee