హే హబ్ర్! వ్యాసం యొక్క అనువాదాన్ని నేను మీ దృష్టికి అందిస్తున్నాను
"రిలేషనల్ డేటాబేస్ ఎలా పని చేస్తుంది".

రిలేషనల్ డేటాబేస్‌ల విషయానికి వస్తే నేను సహాయం చేయలేను, కానీ ఏదో తప్పిపోయిందని నేను అనుకోను. వారు ప్రతిచోటా ఉపయోగిస్తారు. చిన్న మరియు ఉపయోగకరమైన SQLite నుండి శక్తివంతమైన టెరాడేటా వరకు అనేక విభిన్న డేటాబేస్‌లు అందుబాటులో ఉన్నాయి. కానీ డేటాబేస్ ఎలా పనిచేస్తుందో వివరించే కొన్ని కథనాలు మాత్రమే ఉన్నాయి. మీరు "howdoesarelationaldatabasework"ని ఉపయోగించి మీ కోసం శోధించవచ్చు. అంతేకాకుండా, ఈ వ్యాసాలు చిన్నవి. మీరు సరికొత్త బజీ టెక్నాలజీల (BigData, NoSQL లేదా JavaScript) కోసం చూస్తున్నట్లయితే, అవి ఎలా పని చేస్తాయో వివరించే మరిన్ని లోతైన కథనాలను మీరు కనుగొంటారు.

రిలేషనల్ డేటాబేస్‌లు చాలా పాతవి మరియు విశ్వవిద్యాలయ కోర్సులు, పరిశోధనా పత్రాలు మరియు పుస్తకాల వెలుపల వివరించడానికి చాలా విసుగుగా ఉన్నాయా?

డెవలపర్‌గా, నాకు అర్థం కాని వాటిని ఉపయోగించడాన్ని నేను ద్వేషిస్తున్నాను. మరియు డేటాబేస్‌లను 40 సంవత్సరాలకు పైగా ఉపయోగించినట్లయితే, దానికి కారణం ఉండాలి. సంవత్సరాలుగా, నేను ప్రతిరోజూ ఉపయోగించే ఈ వింత బ్లాక్ బాక్స్‌లను నిజంగా అర్థం చేసుకోవడానికి వందల గంటలు గడిపాను. రిలేషనల్ డేటాబేస్‌లు వారు ఎందుకంటే చాలా ఆసక్తికరమైన ఉపయోగకరమైన మరియు పునర్వినియోగ భావనల ఆధారంగా. మీరు డేటాబేస్‌ను అర్థం చేసుకోవడంలో ఆసక్తి కలిగి ఉంటే, కానీ ఈ విస్తృత అంశాన్ని లోతుగా పరిశోధించడానికి ఎప్పుడూ సమయం లేదా మొగ్గు చూపకపోతే, మీరు ఈ కథనాన్ని ఆస్వాదించాలి.

ఈ వ్యాసం యొక్క శీర్షిక స్పష్టంగా ఉన్నప్పటికీ, ఈ వ్యాసం యొక్క ఉద్దేశ్యం డేటాబేస్ను ఎలా ఉపయోగించాలో అర్థం చేసుకోవడం కాదు. అందుకే, సాధారణ కనెక్షన్ అభ్యర్థన మరియు ప్రాథమిక ప్రశ్నలను ఎలా వ్రాయాలో మీకు ఇప్పటికే తెలిసి ఉండాలి రా; లేకుంటే మీరు ఈ కథనాన్ని అర్థం చేసుకోలేరు. మీరు తెలుసుకోవలసినది ఒక్కటే, మిగిలినవి వివరిస్తాను.

నేను అల్గారిథమ్‌ల సమయ సంక్లిష్టత (BigO) వంటి కొన్ని కంప్యూటర్ సైన్స్ బేసిక్స్‌తో ప్రారంభిస్తాను. మీలో కొందరు ఈ భావనను ద్వేషిస్తారని నాకు తెలుసు, కానీ అది లేకుండా మీరు డేటాబేస్‌లోని చిక్కులను అర్థం చేసుకోలేరు. ఇది పెద్ద అంశం కాబట్టి, నేను దృష్టి పెడతాను నేను ఏమనుకుంటున్నానో అది ముఖ్యం: డేటాబేస్ ఎలా ప్రాసెస్ చేస్తుంది SQL విచారణ. నేను పరిచయం చేస్తాను ప్రాథమిక డేటాబేస్ భావనలుకాబట్టి వ్యాసం చివరలో మీరు హుడ్ కింద ఏమి జరుగుతుందో గురించి ఒక ఆలోచన కలిగి ఉంటారు.

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

మీలో మరింత పరిజ్ఞానం ఉన్నవారి కోసం, ఈ కథనం 3 భాగాలుగా విభజించబడింది:

• తక్కువ-స్థాయి మరియు ఉన్నత-స్థాయి డేటాబేస్ భాగాల యొక్క అవలోకనం
• ప్రశ్న ఆప్టిమైజేషన్ ప్రక్రియ యొక్క అవలోకనం
• లావాదేవీ మరియు బఫర్ పూల్ నిర్వహణ యొక్క అవలోకనం

తిరిగి ప్రాథమిక అంశాలకు

సంవత్సరాల క్రితం (గెలాక్సీలో, చాలా దూరంగా...), డెవలపర్‌లు తాము కోడింగ్ చేస్తున్న ఆపరేషన్‌ల సంఖ్యను ఖచ్చితంగా తెలుసుకోవాలి. వారు తమ స్లో కంప్యూటర్‌ల యొక్క CPU మరియు మెమరీని వృధా చేయలేరు కాబట్టి వారు వారి అల్గారిథమ్‌లు మరియు డేటా స్ట్రక్చర్‌లను హృదయపూర్వకంగా తెలుసుకున్నారు.

ఈ భాగంలో, డేటాబేస్‌ను అర్థం చేసుకోవడానికి అవసరమైన వాటిలో కొన్నింటిని నేను మీకు గుర్తు చేస్తాను. కాన్సెప్ట్‌ని కూడా పరిచయం చేస్తాను డేటాబేస్ సూచిక.

O(1) vs O(n2)

ఈ రోజుల్లో, చాలా మంది డెవలపర్‌లు అల్గారిథమ్‌ల సమయ సంక్లిష్టత గురించి పట్టించుకోరు... మరియు వారు సరైనదే!

కానీ మీరు చాలా డేటాతో వ్యవహరిస్తున్నప్పుడు (నేను వేలల్లో మాట్లాడటం లేదు) లేదా మీరు మిల్లీసెకన్లలో కష్టపడుతున్నట్లయితే, ఈ భావనను అర్థం చేసుకోవడం చాలా క్లిష్టమైనది. మరియు మీరు ఊహించినట్లుగా, డేటాబేస్లు రెండు పరిస్థితులను ఎదుర్కోవాలి! పాయింట్‌ని అర్థం చేసుకోవడానికి నేను మీకు అవసరమైన దానికంటే ఎక్కువ సమయం కేటాయించను. ఇది ఖర్చు-ఆధారిత ఆప్టిమైజేషన్ భావనను తరువాత అర్థం చేసుకోవడానికి మాకు సహాయపడుతుంది (ఖరీదు ఆధారిత సర్వోత్తమీకరణం).

భావన

అల్గోరిథం యొక్క సమయ సంక్లిష్టత ఇచ్చిన మొత్తం డేటా కోసం అల్గారిథమ్ పూర్తి చేయడానికి ఎంత సమయం పడుతుందో చూడటానికి ఉపయోగించబడుతుంది. ఈ సంక్లిష్టతను వివరించడానికి, మేము పెద్ద O గణిత సంజ్ఞామానాన్ని ఉపయోగిస్తాము. ఇచ్చిన సంఖ్యలో ఇన్‌పుట్‌ల కోసం అల్గారిథమ్‌కు ఎన్ని ఆపరేషన్‌లు అవసరమో వివరించే ఫంక్షన్‌తో ఈ సంజ్ఞామానం ఉపయోగించబడుతుంది.

ఉదాహరణకు, "ఈ అల్గోరిథం సంక్లిష్టత O(some_function())" అని నేను చెప్పినప్పుడు, కొంత మొత్తంలో డేటాను ప్రాసెస్ చేయడానికి అల్గారిథమ్‌కి కొన్ని_function(a_certain_amount_of_data) ఆపరేషన్‌లు అవసరమని అర్థం.

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

ఈ గ్రాఫ్‌లో మీరు వివిధ రకాల అల్గారిథమ్ సమయ సంక్లిష్టతలకు సంబంధించిన ఇన్‌పుట్ డేటా మొత్తానికి వ్యతిరేకంగా ఆపరేషన్‌ల సంఖ్యను చూడవచ్చు. నేను వాటిని ప్రదర్శించడానికి లాగరిథమిక్ స్కేల్‌ని ఉపయోగించాను. మరో మాటలో చెప్పాలంటే, డేటా మొత్తం త్వరగా 1 నుండి 1 బిలియన్ వరకు పెరుగుతుంది. మనం దీనిని చూడవచ్చు:

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

ఉదాహరణలు

తక్కువ మొత్తంలో డేటాతో, O(1) మరియు O(n2) మధ్య వ్యత్యాసం చాలా తక్కువగా ఉంటుంది. ఉదాహరణకు, మీరు 2000 మూలకాలను ప్రాసెస్ చేయడానికి అవసరమైన అల్గారిథమ్‌ని కలిగి ఉన్నారని అనుకుందాం.

• O(1) అల్గోరిథం మీకు 1 ఆపరేషన్ ఖర్చు అవుతుంది
• O(log(n)) అల్గోరిథం మీకు 7 ఆపరేషన్‌లను ఖర్చు చేస్తుంది
• O(n) అల్గోరిథం మీకు 2 ఆపరేషన్‌లను ఖర్చు చేస్తుంది
• O(n*log(n)) అల్గోరిథం మీకు 14 ఆపరేషన్‌లను ఖర్చు చేస్తుంది
• O(n2) అల్గోరిథం మీకు 4 ఆపరేషన్‌లను ఖర్చు చేస్తుంది

O(1) మరియు O(n2) మధ్య వ్యత్యాసం పెద్దదిగా కనిపిస్తోంది (4 మిలియన్ల ఆపరేషన్‌లు) కానీ మీరు గరిష్ఠంగా 2 msని కోల్పోతారు, కేవలం మీ కళ్ళు రెప్పవేయడం మాత్రమే. నిజానికి, ఆధునిక ప్రాసెసర్లు ప్రాసెస్ చేయగలవు సెకనుకు వందల మిలియన్ల కార్యకలాపాలు. అందుకే అనేక IT ప్రాజెక్ట్‌లలో పనితీరు మరియు ఆప్టిమైజేషన్ సమస్య కాదు.

నేను చెప్పినట్లుగా, భారీ మొత్తంలో డేటాతో పని చేస్తున్నప్పుడు ఈ భావనను తెలుసుకోవడం ఇప్పటికీ ముఖ్యం. ఈసారి అల్గోరిథం 1 మూలకాలను ప్రాసెస్ చేయాల్సి ఉంటే (డేటాబేస్‌కు ఇది అంతగా ఉండదు):

• O(1) అల్గోరిథం మీకు 1 ఆపరేషన్ ఖర్చు అవుతుంది
• O(log(n)) అల్గోరిథం మీకు 14 ఆపరేషన్‌లను ఖర్చు చేస్తుంది
• O(n) అల్గోరిథం మీకు 1 ఆపరేషన్‌లను ఖర్చు చేస్తుంది
• O(n*log(n)) అల్గోరిథం మీకు 14 ఆపరేషన్‌లను ఖర్చు చేస్తుంది
• O(n2) అల్గోరిథం మీకు 1 ఆపరేషన్లను ఖర్చు చేస్తుంది

నేను గణితాన్ని పూర్తి చేయలేదు, కానీ O(n2) అల్గారిథమ్‌తో మీరు కాఫీ తాగడానికి సమయం ఉందని నేను చెప్తాను (రెండు కూడా!). మీరు డేటా వాల్యూమ్‌కు మరో 0ని జోడిస్తే, మీరు నిద్రించడానికి సమయం ఉంటుంది.

లోతుగా వెళ్దాం

సూచన కోసం:

• మంచి హాష్ టేబుల్ లుకప్ O(1)లో ఒక మూలకాన్ని కనుగొంటుంది.
• బాగా సమతుల్య చెట్టును శోధించడం O(log(n))లో ఫలితాలను ఇస్తుంది.
• శ్రేణిని శోధించడం O(n)లో ఫలితాలను అందిస్తుంది.
• ఉత్తమ సార్టింగ్ అల్గారిథమ్‌లు సంక్లిష్టత O(n*log(n))ని కలిగి ఉంటాయి.
• చెడ్డ సార్టింగ్ అల్గోరిథం సంక్లిష్టత O(n2)ని కలిగి ఉంటుంది.

గమనిక: క్రింది భాగాలలో మనం ఈ అల్గారిథమ్‌లు మరియు డేటా స్ట్రక్చర్‌లను చూస్తాము.

అల్గోరిథం సమయ సంక్లిష్టతలో అనేక రకాలు ఉన్నాయి:

• సగటు కేసు దృశ్యం
• ఉత్తమ సందర్భం
• మరియు చెత్త దృష్టాంతం

సమయ సంక్లిష్టత తరచుగా చెత్త దృష్టాంతంగా ఉంటుంది.

నేను అల్గోరిథం యొక్క సమయ సంక్లిష్టత గురించి మాత్రమే మాట్లాడుతున్నాను, కానీ సంక్లిష్టత దీనికి కూడా వర్తిస్తుంది:

• అల్గోరిథం యొక్క మెమరీ వినియోగం
• డిస్క్ I/O వినియోగ అల్గోరిథం

వాస్తవానికి, n2 కంటే అధ్వాన్నమైన సమస్యలు ఉన్నాయి, ఉదాహరణకు:

• n4: ఇది భయంకరమైనది! పేర్కొన్న కొన్ని అల్గారిథమ్‌లు ఈ సంక్లిష్టతను కలిగి ఉన్నాయి.
• 3n: ఇది మరింత ఘోరంగా ఉంది! ఈ వ్యాసం మధ్యలో మనం చూడబోయే అల్గారిథమ్‌లలో ఒకటి ఈ సంక్లిష్టతను కలిగి ఉంది (మరియు ఇది వాస్తవానికి అనేక డేటాబేస్‌లలో ఉపయోగించబడుతుంది).
• ఫాక్టోరియల్ n: మీరు తక్కువ మొత్తంలో డేటాతో కూడా మీ ఫలితాలను ఎప్పటికీ పొందలేరు.
• nn: మీరు ఈ సంక్లిష్టతను ఎదుర్కొంటే, ఇది నిజంగా మీ కార్యాచరణ రంగం కాదా అని మీరే ప్రశ్నించుకోవాలి...

గమనిక: నేను మీకు పెద్ద O హోదా యొక్క అసలు నిర్వచనం ఇవ్వలేదు, కేవలం ఒక ఆలోచన మాత్రమే. మీరు ఈ కథనాన్ని ఇక్కడ చదవవచ్చు వికీపీడియా నిజమైన (అసింప్టోటిక్) నిర్వచనం కోసం.

విలీనక్రమం

మీరు సేకరణను క్రమబద్ధీకరించాల్సిన అవసరం వచ్చినప్పుడు మీరు ఏమి చేస్తారు? ఏమిటి? మీరు sort() ఫంక్షన్‌కి కాల్ చేయండి... సరే, మంచి సమాధానం... కానీ డేటాబేస్ కోసం, ఈ విధమైన () ఫంక్షన్ ఎలా పనిచేస్తుందో మీరు అర్థం చేసుకోవాలి.

అనేక మంచి సార్టింగ్ అల్గారిథమ్‌లు ఉన్నాయి, కాబట్టి నేను చాలా ముఖ్యమైన వాటిపై దృష్టి పెడతాను: విలీన క్రమము. ప్రస్తుతం డేటాను క్రమబద్ధీకరించడం ఎందుకు ఉపయోగపడుతుందో మీకు అర్థం కాకపోవచ్చు, కానీ మీరు ప్రశ్న ఆప్టిమైజేషన్ భాగాన్ని తర్వాత అర్థం చేసుకోవాలి. అంతేకాకుండా, విలీన క్రమాన్ని అర్థం చేసుకోవడం అనేది సాధారణ డేటాబేస్ చేరిక ఆపరేషన్‌ను అర్థం చేసుకోవడంలో మాకు సహాయపడుతుంది విలీనం చేరడానికి (విలీన సంఘం).

విలీనం

అనేక ఉపయోగకరమైన అల్గారిథమ్‌ల మాదిరిగానే, విలీన క్రమబద్ధీకరణ ఒక ఉపాయం మీద ఆధారపడి ఉంటుంది: N/2 పరిమాణంలోని 2 క్రమబద్ధీకరించబడిన శ్రేణులను N-మూలకం క్రమబద్ధీకరించిన శ్రేణిలో కలపడం వలన N కార్యకలాపాలకు మాత్రమే ఖర్చు అవుతుంది. ఈ చర్యను విలీనం అంటారు.

ఒక సాధారణ ఉదాహరణతో దీని అర్థం ఏమిటో చూద్దాం:

చివరిగా క్రమబద్ధీకరించబడిన 8-మూలకాల శ్రేణిని నిర్మించడానికి, మీరు 2 4-మూలకాల శ్రేణులపై ఒక్కసారి మాత్రమే పునరావృతం చేయాల్సి ఉంటుందని ఈ సంఖ్య చూపిస్తుంది. రెండు 4-మూలకాల శ్రేణులు ఇప్పటికే క్రమబద్ధీకరించబడినందున:

• 1) మీరు రెండు ప్రస్తుత మూలకాలను రెండు శ్రేణులలో సరిపోల్చండి (ప్రారంభంలో కరెంట్ = మొదటిది)
• 2) ఆపై 8 మూలకాల శ్రేణిలో ఉంచడానికి చిన్నదాన్ని తీసుకోండి
• 3) మరియు మీరు చిన్న మూలకాన్ని తీసుకున్న శ్రేణిలోని తదుపరి మూలకానికి తరలించండి
• మరియు మీరు శ్రేణులలో ఒకదాని యొక్క చివరి మూలకాన్ని చేరుకునే వరకు 1,2,3 పునరావృతం చేయండి.
• అప్పుడు మీరు వాటిని 8 మూలకాల శ్రేణిలో ఉంచడానికి ఇతర శ్రేణి యొక్క మిగిలిన మూలకాలను తీసుకోండి.

4-ఎలిమెంట్ శ్రేణులు రెండూ క్రమబద్ధీకరించబడినందున ఇది పని చేస్తుంది మరియు మీరు ఆ శ్రేణులలో "వెనుకకు" వెళ్లవలసిన అవసరం లేదు.

ఇప్పుడు మేము ఉపాయాన్ని అర్థం చేసుకున్నాము, విలీనం కోసం నా సూడోకోడ్ ఇక్కడ ఉంది:

array mergeSort(array a)
   if(length(a)==1)
      return a[0];
   end if

   //recursive calls
   [left_array right_array] := split_into_2_equally_sized_arrays(a);
   array new_left_array := mergeSort(left_array);
   array new_right_array := mergeSort(right_array);

   //merging the 2 small ordered arrays into a big one
   array result := merge(new_left_array,new_right_array);
   return result;

విలీనం క్రమబద్ధీకరణ సమస్యను చిన్న సమస్యలుగా విభజిస్తుంది మరియు అసలు సమస్య యొక్క ఫలితాన్ని పొందడానికి చిన్న సమస్యల ఫలితాలను కనుగొంటుంది (గమనిక: ఈ రకమైన అల్గారిథమ్‌ను విభజించి జయించడం అంటారు). మీకు ఈ అల్గోరిథం అర్థం కాకపోతే, చింతించకండి; మొదటిసారి చూసినప్పుడు నాకు అర్థం కాలేదు. ఇది మీకు సహాయం చేయగలిగితే, నేను ఈ అల్గారిథమ్‌ని రెండు-దశల అల్గారిథమ్‌గా చూస్తాను:

• డివిజన్ దశ, ఇక్కడ శ్రేణి చిన్న శ్రేణులుగా విభజించబడింది
• క్రమబద్ధీకరణ దశ అనేది చిన్న శ్రేణులను కలిపి (యూనియన్ ఉపయోగించి) పెద్ద శ్రేణిని ఏర్పరుస్తుంది.

విభజన దశ

విభజన దశలో, శ్రేణి 3 దశల్లో ఏకీకృత శ్రేణులుగా విభజించబడింది. అధికారిక దశల సంఖ్య లాగ్(N) (N=8, లాగ్(N) = 3 కాబట్టి).

ఇది నాకు ఎలా తెలుసు?

నేను మేధావిని! ఒక్క మాటలో చెప్పాలంటే - గణితం. ఆలోచన ఏమిటంటే, ప్రతి దశ అసలు శ్రేణి యొక్క పరిమాణాన్ని 2 ద్వారా భాగిస్తుంది. దశల సంఖ్య అనేది మీరు అసలు శ్రేణిని రెండుగా విభజించగల సంఖ్య. ఇది సంవర్గమానం యొక్క ఖచ్చితమైన నిర్వచనం (బేస్ 2).

క్రమబద్ధీకరణ దశ

క్రమబద్ధీకరణ దశలో, మీరు ఏకీకృత (సింగిల్-ఎలిమెంట్) శ్రేణులతో ప్రారంభించండి. ప్రతి దశలో మీరు బహుళ విలీన కార్యకలాపాలను వర్తింపజేస్తారు మరియు మొత్తం ధర N = 8 కార్యకలాపాలు:

• మొదటి దశలో మీరు 4 విలీనాలను కలిగి ఉన్నారు, ఒక్కోదానికి 2 ఆపరేషన్లు ఖర్చవుతాయి
• రెండవ దశలో మీరు 2 విలీనాలను కలిగి ఉన్నారు, ఒక్కోదానికి 4 ఆపరేషన్‌లు ఖర్చవుతాయి
• మూడవ దశలో మీరు 1 విలీనాన్ని కలిగి ఉన్నారు, దీనికి 8 ఆపరేషన్లు ఖర్చవుతాయి

లాగ్(N) దశలు ఉన్నందున, మొత్తం ఖర్చు N * లాగ్ (N) కార్యకలాపాలు.

విలీన రకం యొక్క ప్రయోజనాలు

ఈ అల్గోరిథం ఎందుకు అంత శక్తివంతమైనది?

ఎందుకంటే:

• మీరు కొత్త శ్రేణులను సృష్టించకుండా నేరుగా ఇన్‌పుట్ శ్రేణిని సవరించడానికి మెమరీ పాదముద్రను తగ్గించడానికి దాన్ని మార్చవచ్చు.

గమనిక: ఈ రకమైన అల్గోరిథం అంటారు in-స్థానం (అదనపు మెమరీ లేకుండా క్రమబద్ధీకరించడం).

• ముఖ్యమైన డిస్క్ I/O ఓవర్‌హెడ్‌కు గురికాకుండా మీరు ఒకే సమయంలో డిస్క్ స్పేస్ మరియు తక్కువ మొత్తంలో మెమరీని ఉపయోగించేలా దీన్ని మార్చవచ్చు. ప్రస్తుతం ప్రాసెస్ చేయబడుతున్న భాగాలను మాత్రమే మెమరీలోకి లోడ్ చేయాలనే ఆలోచన ఉంది. మీరు 100-మెగాబైట్ మెమరీ బఫర్‌తో బహుళ-గిగాబైట్ పట్టికను క్రమబద్ధీకరించాల్సిన అవసరం వచ్చినప్పుడు ఇది ముఖ్యం.

గమనిక: ఈ రకమైన అల్గోరిథం అంటారు బాహ్య విధమైన.

• మీరు దీన్ని బహుళ ప్రక్రియలు/థ్రెడ్‌లు/సర్వర్‌లలో అమలు చేయడానికి మార్చవచ్చు.

ఉదాహరణకు, పంపిణీ చేయబడిన విలీన క్రమబద్ధీకరణ అనేది కీలకమైన భాగాలలో ఒకటి హడూప్ (ఇది పెద్ద డేటాలో ఒక నిర్మాణం).

• ఈ అల్గోరిథం సీసాన్ని బంగారంగా మార్చగలదు (నిజంగా!).

ఈ సార్టింగ్ అల్గోరిథం చాలా (అన్ని కాకపోయినా) డేటాబేస్‌లలో ఉపయోగించబడుతుంది, కానీ ఇది ఒక్కటే కాదు. మీరు మరింత తెలుసుకోవాలనుకుంటే, మీరు దీన్ని చదవగలరు పరిశోధన పని, ఇది సాధారణ డేటాబేస్ సార్టింగ్ అల్గారిథమ్‌ల యొక్క లాభాలు మరియు నష్టాలను చర్చిస్తుంది.

అర్రే, ట్రీ మరియు హాష్ టేబుల్

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

అమరిక

రెండు డైమెన్షనల్ శ్రేణి అనేది సరళమైన డేటా నిర్మాణం. పట్టికను శ్రేణిగా భావించవచ్చు. ఉదాహరణకి:

ఈ 2 డైమెన్షనల్ శ్రేణి అడ్డు వరుసలు మరియు నిలువు వరుసలతో కూడిన పట్టిక:

• ప్రతి పంక్తి ఒక ఎంటిటీని సూచిస్తుంది
• నిలువు వరుసలు ఎంటిటీని వివరించే లక్షణాలను నిల్వ చేస్తాయి.
• ప్రతి నిలువు వరుస నిర్దిష్ట రకం (పూర్ణాంకం, స్ట్రింగ్, తేదీ...) డేటాను నిల్వ చేస్తుంది.

డేటాను నిల్వ చేయడానికి మరియు దృశ్యమానం చేయడానికి ఇది సౌకర్యవంతంగా ఉంటుంది, అయితే, మీరు నిర్దిష్ట విలువను కనుగొనవలసి వచ్చినప్పుడు, ఇది తగినది కాదు.

ఉదాహరణకు, మీరు UKలో పనిచేసే అబ్బాయిలందరినీ కనుగొనాలనుకుంటే, ఆ వరుస UKకి చెందినదో కాదో నిర్ధారించడానికి మీరు ప్రతి అడ్డు వరుసను చూడాలి. ఇది మీకు N లావాదేవీలకు ఖర్చు అవుతుందిపేరు N - లైన్ల సంఖ్య, ఇది చెడ్డది కాదు, కానీ వేగవంతమైన మార్గం ఉందా? ఇప్పుడు మనం చెట్లతో పరిచయం పెంచుకునే సమయం వచ్చింది.

గమనిక: చాలా ఆధునిక డేటాబేస్‌లు పట్టికలను సమర్ధవంతంగా నిల్వ చేయడానికి విస్తరించిన శ్రేణులను అందిస్తాయి: హీప్-ఆర్గనైజ్డ్ టేబుల్స్ మరియు ఇండెక్స్-ఆర్గనైజ్డ్ టేబుల్స్. కానీ ఇది నిలువు వరుసల సమూహంలో నిర్దిష్ట స్థితిని త్వరగా కనుగొనే సమస్యను మార్చదు.

డేటాబేస్ చెట్టు మరియు సూచిక

బైనరీ సెర్చ్ ట్రీ అనేది ఒక ప్రత్యేక ఆస్తిని కలిగి ఉండే బైనరీ ట్రీ, ప్రతి నోడ్‌లోని కీ తప్పనిసరిగా ఇలా ఉండాలి:

• ఎడమ సబ్‌ట్రీలో నిల్వ చేయబడిన అన్ని కీల కంటే ఎక్కువ
• కుడి సబ్‌ట్రీలో నిల్వ చేయబడిన అన్ని కీల కంటే తక్కువ

దృశ్యపరంగా దీని అర్థం ఏమిటో చూద్దాం

ఆలోచన

ఈ చెట్టు N = 15 మూలకాలను కలిగి ఉంటుంది. నేను 208 కోసం వెతుకుతున్నానని అనుకుందాం:

• నేను రూట్ నుండి ప్రారంభిస్తాను దీని కీ 136. 136<208 నుండి, నేను నోడ్ 136 యొక్క కుడి సబ్‌ట్రీని చూస్తున్నాను.
• 398>208 కాబట్టి నేను నోడ్ 398 యొక్క ఎడమ సబ్‌ట్రీని చూస్తున్నాను
• 250>208 కాబట్టి నేను నోడ్ 250 యొక్క ఎడమ సబ్‌ట్రీని చూస్తున్నాను
• 200<208, కాబట్టి నేను నోడ్ 200 యొక్క కుడి సబ్‌ట్రీని చూస్తున్నాను. కానీ 200కి సరైన సబ్‌ట్రీ లేదు, విలువ ఉండదు (ఎందుకంటే అది ఉనికిలో ఉంటే, అది కుడి సబ్‌ట్రీ 200లో ఉంటుంది).

ఇప్పుడు నేను 40 కోసం చూస్తున్నాను అనుకుందాం

• నేను రూట్ నుండి ప్రారంభిస్తాను, దీని కీ 136. 136 > 40 నుండి, నేను నోడ్ 136 యొక్క ఎడమ సబ్‌ట్రీని చూస్తాను.
• 80 > 40, అందుకే నేను నోడ్ 80 యొక్క ఎడమ సబ్‌ట్రీని చూస్తున్నాను
• 40= 40, నోడ్ ఉంది. నేను నోడ్‌లోని అడ్డు వరుస IDని తిరిగి పొందాను (చిత్రంలో చూపబడలేదు) మరియు ఇచ్చిన అడ్డు వరుస ID కోసం పట్టికలో చూడండి.
• అడ్డు వరుస IDని తెలుసుకోవడం వలన పట్టికలో డేటా ఎక్కడ ఉందో ఖచ్చితంగా తెలుసుకోగలుగుతాను, కనుక నేను దానిని తక్షణమే తిరిగి పొందగలను.

చివరికి, రెండు శోధనలు నాకు చెట్టు లోపల స్థాయిల సంఖ్యను ఖర్చు చేస్తాయి. మీరు విలీనం క్రమబద్ధీకరణ గురించి భాగాన్ని జాగ్రత్తగా చదివితే, మీరు లాగ్(N) స్థాయిలు ఉన్నట్లు చూడాలి. ఇది మారుతుంది, శోధన ధర లాగ్ (N), చెడ్డది కాదు!

మన సమస్యకు తిరిగి వద్దాం

కానీ ఇది చాలా వియుక్తమైనది, కాబట్టి మన సమస్యకు తిరిగి వద్దాం. సాధారణ పూర్ణాంకానికి బదులుగా, మునుపటి పట్టికలోని ఒకరి దేశాన్ని సూచించే స్ట్రింగ్‌ను ఊహించుకోండి. మీరు పట్టికలోని "దేశం" ఫీల్డ్ (కాలమ్ 3)ని కలిగి ఉన్న చెట్టును కలిగి ఉన్నారని అనుకుందాం:

• UKలో ఎవరు పనిచేస్తున్నారో తెలుసుకోవాలంటే
• గ్రేట్ బ్రిటన్‌ను సూచించే నోడ్‌ని పొందడానికి మీరు చెట్టును చూస్తారు
• "UKnode" లోపల మీరు UK వర్కర్ రికార్డ్‌ల స్థానాన్ని కనుగొంటారు.

మీరు శ్రేణిని నేరుగా ఉపయోగిస్తే, ఈ శోధనకు N ఆపరేషన్‌లకు బదులుగా లాగ్(N) ఆపరేషన్‌లు ఖర్చవుతాయి. మీరు ఇప్పుడే అందించినది డేటాబేస్ సూచిక.

మీరు కీలను (అంటే ఫీల్డ్ గ్రూప్‌లు) సరిపోల్చడానికి ఫంక్షన్‌ని కలిగి ఉన్నంత వరకు మీరు ఏదైనా ఫీల్డ్‌ల సమూహానికి (స్ట్రింగ్, నంబర్, 2 లైన్లు, నంబర్ మరియు స్ట్రింగ్, తేదీ...) ఇండెక్స్ ట్రీని నిర్మించవచ్చు. కీల మధ్య క్రమం (డేటాబేస్‌లోని ఏదైనా ప్రాథమిక రకాలకు ఇది వర్తిస్తుంది).

బి+ట్రీ ఇండెక్స్

నిర్దిష్ట విలువను పొందడానికి ఈ చెట్టు బాగా పనిచేస్తుండగా, మీకు అవసరమైనప్పుడు పెద్ద సమస్య ఉంటుంది రెండు విలువల మధ్య బహుళ మూలకాలను పొందండి. దీనికి O(N) ఖర్చవుతుంది, ఎందుకంటే మీరు చెట్టులోని ప్రతి నోడ్‌ను చూడాలి మరియు అది ఈ రెండు విలువల మధ్య ఉందో లేదో తనిఖీ చేయాలి (ఉదా. చెట్టు యొక్క ఆర్డర్ ట్రావర్సల్‌తో). అంతేకాకుండా, మీరు మొత్తం ట్రీని చదవవలసి ఉంటుంది కాబట్టి ఈ ఆపరేషన్ డిస్క్ I/O ఫ్రెండ్లీ కాదు. సమర్థవంతంగా అమలు చేయడానికి మేము ఒక మార్గాన్ని కనుగొనాలి పరిధి అభ్యర్థన. ఈ సమస్యను పరిష్కరించడానికి, ఆధునిక డేటాబేస్‌లు B+Tree అని పిలువబడే మునుపటి చెట్టు యొక్క సవరించిన సంస్కరణను ఉపయోగిస్తాయి. బి+ట్రీ చెట్టులో:

• అత్యల్ప నోడ్లు మాత్రమే (ఆకులు) సమాచారాన్ని నిల్వ చేయండి (సంబంధిత పట్టికలో అడ్డు వరుసల స్థానం)
• మిగిలిన నోడ్‌లు ఇక్కడ ఉన్నాయి రూటింగ్ కోసం సరైన నోడ్‌కి శోధన సమయంలో.

మీరు చూడగలిగినట్లుగా, ఇక్కడ ఎక్కువ నోడ్‌లు ఉన్నాయి (రెండుసార్లు). నిజానికి, మీకు అదనపు నోడ్‌లు ఉన్నాయి, "నిర్ణయ నోడ్‌లు", అది మీకు సరైన నోడ్‌ను కనుగొనడంలో సహాయపడుతుంది (అనుబంధ పట్టికలో అడ్డు వరుసల స్థానాన్ని నిల్వ చేస్తుంది). కానీ శోధన సంక్లిష్టత ఇప్పటికీ O(లాగ్(N)) (మరో ఒక స్థాయి మాత్రమే ఉంది). పెద్ద తేడా ఏమిటంటే దిగువ స్థాయిలో ఉన్న నోడ్‌లు వాటి వారసులకు అనుసంధానించబడి ఉంటాయి.

ఈ B+ట్రీతో, మీరు 40 మరియు 100 మధ్య విలువల కోసం చూస్తున్నట్లయితే:

• మీరు మునుపటి చెట్టుతో చేసినట్లుగా మీరు 40 (లేదా 40 ఉనికిలో లేకుంటే 40 తర్వాత సమీప విలువ) కోసం వెతకాలి.
• మీరు 40కి చేరుకునే వరకు డైరెక్ట్ హెయిర్ లింక్‌లను ఉపయోగించి 100 మంది వారసులను సేకరించండి.

మీరు M వారసులను కనుగొన్నారని మరియు చెట్టుకు N నోడ్‌లు ఉన్నాయని అనుకుందాం. నిర్దిష్ట నోడ్‌ని కనుగొనడం వలన మునుపటి ట్రీ లాగా లాగ్(N) ఖర్చవుతుంది. కానీ మీరు ఈ నోడ్‌ని పొందిన తర్వాత, మీరు M ఆపరేషన్‌లలో M వారసులను వారి వారసుల సూచనలతో పొందుతారు. ఈ శోధనకు M+log(N) మాత్రమే ఖర్చవుతుంది మునుపటి ట్రీపై N ఆపరేషన్‌లతో పోలిస్తే కార్యకలాపాలు. అంతేకాకుండా, మీరు పూర్తి ట్రీ (M+log(N) నోడ్‌లు మాత్రమే) చదవాల్సిన అవసరం లేదు, అంటే డిస్క్ వినియోగం తక్కువగా ఉంటుంది. M చిన్నది (ఉదా. 200 వరుసలు) మరియు N పెద్దది (1 వరుసలు) అయితే, పెద్ద వ్యత్యాసం ఉంటుంది.

కానీ ఇక్కడ కొత్త సమస్యలు ఉన్నాయి (మళ్ళీ!). మీరు డేటాబేస్‌లో అడ్డు వరుసను జోడించినా లేదా తొలగిస్తే (అందువలన అనుబంధిత B+Tree ఇండెక్స్‌లో):

• మీరు B+Tree లోపల నోడ్‌ల మధ్య క్రమాన్ని తప్పనిసరిగా నిర్వహించాలి, లేకుంటే మీరు క్రమబద్ధీకరించని చెట్టు లోపల నోడ్‌లను కనుగొనలేరు.
• మీరు B+Treeలో కనీస సాధ్యం స్థాయిల సంఖ్యను తప్పనిసరిగా ఉంచాలి, లేకుంటే O(log(N)) సమయ సంక్లిష్టత O(N) అవుతుంది.

మరో మాటలో చెప్పాలంటే, B+Tree తప్పనిసరిగా స్వీయ-ఆర్డర్ మరియు సమతుల్యతను కలిగి ఉండాలి. అదృష్టవశాత్తూ, స్మార్ట్ డిలీట్ మరియు ఇన్సర్ట్ ఆపరేషన్‌లతో ఇది సాధ్యమవుతుంది. కానీ ఇది ఖర్చుతో వస్తుంది: B+ ట్రీలో చొప్పించడం మరియు తొలగింపుల ధర O(లాగ్(N)). అందుకే మీలో కొందరు విన్నారు చాలా ఎక్కువ సూచికలను ఉపయోగించడం మంచిది కాదు. నిజంగా, మీరు పట్టికలో అడ్డు వరుసను వేగంగా చొప్పించడం/నవీకరించడం/తొలగించడం నెమ్మదిస్తున్నారుఎందుకంటే డేటాబేస్ ప్రతి ఇండెక్స్ కోసం ఖరీదైన O(log(N)) ఆపరేషన్‌ని ఉపయోగించి పట్టిక సూచికలను నవీకరించాలి. అంతేకాకుండా, ఇండెక్స్‌లను జోడించడం అంటే మరింత పనిభారం లావాదేవీ నిర్వాహకుడు (వ్యాసం చివరిలో వివరించబడుతుంది).

మరిన్ని వివరాల కోసం, మీరు వికీపీడియా కథనాన్ని చూడవచ్చు B+ట్రీ. డేటాబేస్‌లో B+Treeని అమలు చేయడానికి మీకు ఉదాహరణ కావాలంటే, ఒకసారి చూడండి ఈ వ్యాసం и ఈ వ్యాసం ప్రముఖ MySQL డెవలపర్ నుండి. InnoDB (MySQL ఇంజిన్) ఇండెక్స్‌లను ఎలా నిర్వహిస్తుందనే దానిపై వారిద్దరూ దృష్టి సారిస్తారు.

గమనిక: తక్కువ-స్థాయి ఆప్టిమైజేషన్‌ల కారణంగా, B+ ట్రీ పూర్తిగా సమతుల్యంగా ఉండాలని ఒక రీడర్ నాకు చెప్పారు.

హ్యాష్టబుల్

మా చివరి ముఖ్యమైన డేటా నిర్మాణం హాష్ పట్టిక. మీరు త్వరగా విలువలను చూడాలనుకున్నప్పుడు ఇది చాలా ఉపయోగకరంగా ఉంటుంది. అంతేకాకుండా, హాష్ టేబుల్‌ను అర్థం చేసుకోవడం వల్ల హాష్ జాయిన్ అని పిలువబడే సాధారణ డేటాబేస్ జాయిన్ ఆపరేషన్‌ని అర్థం చేసుకోవడంలో మాకు సహాయపడుతుంది ( హాష్ చేరండి) ఈ డేటా నిర్మాణం కొన్ని అంతర్గత విషయాలను నిల్వ చేయడానికి డేటాబేస్ ద్వారా కూడా ఉపయోగించబడుతుంది (ఉదా. లాక్ టేబుల్ లేదా బఫర్ పూల్, మేము ఈ రెండు భావనలను తరువాత చూస్తాము).

హాష్ టేబుల్ అనేది ఒక మూలకాన్ని దాని కీ ద్వారా త్వరగా కనుగొనే డేటా నిర్మాణం. హాష్ పట్టికను రూపొందించడానికి మీరు నిర్వచించాలి:

• కీ మీ అంశాల కోసం
• హాష్ ఫంక్షన్ కీల కోసం. కంప్యూటెడ్ కీ హాష్‌లు మూలకాల స్థానాన్ని ఇస్తాయి (అని పిలుస్తారు విభాగాలు ).
• కీలను పోల్చడానికి ఫంక్షన్. మీరు సరైన విభాగాన్ని కనుగొన్న తర్వాత, ఈ పోలికను ఉపయోగించి సెగ్మెంట్‌లో మీరు వెతుకుతున్న మూలకాన్ని తప్పక కనుగొనాలి.

సాధారణ ఉదాహరణ

స్పష్టమైన ఉదాహరణ తీసుకుందాం:

ఈ హాష్ పట్టికలో 10 విభాగాలు ఉన్నాయి. నేను సోమరిగా ఉన్నందున, నేను 5 విభాగాలను మాత్రమే చిత్రీకరించాను, కానీ మీరు తెలివైనవారని నాకు తెలుసు, కాబట్టి నేను మిగిలిన 5ని మీ స్వంతంగా చిత్రీకరించడానికి అనుమతిస్తాను. నేను కీ యొక్క హాష్ ఫంక్షన్ మాడ్యులో 10ని ఉపయోగించాను. మరో మాటలో చెప్పాలంటే, నేను దాని విభాగాన్ని కనుగొనడానికి మూలకం యొక్క కీ యొక్క చివరి అంకెను మాత్రమే నిల్వ చేస్తాను:

• చివరి అంకె 0 అయితే, మూలకం సెగ్మెంట్ 0లోకి వస్తుంది,
• చివరి అంకె 1 అయితే, మూలకం సెగ్మెంట్ 1లోకి వస్తుంది,
• చివరి అంకె 2 అయితే, మూలకం ప్రాంతం 2లోకి వస్తుంది,
• ...

నేను ఉపయోగించిన పోలిక ఫంక్షన్ రెండు పూర్ణాంకాల మధ్య సమానత్వం.

మీరు మూలకం 78ని పొందాలనుకుంటున్నారని అనుకుందాం:

• హాష్ పట్టిక 78 కోసం హాష్ కోడ్‌ను గణిస్తుంది, ఇది 8.
• హాష్ పట్టిక సెగ్మెంట్ 8ని చూస్తుంది మరియు అది కనుగొన్న మొదటి మూలకం 78.
• ఆమె మీకు ఐటెమ్ 78ని తిరిగి ఇస్తుంది
• శోధన ఖర్చులు కేవలం 2 ఆపరేషన్లు మాత్రమే (ఒకటి హాష్ విలువను లెక్కించడానికి మరియు మరొకటి విభాగంలోని మూలకాన్ని చూసేందుకు).

ఇప్పుడు మీరు ఎలిమెంట్ 59ని పొందాలనుకుంటున్నారని అనుకుందాం:

• హాష్ పట్టిక 59 కోసం హాష్ కోడ్‌ను గణిస్తుంది, ఇది 9.
• హాష్ పట్టిక సెగ్మెంట్ 9లో శోధిస్తుంది, మొదటి మూలకం 99. 99!=59 నుండి, మూలకం 99 చెల్లుబాటు అయ్యే మూలకం కాదు.
• అదే తర్కాన్ని ఉపయోగించి, రెండవ మూలకం (9), మూడవ (79), ..., చివరి (29) తీసుకోబడ్డాయి.
• మూలకం కనుగొనబడలేదు.
• శోధన ఖర్చు 7 కార్యకలాపాలు.

మంచి హాష్ ఫంక్షన్

మీరు చూస్తున్నట్లుగా, మీరు వెతుకుతున్న విలువను బట్టి, ఖర్చు ఒకేలా ఉండదు!

నేను ఇప్పుడు హాష్ ఫంక్షన్ మాడ్యులో 1 కీని మార్చినట్లయితే (అంటే, చివరి 000 అంకెలను తీసుకుంటే), సెగ్మెంట్ 000లో మూలకాలు లేనందున రెండవ శోధనకు 6 ఆపరేషన్ మాత్రమే ఖర్చవుతుంది. చాలా తక్కువ సంఖ్యలో ఎలిమెంట్‌లను కలిగి ఉన్న బకెట్‌లను సృష్టించే మంచి హాష్ ఫంక్షన్‌ను కనుగొనడం నిజమైన సవాలు.

నా ఉదాహరణలో, మంచి హాష్ ఫంక్షన్‌ను కనుగొనడం సులభం. కానీ ఇది ఒక సాధారణ ఉదాహరణ, కీ అయినప్పుడు మంచి హాష్ ఫంక్షన్‌ను కనుగొనడం చాలా కష్టం:

• స్ట్రింగ్ (ఉదాహరణకు - చివరి పేరు)
• 2 పంక్తులు (ఉదాహరణకు - చివరి పేరు మరియు మొదటి పేరు)
• 2 పంక్తులు మరియు తేదీ (ఉదాహరణకు - చివరి పేరు, మొదటి పేరు మరియు పుట్టిన తేదీ)
• ...

మంచి హాష్ ఫంక్షన్‌తో, హాష్ టేబుల్ లుకప్‌ల ధర O(1).

అర్రే vs హాష్ టేబుల్

శ్రేణిని ఎందుకు ఉపయోగించకూడదు?

హ్మ్, మంచి ప్రశ్న.

• హాష్ పట్టిక ఉంటుంది మెమరీలోకి పాక్షికంగా లోడ్ చేయబడింది, మరియు మిగిలిన విభాగాలు డిస్క్‌లో ఉండవచ్చు.
• శ్రేణితో మీరు తప్పనిసరిగా మెమొరీలో పక్కన ఉన్న స్థలాన్ని ఉపయోగించాలి. మీరు పెద్ద పట్టికను లోడ్ చేస్తుంటే తగినంత నిరంతర స్థలాన్ని కనుగొనడం చాలా కష్టం.
• హాష్ పట్టిక కోసం, మీరు మీకు కావలసిన కీని ఎంచుకోవచ్చు (ఉదాహరణకు, దేశం మరియు వ్యక్తి యొక్క చివరి పేరు).

మరింత సమాచారం కోసం, మీరు గురించి కథనాన్ని చదవవచ్చు జావాహాష్ మ్యాప్, ఇది హాష్ పట్టిక యొక్క సమర్థవంతమైన అమలు; ఈ కథనంలో కవర్ చేయబడిన భావనలను అర్థం చేసుకోవడానికి మీరు జావాను అర్థం చేసుకోవలసిన అవసరం లేదు.

మూలం: www.habr.com