मोंगोडब में अनुक्रमण का उपयोग करने का क्रम

MongoDB अनुक्रमण के लिए B-पेड़ का उपयोग करता है, जैसा कि index.cpp . इसका मतलब है कि लुकअप को O(log N) . के रूप में व्यक्त किया जा सकता है जहाँ N दस्तावेज़ों की संख्या है, लेकिन यह O(D) . भी है यदि डी पेड़ की गहराई है (मान लें कि पेड़ कुछ संतुलित है)। डी आमतौर पर बहुत छोटा होता है क्योंकि प्रत्येक नोड में कई बच्चे होंगे।

MongoDB में एक नोड में बच्चों की संख्या लगभग 8192 है (btree.h ) तो कुछ अरब . के साथ एक अनुक्रमणिका दस्तावेज़ केवल 3 स्तरों वाले पेड़ में फिट हो सकते हैं! आप आसानी से महसूस कर सकते हैं कि लॉगरिदम log_2 नहीं है (जैसा कि बाइनरी ट्री में होता है) बल्कि log_8192 होता है, जो बहुत धीरे-धीरे बढ़ता है।

इस वजह से, बी-पेड़ों को आमतौर पर निरंतर-समय लुकअप माना जाता है, O(1) , व्यवहार में।

प्रत्येक नोड में कई बच्चों को रखने का एक और अच्छा कारण यह है कि सूचकांक डिस्क पर संग्रहीत होता है। आप कैश प्रदर्शन में सुधार और डिस्क की तलाश को कम करने के लिए एक नोड के लिए डिस्क ब्लॉक में सभी स्थान का उपयोग करने का प्रयास करना चाहते हैं। बी-पेड़ों का डिस्क प्रदर्शन बहुत अच्छा है क्योंकि आप जो खोज रहे हैं उसे खोजने के लिए आपको केवल बहुत कम नोड्स पर जाने की आवश्यकता है।