ट्री बनाम बी + पेड़

Question

ट्री और बी + पेड़ इंडेक्सिंग लेक्सिकोग्राफिकली सॉर्ट स्ट्रिंग्स [कुछ अरबों के क्रम में] के लिए तुलना कैसे करता है? इसे रेंज क्वेरीज़ का भी समर्थन करना चाहिए।

perf से। साथ ही कार्यान्वयन जटिलता बिंदु दृष्टिकोण।

Answer 1

मैं कहूंगा कि यह रेंज द्वारा आपके मतलब पर निर्भर करता है।

यदि आपकी सीमा के रूप में व्यक्त की गई है तो से शुरू होने वाले सभी शब्द, तो Trie सही विकल्प है जो मैं कहूंगा। दूसरी ओर, Trieजैसे अनुरोधों के लिए नहीं हैं XX और ZZ के बीच सभी शब्द।

ध्यान दें कि B+ Tree का ब्रांचिंग कारक इसके प्रदर्शन (मध्यस्थ नोड्स की संख्या) को प्रभावित करता है। यदि h पेड़ की ऊंचाई है, तो n _{अधिकतम} ~~ बी ^एच। इसलिए एच ~~ लॉग (एन _{अधिकतम})/लॉग (बी)।

n = 1 000 000 000 और b = 100 के साथ, हमारे पास h ~~ 5 है। इसलिए इसका मतलब रूट से पत्ते तक जाने के लिए केवल 5 सूचक डीफरेंसिंग है। यह Trie से अधिक कैश-अनुकूल है।

अंत में, B+ TreeTrie से लागू करने के लिए स्वीकार्य रूप से अधिक कठिन है: यह Red-Black Tree जटिलता के स्तर पर अधिक है।

Answer 2

विकिपीडिया में कुछ एल्गोरिदमिक जटिलता तथ्य हैं: B+ tree (सेक्शन लक्षण), Trie (दुर्भाग्यवश पूरे लेख में फैला हुआ है)। उम्मीद है की वो मदद करदे।

Answer 3

अपने वास्तविक कार्य पर निर्भर करता है:

• आप पूरे सबट्री प्राप्त करना चाहते हैं, एक बी + ट्री यह अंतरिक्ष कुशल है, क्योंकि तुम्हारा सबसे अच्छा विकल्प है।
• लेकिन अगर आप एक substree से पहले N बच्चों पाने के लिए चाहते हैं, तो एक Trie सबसे अच्छा विकल्प है क्योंकि आप बस एक बी + ट्री परिदृश्य की तुलना में कम नोड्स की यात्रा है।
• सबसे लोकप्रिय कार्य जो द्वारा अच्छी तरह से संभाला जाता है Trieशब्द उपसर्ग पूर्णता है।