टी-ट्री: Difference between revisions
No edit summary |
No edit summary |
||
| Line 21: | Line 21: | ||
}}</ref> | }}</ref> | ||
==नोड संरचनाएं== | ==नोड संरचनाएं== | ||
एक टी-ट्री नोड में सामान्यतः पैरेंट नोड के पॉइंटर्स, बाएँ और दाएँ चाइल्ड नोड, डेटा पॉइंटर्स की क्रमबद्ध सरणी और कुछ अतिरिक्त नियंत्रण डेटा होते हैं। दो सब-ट्री वाले नोड्स को | एक टी-ट्री नोड में सामान्यतः पैरेंट नोड के पॉइंटर्स, बाएँ और दाएँ चाइल्ड नोड, डेटा पॉइंटर्स की क्रमबद्ध सरणी और कुछ अतिरिक्त नियंत्रण डेटा होते हैं। दो सब-ट्री वाले नोड्स को इंटरनल नोड्स कहा जाता है, बिना सब-ट्री वाले नोड्स को लीफ नोड्स कहा जाता है और केवल सब-ट्री वाले नोड्स को हाफ-लीफ नोड्स कहा जाता है। नोड को किसी मान के लिए बाउंडिंग नोड कहा जाता है यदि मान समग्र रूप से नोड के वर्तमान न्यूनतम और अधिकतम मान के मध्य है। | ||
[[Image:T-tree-2.png|thumb|right|251px|बंधे हुए मूल्य]]प्रत्येक | [[Image:T-tree-2.png|thumb|right|251px|बंधे हुए मूल्य]]प्रत्येक इंटरनल नोड के लिए, लीफ या हाफ लीफ नोड्स उपस्थित होते हैं जिनमें इसके सबसे छोटे डेटा मान का पूर्ववर्ती होता है (जिसे सबसे उच्च निचली सीमा कहा जाता है) और जिसमें इसके अधि उच्च डेटा मान का उत्तराधिकारी होता है (जिसे सबसे कम ऊपरी सीमा कहा जाता है)। लीफ और हाफ-लीफ नोड्स में डेटा सरणी के एक से अधिकतम आकार तक किसी भी संख्या में डेटा तत्व सम्मिलित हो सकते हैं। इंटरनल नोड्स पूर्वनिर्धारित न्यूनतम और अधिकतम संख्या में तत्वों के मध्य अपना अधिभोग बनाए रखते हैं | ||
==एल्गोरिदम== | ==एल्गोरिदम== | ||
| Line 30: | Line 30: | ||
* खोज रूट नोड पर प्रारंभ होती है | * खोज रूट नोड पर प्रारंभ होती है | ||
* यदि वर्तमान नोड खोज मान के लिए बाउंडिंग नोड है तो उसके डेटा ऐरे को खोजा जाता है। यदि डेटा सरणी में मान नहीं मिलता है तो खोज विफल हो जाती है। | * यदि वर्तमान नोड खोज मान के लिए बाउंडिंग नोड है तो उसके डेटा ऐरे को खोजा जाता है। यदि डेटा सरणी में मान नहीं मिलता है तो खोज विफल हो जाती है। | ||
* यदि खोज मान वर्तमान नोड के न्यूनतम मान से कम है तो इसके बाएं सबट्री में खोज | * यदि खोज मान वर्तमान नोड के न्यूनतम मान से कम है तो इसके बाएं सबट्री में खोज प्रवाहित रखते है। यदि कोई बायाँ सबट्री नहीं है तो खोज विफल हो जाती है। | ||
* यदि खोज मान वर्तमान नोड के अधिकतम मान से अधिक है तो उसके दाएँ सबट्री में खोज | * यदि खोज मान वर्तमान नोड के अधिकतम मान से अधिक है तो उसके दाएँ सबट्री में खोज प्रवाहित रखते है। यदि कोई सही सबट्री नहीं है तो खोज विफल हो जाती है। | ||
===सम्मिलन=== | ===सम्मिलन=== | ||
* नए मान के लिए बाउंडिंग नोड खोजें। यदि ऐसा कोई नोड उपस्थित है तो: | * नए मान के लिए बाउंडिंग नोड खोजें। यदि ऐसा कोई नोड उपस्थित है तो: | ||
** जांचें कि क्या इसके डेटा ऐरे में अभी भी स्थान है, यदि हां तो नया मान डालें और समाप्त करें | ** जांचें कि क्या इसके डेटा ऐरे में अभी भी स्थान है, यदि हां तो नया मान डालें और समाप्त करें | ||
** यदि कोई स्थान उपलब्ध नहीं है तो नोड के डेटा ऐरे से न्यूनतम मान हटा दें और नया मान डालें। अब उस नोड के लिए सबसे | ** यदि कोई स्थान उपलब्ध नहीं है तो नोड के डेटा ऐरे से न्यूनतम मान हटा दें और नया मान डालें। अब उस नोड के लिए सबसे उच्च निचली सीमा को पकड़कर उस नोड पर आगे बढ़ें जिसमें नया मान डाला गया था। यदि हटाया गया न्यूनतम मान अभी भी वहां फिट बैठता है तो इसे नोड के नए अधिकतम मान के रूप में जोड़ें, अन्यथा इस नोड के लिए नया दायां सबनोड बनाएं। | ||
* यदि कोई बाउंडिंग नोड नहीं मिला तो खोजे गए अंतिम नोड में मान डालें यदि वह अभी भी उसमें फिट बैठता है। इस स्थिति में नया मान या तो नया न्यूनतम या अधिकतम मान बन जाएगा। यदि मान अब फिट नहीं बैठता है तो नया बाएँ या दाएँ सबट्री बनाएँ। | * यदि कोई बाउंडिंग नोड नहीं मिला तो खोजे गए अंतिम नोड में मान डालें यदि वह अभी भी उसमें फिट बैठता है। इस स्थिति में नया मान या तो नया न्यूनतम या अधिकतम मान बन जाएगा। यदि मान अब फिट नहीं बैठता है तो नया बाएँ या दाएँ सबट्री बनाएँ। | ||
| Line 48: | Line 48: | ||
अब हमें नोड प्रकार के आधार पर अंतर करना होगा: | अब हमें नोड प्रकार के आधार पर अंतर करना होगा: | ||
* | * इंटरनल नोड: | ||
यदि नोड के डेटा ऐरे में अब तत्वों की न्यूनतम संख्या से कम है तो इस नोड के | यदि नोड के डेटा ऐरे में अब तत्वों की न्यूनतम संख्या से कम है तो इस नोड के अधि उच्च निचले बाउंड मान को उसके डेटा मान पर ले जाएं। हाफ लीफ या लीफ नोड के लिए निम्नलिखित दो चरणों में से एक के साथ आगे बढ़ें जिससे मान हटा दिया गया था। | ||
* लसीका नोड: | * लसीका नोड: | ||
| Line 60: | Line 60: | ||
यदि नोड के डेटा ऐरे को ओवरफ्लो के बिना उसके लीफ के डेटा ऐरे के साथ मर्ज किया जा सकता है तो ऐसा करें और लीफ नोड को हटा दें। यदि आवश्यक हो तो ट्री को पुनः संतुलित करें। | यदि नोड के डेटा ऐरे को ओवरफ्लो के बिना उसके लीफ के डेटा ऐरे के साथ मर्ज किया जा सकता है तो ऐसा करें और लीफ नोड को हटा दें। यदि आवश्यक हो तो ट्री को पुनः संतुलित करें। | ||
=== | ===रोटेशन और बैलेंसिंग=== | ||
एक टी-ट्री को अंतर्निहित [[स्व-संतुलन द्विआधारी खोज वृक्ष| | एक टी-ट्री को अंतर्निहित [[स्व-संतुलन द्विआधारी खोज वृक्ष|सेल्फ-बैलेंसिंग बाइनरी सर्च ट्री।]] के शीर्ष पर क्रियान्वित किया गया है। विशेष रूप से, लेहमैन और कैरी का लेख टी-ट्री को [[ एवीएल पेड़ |एवीएल ट्री]] की तरह संतुलित करने का वर्णन करता है: यह तब बैलेंसिंग से बाहर हो जाता है जब नोड के चाइल्ड ट्री की ऊंचाई में कम से कम दो स्तर का अंतर होता है। यह किसी नोड को सम्मिलित करने या हटाने के बाद हो सकता है। सम्मिलन या विलोपन के बाद, ट्री को लीफ से जड़ तक स्कैन किया जाता है। यदि असंतुलन पाया जाता है, तो ट्री का रोटेशन या रोटेशन की जोड़ी का प्रदर्शन किया जाता है, जो पूरे ट्री को संतुलित करने की प्रमाण देता है। | ||
जब | जब रोटेशन के परिणामस्वरूप इंटरनल नोड में न्यूनतम संख्या से कम आइटम होते हैं, तो नोड के नए चाइल्ड (रेन) से आइटम इंटरनल नोड में ले जाया जाता है। | ||
==प्रदर्शन और स्टोरेज == | ==प्रदर्शन और स्टोरेज == | ||
चूँकि प्रदर्शन लाभों के कारण टी-ट्री का उपयोग एक बार मेन-मेमोरी डेटाबेस के लिए व्यापक रूप से किया जाता था, बहुत बड़े मेन-मेमोरी डेटाबेस के लिए वर्तमान की प्रवृत्तियों ने प्रावधान | चूँकि प्रदर्शन लाभों के कारण टी-ट्री का उपयोग एक बार मेन-मेमोरी डेटाबेस के लिए व्यापक रूप से किया जाता था, बहुत बड़े मेन-मेमोरी डेटाबेस के लिए वर्तमान की प्रवृत्तियों ने प्रावधान निवेश पर अधिक जोर दिया है। आधुनिक एनओएसक्यूएल डेटाबेस सिस्टम अधिकांशतः खरबों रिकॉर्ड संग्रहीत करते हैं, यहां तक कि एकल सूचकांक को संग्रहीत करने की मेमोरी निवेश जिसमें वास्तविक मान सम्मिलित होते हैं, दसियों या यहां तक कि सैकड़ों टेराबाइट्स से अधिक हो सकते हैं। | ||
==यह भी देखें== | ==यह भी देखें== | ||
* [[वृक्ष (ग्राफ़ सिद्धांत)|ट्री (ग्राफ़ | * [[वृक्ष (ग्राफ़ सिद्धांत)|ट्री (ग्राफ़ थ्योरी)]] | ||
* [[वृक्ष (सेट सिद्धांत)|ट्री (सेट | * [[वृक्ष (सेट सिद्धांत)|ट्री (सेट थ्योरी)]] | ||
* [[वृक्ष संरचना|ट्री | * [[वृक्ष संरचना|ट्री स्ट्रकचर]] | ||
* | *एक्सपौनेनटिअल ट्री | ||
===अन्य ट्री=== | ===अन्य ट्री=== | ||
* बी-ट्री ([[2-3 पेड़|2-3 ट्री]], [[2-3-4 पेड़|2-3-4 ट्री]], [[बी+ पेड़|बी+ ट्री]], बी*-ट्री, यूबी-ट्री) | * बी-ट्री ([[2-3 पेड़|2-3 ट्री]], [[2-3-4 पेड़|2-3-4 ट्री]], [[बी+ पेड़|बी+ ट्री]], बी*-ट्री, यूबी-ट्री) | ||
* [[नाचता हुआ पेड़| | * [[नाचता हुआ पेड़|डांसिंग ट्री]] | ||
* [[संलयन वृक्ष| | * [[संलयन वृक्ष|फयूसन ट्री]] | ||
* [[के-डी पेड़|के-डी ट्री]] | * [[के-डी पेड़|के-डी ट्री]] | ||
* [[ऑक्ट्री]] | * [[ऑक्ट्री]] | ||
* [[क्वाडट्री]] | * [[क्वाडट्री]] | ||
* [[आर-वृक्ष|आर-ट्री]] | * [[आर-वृक्ष|आर-ट्री]] | ||
* [[मूलांक वृक्ष| | * [[मूलांक वृक्ष|रेडिक्स ट्री]] | ||
* [[शीर्ष वृक्ष| | * [[शीर्ष वृक्ष|टॉप ट्री]] | ||
==संदर्भ== | ==संदर्भ== | ||
Revision as of 15:35, 28 July 2023
कंप्यूटर विज्ञान में टी-ट्री एक प्रकार की बाइनरी ट्री डेटा संरचना है जिसका उपयोग मेन मेमोरी डेटाबेस, जैसे डेटाब्लिट्ज़, एक्सट्रीमडीबी, माईएसक्यूएल क्लस्टर, टाइम्सटेन और मोबाइललाइट द्वारा किया जाता है।
टी-ट्री ऊंचाई-संतुलित ट्री इंडेक्स ट्री डेटा संरचना है जो स्थितियों के लिए अनुकूलित है जहां इंडेक्स और वास्तविक डेटा दोनों को पूरी तरह से मेमोरी में रखा जाता है, जैसे बी-ट्री एक इंडेक्स संरचना है जो हार्ड डिस्क जैसे ब्लॉक ओरिएंटेड सेकेंडरी स्टोरेज उपकरण पर स्टोरेज के लिए अनुकूलित होती है। टी-ट्रीज़ एवीएल ट्री जैसे इन-मेमोरी ट्री संरचनाओं के प्रदर्शन लाभ प्राप्त करना चाहते हैं, जबकि लार्ज स्टोरेज स्पेस ओवरहेड से बचते हैं जो उनके लिए सामान्य है।
टी-ट्री इंडेक्स ट्री नोड्स के अंदर अनुक्रमित डेटा फ़ील्ड की प्रतियां स्वयं नहीं रखते हैं। इसके अतिरिक्त, वे इस तथ्य का लाभ उठाते हैं कि वास्तविक डेटा सदैव इंडेक्स के साथ मेन मेमोरी में होता है जिससे उनमें केवल वास्तविक डेटा फ़ील्ड के पॉइंटर्स होंते है।
टी-ट्री में 'टी' मूल पेपर में नोड डेटा संरचनाओं के आकार को संदर्भित करता है जिसने पहली बार इस प्रकार के सूचकांक का वर्णन किया था।[1]
नोड संरचनाएं
एक टी-ट्री नोड में सामान्यतः पैरेंट नोड के पॉइंटर्स, बाएँ और दाएँ चाइल्ड नोड, डेटा पॉइंटर्स की क्रमबद्ध सरणी और कुछ अतिरिक्त नियंत्रण डेटा होते हैं। दो सब-ट्री वाले नोड्स को इंटरनल नोड्स कहा जाता है, बिना सब-ट्री वाले नोड्स को लीफ नोड्स कहा जाता है और केवल सब-ट्री वाले नोड्स को हाफ-लीफ नोड्स कहा जाता है। नोड को किसी मान के लिए बाउंडिंग नोड कहा जाता है यदि मान समग्र रूप से नोड के वर्तमान न्यूनतम और अधिकतम मान के मध्य है।
प्रत्येक इंटरनल नोड के लिए, लीफ या हाफ लीफ नोड्स उपस्थित होते हैं जिनमें इसके सबसे छोटे डेटा मान का पूर्ववर्ती होता है (जिसे सबसे उच्च निचली सीमा कहा जाता है) और जिसमें इसके अधि उच्च डेटा मान का उत्तराधिकारी होता है (जिसे सबसे कम ऊपरी सीमा कहा जाता है)। लीफ और हाफ-लीफ नोड्स में डेटा सरणी के एक से अधिकतम आकार तक किसी भी संख्या में डेटा तत्व सम्मिलित हो सकते हैं। इंटरनल नोड्स पूर्वनिर्धारित न्यूनतम और अधिकतम संख्या में तत्वों के मध्य अपना अधिभोग बनाए रखते हैं
एल्गोरिदम
खोज
- खोज रूट नोड पर प्रारंभ होती है
- यदि वर्तमान नोड खोज मान के लिए बाउंडिंग नोड है तो उसके डेटा ऐरे को खोजा जाता है। यदि डेटा सरणी में मान नहीं मिलता है तो खोज विफल हो जाती है।
- यदि खोज मान वर्तमान नोड के न्यूनतम मान से कम है तो इसके बाएं सबट्री में खोज प्रवाहित रखते है। यदि कोई बायाँ सबट्री नहीं है तो खोज विफल हो जाती है।
- यदि खोज मान वर्तमान नोड के अधिकतम मान से अधिक है तो उसके दाएँ सबट्री में खोज प्रवाहित रखते है। यदि कोई सही सबट्री नहीं है तो खोज विफल हो जाती है।
सम्मिलन
- नए मान के लिए बाउंडिंग नोड खोजें। यदि ऐसा कोई नोड उपस्थित है तो:
- जांचें कि क्या इसके डेटा ऐरे में अभी भी स्थान है, यदि हां तो नया मान डालें और समाप्त करें
- यदि कोई स्थान उपलब्ध नहीं है तो नोड के डेटा ऐरे से न्यूनतम मान हटा दें और नया मान डालें। अब उस नोड के लिए सबसे उच्च निचली सीमा को पकड़कर उस नोड पर आगे बढ़ें जिसमें नया मान डाला गया था। यदि हटाया गया न्यूनतम मान अभी भी वहां फिट बैठता है तो इसे नोड के नए अधिकतम मान के रूप में जोड़ें, अन्यथा इस नोड के लिए नया दायां सबनोड बनाएं।
- यदि कोई बाउंडिंग नोड नहीं मिला तो खोजे गए अंतिम नोड में मान डालें यदि वह अभी भी उसमें फिट बैठता है। इस स्थिति में नया मान या तो नया न्यूनतम या अधिकतम मान बन जाएगा। यदि मान अब फिट नहीं बैठता है तो नया बाएँ या दाएँ सबट्री बनाएँ।
यदि कोई नया नोड जोड़ा गया था तो ट्री को पुनः संतुलित करने की आवश्यकता हो सकती है, जैसा कि नीचे बताया गया है।
विलोपन
- हटाए जाने वाले मान के बाउंडिंग नोड की खोज करें। यदि कोई बाउंडिंग नोड नहीं मिलता है तो समाप्त करें।
- यदि बाउंडिंग नोड में मान नहीं है तो समाप्त करें।
- नोड के डेटा सरणी से मान हटाएं
अब हमें नोड प्रकार के आधार पर अंतर करना होगा:
- इंटरनल नोड:
यदि नोड के डेटा ऐरे में अब तत्वों की न्यूनतम संख्या से कम है तो इस नोड के अधि उच्च निचले बाउंड मान को उसके डेटा मान पर ले जाएं। हाफ लीफ या लीफ नोड के लिए निम्नलिखित दो चरणों में से एक के साथ आगे बढ़ें जिससे मान हटा दिया गया था।
- लसीका नोड:
यदि यह डेटा सरणी में एकमात्र तत्व था तो नोड हटा दें। यदि आवश्यक हो तो ट्री को पुनः संतुलित करें।
- हाफ लीफ नोड:
यदि नोड के डेटा ऐरे को ओवरफ्लो के बिना उसके लीफ के डेटा ऐरे के साथ मर्ज किया जा सकता है तो ऐसा करें और लीफ नोड को हटा दें। यदि आवश्यक हो तो ट्री को पुनः संतुलित करें।
रोटेशन और बैलेंसिंग
एक टी-ट्री को अंतर्निहित सेल्फ-बैलेंसिंग बाइनरी सर्च ट्री। के शीर्ष पर क्रियान्वित किया गया है। विशेष रूप से, लेहमैन और कैरी का लेख टी-ट्री को एवीएल ट्री की तरह संतुलित करने का वर्णन करता है: यह तब बैलेंसिंग से बाहर हो जाता है जब नोड के चाइल्ड ट्री की ऊंचाई में कम से कम दो स्तर का अंतर होता है। यह किसी नोड को सम्मिलित करने या हटाने के बाद हो सकता है। सम्मिलन या विलोपन के बाद, ट्री को लीफ से जड़ तक स्कैन किया जाता है। यदि असंतुलन पाया जाता है, तो ट्री का रोटेशन या रोटेशन की जोड़ी का प्रदर्शन किया जाता है, जो पूरे ट्री को संतुलित करने की प्रमाण देता है।
जब रोटेशन के परिणामस्वरूप इंटरनल नोड में न्यूनतम संख्या से कम आइटम होते हैं, तो नोड के नए चाइल्ड (रेन) से आइटम इंटरनल नोड में ले जाया जाता है।
प्रदर्शन और स्टोरेज
चूँकि प्रदर्शन लाभों के कारण टी-ट्री का उपयोग एक बार मेन-मेमोरी डेटाबेस के लिए व्यापक रूप से किया जाता था, बहुत बड़े मेन-मेमोरी डेटाबेस के लिए वर्तमान की प्रवृत्तियों ने प्रावधान निवेश पर अधिक जोर दिया है। आधुनिक एनओएसक्यूएल डेटाबेस सिस्टम अधिकांशतः खरबों रिकॉर्ड संग्रहीत करते हैं, यहां तक कि एकल सूचकांक को संग्रहीत करने की मेमोरी निवेश जिसमें वास्तविक मान सम्मिलित होते हैं, दसियों या यहां तक कि सैकड़ों टेराबाइट्स से अधिक हो सकते हैं।
यह भी देखें
- ट्री (ग्राफ़ थ्योरी)
- ट्री (सेट थ्योरी)
- ट्री स्ट्रकचर
- एक्सपौनेनटिअल ट्री
अन्य ट्री
- बी-ट्री (2-3 ट्री, 2-3-4 ट्री, बी+ ट्री, बी*-ट्री, यूबी-ट्री)
- डांसिंग ट्री
- फयूसन ट्री
- के-डी ट्री
- ऑक्ट्री
- क्वाडट्री
- आर-ट्री
- रेडिक्स ट्री
- टॉप ट्री
संदर्भ
- ↑ Lehman, Tobin J.; Carey, Michael J. (25–28 August 1986). A Study of Index Structures for Main Memory Database Management Systems. Twelfth International Conference on Very Large Databases (VLDB 1986). Kyoto. ISBN 0-934613-18-4.
