टी-ट्री
कंप्यूटर विज्ञान में टी-ट्री एक प्रकार की द्विआधारी वृक्ष डेटा संरचना है जिसका उपयोग मुख्य मेमोरी डेटाबेस|मुख्य-मेमोरी डेटाबेस, जैसे डेटाब्लिट्ज़, eXtremeDB, MySQL क्लस्टर, टाइम्सटेन और मोबाइललाइट द्वारा किया जाता है।
टी-ट्री ऊंचाई-संतुलित ट्री इंडेक्स ट्री डेटा संरचना है जो मामलों के लिए अनुकूलित है जहां इंडेक्स और वास्तविक डेटा दोनों को पूरी तरह से मेमोरी में रखा जाता है, जैसे बी-वृक्ष एक इंडेक्स संरचना है जो हार्ड डिस्क जैसे ब्लॉक ओरिएंटेड सेकेंडरी स्टोरेज डिवाइस पर स्टोरेज के लिए अनुकूलित होती है। टी-ट्रीज़ एवीएल पेड़ जैसे इन-मेमोरी ट्री संरचनाओं के प्रदर्शन लाभ प्राप्त करना चाहते हैं, जबकि बड़े भंडारण स्थान ओवरहेड से बचते हैं जो उनके लिए सामान्य है।
टी-ट्री इंडेक्स ट्री नोड्स के भीतर अनुक्रमित डेटा फ़ील्ड की प्रतियां स्वयं नहीं रखते हैं। इसके बजाय, वे इस तथ्य का लाभ उठाते हैं कि वास्तविक डेटा हमेशा इंडेक्स के साथ मुख्य मेमोरी में होता है ताकि उनमें केवल वास्तविक डेटा फ़ील्ड के पॉइंटर्स हों।
टी-ट्री में 'टी' मूल पेपर में नोड डेटा संरचनाओं के आकार को संदर्भित करता है जिसने पहली बार इस प्रकार के सूचकांक का वर्णन किया था।[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.
