टी-ट्री
कंप्यूटर विज्ञान में टी-ट्री एक प्रकार की बाइनरी ट्री डेटा संरचना है जिसका उपयोग मुख्य मेमोरी डेटाबेस, जैसे डेटाब्लिट्ज़, एक्सट्रीमडीबी, माईएसक्यूएल क्लस्टर, टाइम्सटेन और मोबाइललाइट द्वारा किया जाता है।
टी-ट्री ऊंचाई-संतुलित ट्री इंडेक्स ट्री डेटा संरचना है जो स्थितियों के लिए अनुकूलित है जहां इंडेक्स और वास्तविक डेटा दोनों को पूरी तरह से मेमोरी में रखा जाता है, जैसे बी-ट्री एक इंडेक्स संरचना है जो हार्ड डिस्क जैसे ब्लॉक ओरिएंटेड सेकेंडरी स्टोरेज डिवाइस पर स्टोरेज के लिए अनुकूलित होती है। टी-ट्रीज़ एवीएल ट्री जैसे इन-मेमोरी ट्री संरचनाओं के प्रदर्शन लाभ प्राप्त करना चाहते हैं, जबकि लार्ज स्टोरेज स्पेस ओवरहेड से बचते हैं जो उनके लिए सामान्य है।
टी-ट्री इंडेक्स ट्री नोड्स के अंदर अनुक्रमित डेटा फ़ील्ड की प्रतियां स्वयं नहीं रखते हैं। इसके अतिरिक्त, वे इस तथ्य का लाभ उठाते हैं कि वास्तविक डेटा सदैव इंडेक्स के साथ मुख्य मेमोरी में होता है जिससे उनमें केवल वास्तविक डेटा फ़ील्ड के पॉइंटर्स होंते है।
टी-ट्री में 'टी' मूल पेपर में नोड डेटा संरचनाओं के आकार को संदर्भित करता है जिसने पहली बार इस प्रकार के सूचकांक का वर्णन किया था।[1]
के आकार को संदर्भित करता है जिसने पहली बार इस प्रकार के सूचकांक का वर्णन किया था।[1]टी-ट्री में 'टी' मूल पेपर में नोड डेटा संरचनाओं के आकार को संदर्भित करता है जिसने पहली बार इस प्रकार के सूचकांक का वर्णन किया था।[1]
नोड संरचनाएं
एक टी-ट्री नोड में सामान्यतः पैरेंट नोड के पॉइंटर्स, बाएँ और दाएँ चाइल्ड नोड, डेटा पॉइंटर्स की क्रमबद्ध सरणी और कुछ अतिरिक्त नियंत्रण डेटा होते हैं। दो उप-ट्री वाले नोड्स को आंतरिक नोड्स कहा जाता है, बिना उप-ट्री वाले नोड्स को लीफ नोड्स कहा जाता है और केवल उप-ट्री वाले नोड्स को हाफ-लीफ नोड्स कहा जाता है। नोड को किसी मान के लिए बाउंडिंग नोड कहा जाता है यदि मान समग्र रूप से नोड के वर्तमान न्यूनतम और अधिकतम मान के बीच है।
प्रत्येक आंतरिक नोड के लिए, लीफ या हाफ लीफ नोड्स उपस्थित होते हैं जिनमें इसके सबसे छोटे डेटा मान का पूर्ववर्ती होता है (जिसे सबसे बड़ी निचली सीमा कहा जाता है) और जिसमें इसके सबसे बड़े डेटा मान का उत्तराधिकारी होता है (जिसे सबसे कम ऊपरी सीमा कहा जाता है)। लीफ और हाफ-लीफ नोड्स में डेटा सरणी के एक से अधिकतम आकार तक किसी भी संख्या में डेटा तत्व सम्मिलित हो सकते हैं। आंतरिक नोड्स पूर्वनिर्धारित न्यूनतम और अधिकतम संख्या में तत्वों के बीच अपना अधिभोग बनाए रखते हैं
एल्गोरिदम
खोज
- खोज रूट नोड पर शुरू होती है
- यदि वर्तमान नोड खोज मान के लिए बाउंडिंग नोड है तो उसके डेटा ऐरे को खोजें। यदि डेटा सरणी में मान नहीं मिलता है तो खोज विफल हो जाती है।
- यदि खोज मान वर्तमान नोड के न्यूनतम मान से कम है तो इसके बाएं उपट्री में खोज जारी रखें। यदि कोई बायाँ उपवृक्ष नहीं है तो खोज विफल हो जाती है।
- यदि खोज मान वर्तमान नोड के अधिकतम मान से अधिक है तो उसके दाएँ उपवृक्ष में खोज जारी रखें। यदि कोई सही उपवृक्ष नहीं है तो खोज विफल हो जाती है।
सम्मिलन
- नए मान के लिए बाउंडिंग नोड खोजें। यदि ऐसा कोई नोड उपस्थित है तो:
- जांचें कि क्या इसके डेटा ऐरे में अभी भी जगह है, यदि हां तो नया मान डालें और समाप्त करें
- यदि कोई स्थान उपलब्ध नहीं है तो नोड के डेटा ऐरे से न्यूनतम मान हटा दें और नया मान डालें। अब उस नोड के लिए सबसे बड़ी निचली सीमा को पकड़कर उस नोड पर आगे बढ़ें जिसमें नया मान डाला गया था। यदि हटाया गया न्यूनतम मान अभी भी वहां फिट बैठता है तो इसे नोड के नए अधिकतम मान के रूप में जोड़ें, अन्यथा इस नोड के लिए नया दायां सबनोड बनाएं।
- यदि कोई बाउंडिंग नोड नहीं मिला तो खोजे गए अंतिम नोड में मान डालें यदि वह अभी भी उसमें फिट बैठता है। इस स्थिति में नया मान या तो नया न्यूनतम या अधिकतम मान बन जाएगा। यदि मान अब फिट नहीं बैठता है तो नया बाएँ या दाएँ सबट्री बनाएँ।
यदि कोई नया नोड जोड़ा गया था तो ट्री को पुनः संतुलित करने की आवश्यकता हो सकती है, जैसा कि नीचे बताया गया है।
विलोपन
- हटाए जाने वाले मान के बाउंडिंग नोड की खोज करें। यदि कोई बाउंडिंग नोड नहीं मिलता है तो समाप्त करें।
- यदि बाउंडिंग नोड में मान नहीं है तो समाप्त करें।
- नोड के डेटा सरणी से मान हटाएं
अब हमें नोड प्रकार के आधार पर अंतर करना होगा:
- आंतरिक नोड:
यदि नोड के डेटा ऐरे में अब तत्वों की न्यूनतम संख्या से कम है तो इस नोड के सबसे बड़े निचले बाउंड मान को उसके डेटा मान पर ले जाएं। आधे पत्ते या पत्ते के नोड के लिए निम्नलिखित दो चरणों में से एक के साथ आगे बढ़ें जिससे मान हटा दिया गया था।
- लसीका नोड:
यदि यह डेटा सरणी में एकमात्र तत्व था तो नोड हटा दें। यदि आवश्यक हो तो ट्री को पुनः संतुलित करें।
- आधा पत्ता नोड:
यदि नोड के डेटा ऐरे को ओवरफ्लो के बिना उसके लीफ के डेटा ऐरे के साथ मर्ज किया जा सकता है तो ऐसा करें और लीफ नोड को हटा दें। यदि आवश्यक हो तो ट्री को पुनः संतुलित करें।
रोटेशन और संतुलन
एक टी-ट्री को अंतर्निहित स्व-संतुलन द्विआधारी खोज ट्री के शीर्ष पर लागू किया गया है। विशेष रूप से, लेहमैन और कैरी का लेख टी-ट्री को एवीएल ट्री की तरह संतुलित करने का वर्णन करता है: यह तब संतुलन से बाहर हो जाता है जब नोड के चाइल्ड ट्री की ऊंचाई में कम से कम दो स्तर का अंतर होता है। यह किसी नोड को सम्मिलित करने या हटाने के बाद हो सकता है। सम्मिलन या विलोपन के बाद, ट्री को पत्ती से जड़ तक स्कैन किया जाता है। यदि असंतुलन पाया जाता है, तो ट्री का रोटेशन या रोटेशन की जोड़ी का प्रदर्शन किया जाता है, जो पूरे ट्री को संतुलित करने की गारंटी देता है।
जब रोटेशन के परिणामस्वरूप आंतरिक नोड में न्यूनतम संख्या से कम आइटम होते हैं, तो नोड के नए बच्चे (रेन) से आइटम आंतरिक नोड में ले जाया जाता है।
प्रदर्शन और भंडारण
हालाँकि प्रदर्शन लाभों के कारण टी-ट्री का उपयोग एक बार मुख्य-मेमोरी डेटाबेस के लिए व्यापक रूप से किया जाता था, बहुत बड़े मुख्य-मेमोरी डेटाबेस के लिए हाल के रुझानों ने प्रावधान लागत पर अधिक जोर दिया है। आधुनिक एनओएसक्यूएल डेटाबेस सिस्टम अक्सर खरबों रिकॉर्ड संग्रहीत करते हैं, यहां तक कि एकल सूचकांक को संग्रहीत करने की मेमोरी लागत जिसमें वास्तविक मान सम्मिलित होते हैं, दसियों या यहां तक कि सैकड़ों टेराबाइट्स से अधिक हो सकते हैं।
यह भी देखें
- ट्री (ग्राफ़ सिद्धांत)
- ट्री (सेट सिद्धांत)
- ट्री संरचना
- घातांकीय ट्री
अन्य ट्री
- बी-ट्री (2-3 ट्री, 2-3-4 ट्री, बी+ ट्री, बी*-ट्री, यूबी-ट्री)
- नाचता हुआ ट्री
- संलयन ट्री
- के-डी ट्री
- ऑक्ट्री
- क्वाडट्री
- आर-ट्री
- मूलांक ट्री
- शीर्ष ट्री
संदर्भ
- ↑ 1.0 1.1 1.2 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.
