విషయము

• పోలిక చార్ట్
• B- చెట్టు యొక్క నిర్వచనం
• ఆర్డర్ M యొక్క B- చెట్టు యొక్క లక్షణాలు
• బైనరీ చెట్టు యొక్క నిర్వచనం
• ట్రావెర్సల్ టెక్నిక్స్
• ముగింపు

బి-ట్రీ మరియు బైనరీ ట్రీ అనేది నాన్-లీనియర్ డేటా స్ట్రక్చర్ రకాలు. నిబంధనలు సారూప్యంగా ఉన్నప్పటికీ అన్ని అంశాలలో భిన్నంగా ఉంటాయి. RAM యొక్క ప్రాప్యత వేగం డిస్క్ కంటే చాలా ఎక్కువగా ఉన్నందున రికార్డులు లేదా డేటా డిస్కుకు బదులుగా RAM లో నిల్వ చేయబడినప్పుడు బైనరీ చెట్టు ఉపయోగించబడుతుంది. మరోవైపు, డేటాను డిస్క్‌లో నిల్వ చేసినప్పుడు బి-ట్రీ ఉపయోగించబడుతుంది, ఇది చెట్టు యొక్క ఎత్తును తగ్గించడం మరియు నోడ్‌లోని కొమ్మలను పెంచడం ద్వారా యాక్సెస్ సమయాన్ని తగ్గిస్తుంది.

B- చెట్టు మరియు బైనరీ చెట్టు మధ్య ఉన్న మరో వ్యత్యాసం ఏమిటంటే, B- చెట్టు దాని పిల్లల నోడ్‌లన్నింటినీ ఒకే స్థాయిలో కలిగి ఉండాలి, అయితే బైనరీ చెట్టుకు అలాంటి పరిమితి లేదు. ఒక బైనరీ చెట్టు గరిష్టంగా 2 సబ్‌ట్రీలు లేదా నోడ్‌లను కలిగి ఉంటుంది, అయితే B- ట్రీలో M కు సబ్‌ట్రీలు లేదా నోడ్‌లు ఉండవు, ఇక్కడ M అనేది B- ట్రీ యొక్క క్రమం.

1. పోలిక చార్ట్
2. నిర్వచనం
3. కీ తేడాలు
4. ముగింపు

పోలిక చార్ట్

పోలిక కోసం ఆధారం	B-tree	బైనరీ చెట్టు
అవసరమైన అడ్డంకి	ఒక నోడ్ పిల్లల నోడ్ల గరిష్ట M సంఖ్యను కలిగి ఉంటుంది (ఇక్కడ M అనేది చెట్టు యొక్క క్రమం).	ఒక నోడ్ గరిష్టంగా 2 సంఖ్యల సబ్‌ట్రీలను కలిగి ఉంటుంది.
ఉపయోగించబడిన	డేటా డిస్క్‌లో నిల్వ చేయబడినప్పుడు ఇది ఉపయోగించబడుతుంది.	రికార్డులు మరియు డేటా RAM లో నిల్వ చేయబడినప్పుడు ఇది ఉపయోగించబడుతుంది.
చెట్టు యొక్క ఎత్తు	లాగ్M N (ఇక్కడ m అనేది M- వే చెట్టు యొక్క క్రమం)	లాగ్2 N
అప్లికేషన్	అనేక DBMS లో కోడ్ ఇండెక్సింగ్ డేటా నిర్మాణం.	కోడ్ ఆప్టిమైజేషన్, హఫ్ఫ్మన్ కోడింగ్ మొదలైనవి.

B- చెట్టు యొక్క నిర్వచనం

B- చెట్టు అనేది సమతుల్య M- వే చెట్టు మరియు దీనిని సమతుల్య విధమైన చెట్టు అని కూడా పిలుస్తారు. ఇది బైనరీ సెర్చ్ ట్రీని పోలి ఉంటుంది, ఇక్కడ నోడర్లు ఇన్ఆర్డర్ ట్రావెర్సల్ ఆధారంగా నిర్వహించబడతాయి. B- చెట్టు యొక్క స్థల సంక్లిష్టత O (n). చొప్పించడం మరియు తొలగించే సమయం సంక్లిష్టత O (లాగ్ n).

B- చెట్టుకు తప్పక కొన్ని షరతులు ఉన్నాయి:

• చెట్టు యొక్క ఎత్తు సాధ్యమైనంత కనిష్టంగా ఉండాలి.
• చెట్టు ఆకుల పైన, ఖాళీ సబ్‌ట్రీలు ఉండకూడదు.
• చెట్టు ఆకులు తప్పనిసరిగా అదే స్థాయిలో రావాలి.
• సెలవు నోడ్లు తప్ప అన్ని నోడ్లలో కనీసం పిల్లలు ఉండాలి.

ఆర్డర్ M యొక్క B- చెట్టు యొక్క లక్షణాలు

• ప్రతి నోడ్‌లో గరిష్ట M పిల్లల సంఖ్య మరియు కనీస M / 2 పిల్లల సంఖ్య లేదా 2 నుండి గరిష్టంగా ఏదైనా సంఖ్య ఉండవచ్చు.
• ప్రతి నోడ్‌లో గరిష్ట M-1 కీలు ఉన్న పిల్లల కంటే ఒక కీ తక్కువగా ఉంటుంది.
• కీల అమరిక నోడ్స్‌లో కొన్ని నిర్దిష్ట క్రమంలో ఉంటుంది. కీ యొక్క ఎడమ వైపున ఉన్న సబ్‌ట్రీలోని అన్ని కీలు కీ యొక్క పూర్వీకులు, మరియు కీ యొక్క కుడి వైపున ఉన్న వాటిని వారసులు అంటారు.
• పూర్తి నోడ్ చొప్పించే సమయంలో, చెట్టు రెండు భాగాలుగా విడిపోతుంది మరియు మధ్యస్థ విలువ కలిగిన కీ పేరెంట్ నోడ్ వద్ద చేర్చబడుతుంది.
• నోడ్స్ తొలగించబడినప్పుడు విలీన ఆపరేషన్ జరుగుతుంది.

బైనరీ చెట్టు యొక్క నిర్వచనం

బైనరీ చెట్టు అనేది ఒక చెట్టు నిర్మాణం, దాని పిల్లల నోడ్లకు గరిష్టంగా రెండు పాయింటర్లను కలిగి ఉంటుంది. అంటే నోడ్ కలిగి ఉన్న అత్యధిక డిగ్రీ 2 మరియు సున్నా లేదా ఒక-డిగ్రీ నోడ్ కూడా ఉండవచ్చు.

ఖచ్చితంగా బైనరీ చెట్టు, పూర్తి బైనరీ చెట్టు, విస్తరించిన బైనరీ చెట్టు మొదలైన బైనరీ చెట్టు యొక్క కొన్ని వైవిధ్యాలు ఉన్నాయి.

• ఖచ్చితంగా బైనరీ చెట్టు ఒక చెట్టు, ఇక్కడ ప్రతి టెర్మినల్ కాని నోడ్ ఎడమ సబ్‌ట్రీ మరియు కుడి సబ్‌ట్రీ కలిగి ఉండాలి.
• ఒక చెట్టును 2 కలిగి ఉన్న పరిస్థితిని సంతృప్తిపరిచినప్పుడు పూర్తి బైనరీ చెట్టు అంటారు ^నేను నేను స్థాయి ఉన్న ప్రతి స్థాయిలో నోడ్లు.
• థ్రెడ్డ్ బైనరీ అనేది బైనరీ చెట్టు, ఇది 0 నోడ్లు లేదా 2 సంఖ్య నోడ్లను కలిగి ఉంటుంది.

ట్రావెర్సల్ టెక్నిక్స్

ట్రీ ట్రావెర్సల్ అనేది చెట్టు డేటా నిర్మాణంపై తరచుగా జరిగే ఆపరేషన్లలో ఒకటి, దీనిలో ప్రతి నోడ్ ఒక క్రమ పద్ధతిలో ఒకసారి సందర్శిస్తుంది.

• క్రమరహిత- ఈ చెట్టు ట్రావెర్సల్‌లో ఎడమ సబ్‌ట్రీని పునరావృతంగా సందర్శిస్తారు, తరువాత రూట్ నోడ్ సందర్శించబడుతుంది మరియు చివరి కుడి సబ్‌ట్రీని సందర్శిస్తారు.
• ప్రీరర్- ఈ ట్రీ ట్రావెర్సల్‌లో రూట్ నోడ్‌ను మొదట ఎడమ సబ్‌ట్రీ మరియు చివరి కుడి సబ్‌ట్రీ వద్ద సందర్శిస్తారు.
• పోస్టార్డర్- ఈ టెక్నిక్ ఎడమ సబ్‌ట్రీని, ఆపై కుడి సబ్‌ట్రీని మరియు చివరి రూట్ నోడ్‌ను సందర్శిస్తుంది.

1. B- చెట్టులో, టెర్మినల్ కాని నోడ్ కలిగి ఉన్న పిల్లల సంఖ్యల గరిష్ట సంఖ్య M, ఇక్కడ M అనేది B- చెట్టు యొక్క క్రమం. మరోవైపు, బైనరీ చెట్టు గరిష్టంగా రెండు సబ్‌ట్రీలు లేదా చైల్డ్ నోడ్‌లను కలిగి ఉంటుంది.
2. డేటాను డిస్క్‌లో నిల్వ చేసినప్పుడు బి-ట్రీ ఉపయోగించబడుతుంది, అయితే ర్యామ్ వంటి ఫాస్ట్ మెమరీలో డేటాను నిల్వ చేసినప్పుడు బైనరీ ట్రీ ఉపయోగించబడుతుంది.
3. B- ట్రీ కోసం దరఖాస్తు యొక్క మరొక ప్రాంతం DBMS లోని కోడ్ ఇండెక్సింగ్ డేటా నిర్మాణం, దీనికి విరుద్ధంగా, బైనరీ ట్రీ కోడ్ ఆప్టిమైజేషన్, హఫ్ఫ్మన్ కోడింగ్ మొదలైన వాటిలో ఉపయోగించబడుతుంది.
4. B- చెట్టు యొక్క గరిష్ట ఎత్తు లాగ్_MN (M అనేది చెట్టు యొక్క క్రమం). దీనికి విరుద్ధంగా, బైనరీ చెట్టు గరిష్ట ఎత్తు లాగ్₂N (N అనేది నోడ్ల సంఖ్య మరియు బేస్ 2 ఎందుకంటే ఇది బైనరీ కోసం).

ముగింపు

బైనరీ మరియు బైనరీ సెర్చ్ ట్రీపై బి-ట్రీ ఉపయోగించబడుతుంది, దీని వెనుక ప్రధాన కారణం మెమరీ సోపానక్రమం, ఇక్కడ అధిక బ్యాండ్‌విడ్త్ ఛానెల్‌లతో కాష్‌కు CPU అనుసంధానించబడి ఉంటుంది, అయితే తక్కువ బ్యాండ్‌విడ్త్ ఛానెల్ ద్వారా CPU డిస్క్‌కు అనుసంధానించబడి ఉంటుంది. రికార్డులు RAM (చిన్న మరియు వేగవంతమైన) లో నిల్వ చేయబడినప్పుడు బైనరీ చెట్టు ఉపయోగించబడుతుంది మరియు రికార్డులు డిస్క్‌లో నిల్వ చేయబడినప్పుడు (పెద్ద మరియు నెమ్మదిగా) B- చెట్టు ఉపయోగించబడుతుంది. కాబట్టి, బైనరీ చెట్టుకు బదులుగా బి-ట్రీని ఉపయోగించడం వల్ల అధిక బ్రాంచింగ్ కారకం మరియు చెట్టు యొక్క ఎత్తు తగ్గడం వల్ల యాక్సెస్ సమయం గణనీయంగా తగ్గుతుంది.