एक डिस्क फ़ाइल में Btrees को सहेज रहा है और इसे

Question

पढ़ता है मैं डिस्क फ़ाइल में एक Btree (सुनिश्चित नहीं है कि एक बाइनरी एक) को सहेजना चाहता हूं। और फिर इसे स्मृति में पढ़ें। कुछ लेवल-ऑर्डर ट्रैवर्सल बाइनरी बीटी के लिए एक अच्छा तरीका हो सकता है। लेकिन यदि यह एक बाइनरी नहीं है। मैं पत्ती के पत्थर से बीटी को मेमोरी में रूटनोड में बना देता हूं। मेरा मानना ​​है कि मुझे डिस्क फ़ाइल में कुछ संरचनाओं को परिभाषित करना है और पेड़ नोड्स को आउटपुट करना है। फ़ाइल में नोड की पहचान करने के लिए कुछ अतिरिक्त टैग का उपयोग कर? ट्रैवर्सल कैसे करें यहां मुख्य समस्या हो सकती है। मैंने नोड्स और पॉइंटर्स को सहेजने के लिए एक अच्छा तरीका नहीं बताया है। और फिर इसे पढ़ें। स्मृति में पेड़ rconstruct। कोई अच्छा विचार? बहुत बहुत धन्यवाद।

Answer 1

तुम सच में कुछ इसी तरह करना चाहते हैं, तो आप बस प्रत्येक नोड एक आईडी पर निर्दिष्ट करेंगे और उस प्रारूप में नोड्स बचा सकते हैं:

[नोड आईडी मान छोड़ दिया नोड आईडी सही नोड-id]

और फिर एक चौड़ाई वाली पहली खोज के साथ पेड़ पर जाएं।

आप पेड़ को फिर से संगठित, एक नक्शा ID-> नोड बनाने और उसके बाद करना चाहते हैं फ़ाइल को पढ़ने पिछड़े: तो, जब आप एक रिकॉर्ड पढ़ा है,, नोड बनाने के मानचित्र में पंजीकृत और बाईं आवंटित और मानचित्र से नोड्स लाने के लिए सही नोड।

Answer 2

प्रत्येक नोड के लिए कुछ डेटा संरचना परिभाषित करती है जो आपके लिए नोड के समान जानकारी रखती है और उस संरचना को अतिरिक्त फ़ील्ड में जोड़ती है जो आपके लिए अगले बेटे के लिए फ़ाइल में ऑफ़सेट चिह्नित करेगी। और उस संरचना के शीर्ष क्षेत्र को वास्तविक आकार बनाएं, क्योंकि आप नहीं जानते कि अब आप किस प्रकार का पेड़ देख रहे हैं। अब फाइल पर कूदकर आप अपने पेड़ का पुनर्निर्माण करने में सक्षम होंगे। मुझे यकीन है कि मेरा समाधान अंतिम नहीं है, लेकिन मुझे उम्मीद है कि यह आपके लिए अच्छा सितारा बिंदु हो सकता है।

Answer 3

आप Protocol Buffers देख सकते हैं। वे कॉम्पैक्ट, बाइनरी, एक्स्टेंसिबल, पढ़ने और लिखने में आसान हैं, और सी ++, जावा और पायथन (साथ ही साथ अन्य भाषाओं में तीसरे पक्ष के कार्यान्वयन) में उपलब्ध हैं।

आप बीटी नोड के लिए प्रोटोकॉल बफर संदेश को परिभाषित कर सकते हैं, जिसमें बच्चे नोड्स के लिए फ़ाइल ऑफसेट हैं, और बस इसे स्पष्ट तरीके से डिस्क पर क्रमबद्ध करें।

Answer 4

बी-पेड़ के लिए सामान्य तकनीक यह सुनिश्चित करना है कि नोड का आकार डिस्क के ब्लॉक आकार के बराबर है, और डिस्क फ़ाइल को mmap। आप यह निर्दिष्ट नहीं करते कि आप किस प्रोग्रामिंग भाषा में काम कर रहे हैं, इसलिए यह सी में एक कलाकार के रूप में सरल हो सकता है, या कुछ जटिल हो सकता है जैसे कि java.nio.IntBuffer को लपेटने के लिए फ्लाईवेट ऑब्जेक्ट्स बनाना। किसी भी तरह से, बी-पेड़ का अधिक लाभ यह है कि आपको इसे एक साथ लोड करने की ज़रूरत नहीं है, लेकिन इसके आसपास काफी कुशलता से कूद सकते हैं।