इस खंड में हम बताते हैं कि कैसे (2,4)-ट्रीज़ लेवल लिंक्स (Level Links) के परिचय द्वारा कुशल फिंगर खोज का समर्थन कर सकती हैं। इस खंड में समझाए गए विचार (a, b)-ट्रीज़ नामक ऊंचाई-संतुलित ट्रीज़ (Height-balanced Trees) के अधिक सामान्य वर्ग पर भी लागू होते हैं, जहां b ≥ 2a।
(2,4)-ट्री को एक ऊंचाई-संतुलित खोज ट्री (Height-balanced Search Tree) के रूप में परिभाषित किया जाता है जहां सभी लीफ की समान गहराई (Depth) होती है और सभी आंतरिक नोड्स (Internal Nodes) की डिग्री दो, तीन या चार होती है। एलिमेंट्स लीफ पर स्टोर किए जाते हैं, और आंतरिक नोड्स केवल खोज को निर्देशित करने के लिए सर्च की (Search Keys) स्टोर करते हैं। चूंकि प्रत्येक आंतरिक नोड की डिग्री कम से कम दो होती है, यह निम्नलिखित है कि (2,4)-ट्री की ऊंचाई O(log n) होती है और O(log n) समय में खोज का समर्थन करती है। (2,4)-ट्री की एक महत्वपूर्ण विशेषता यह है कि फिंगर द्वारा प्रदान किए गए इंसर्शन और डिलीशन परिशोधित O(1) समय लेते हैं (यह गुण (2,3)-ट्रीज़ द्वारा साझा नहीं किया जाता, जहां m इंसर्शन और डिलीशन के अनुक्रम मौजूद हैं जिन्हें Θ(m log m) समय की आवश्यकता होती है)। इसके अलावा m लीफ वाली (2,4)-ट्री को m1 और m2 आकार के दो ट्री में परिशोधित O(log min(m1, m2)) समय में विभाजित किया जा सकता है। इसी तरह m1 और m2 आकार की दो (2,4)-ट्रीज़ को परिशोधित O(log min(m1, m2)) समय में जोड़ा (Concatenated) जा सकता है।
फिंगर खोज का समर्थन करने के लिए, (2,4)-ट्रीज़ को लेवल लिंक्स के साथ संवर्धित (Augmented) किया जाता है, जैसे कि समान गहराई वाले सभी नोड्स एक डबल लिंक्ड लिस्ट (Doubly Linked List) में एक साथ जुड़े होते हैं। निम्न आकृति लेवल लिंक्स के साथ संवर्धित (2,4)-ट्री को दर्शाती है। याद रखें सभी एज बाइडायरेक्टेड लिंक्स (Bidirected Links) दर्शाते हैं। अतिरिक्त लेवल लिंक्स को इंसर्शन, डिलीशन, स्प्लिट और जॉइन के दौरान बनाए रखना सीधा है।
X से Y तक फिंगर खोज करने के लिए हम पहले जांचते हैं कि Y, X के बाईं या दाईं ओर है। बिना किसी हानि के मान लें कि Y, X के दाईं ओर है। हम फिर X से रूट की ओर पथ पर जाते हुए नोड्स V और उनके दाएं पड़ोसियों (Right Neighbours) की जांच करते हैं जब तक कि यह स्थापित न हो जाए कि Y, V या V के दाएं पड़ोसी में रूटेड सबट्री के भीतर समाहित है। ऊपर की खोज तब समाप्त होती है और अधिकतम दो नीचे की खोज (Downward Searches) क्रमशः V और/या V के दाएं पड़ोसी से y के लिए शुरू होती है। चित्र 1 में j से t तक फिंगर खोज के दौरान अनुसरण किए गए पॉइंटर्स को मोटी रेखाओं द्वारा दर्शाया गया है।
O(log d) खोज समय इस अवलोकन से आता है कि यदि हम ऊपर की खोज को नोड V के पैरेंट तक आगे बढ़ाते हैं तो Y, V' के दाएं पड़ोसी के बाएं-सबसे सबट्री के दाईं ओर है, यानी d कम से कम अब तक पहुंची ऊंचाई में घातीय (Exponential) है।
चित्र 1 में हम "l n" लेबल वाले आंतरिक नोड से "h" लेबल वाले नोड पर आगे बढ़ते हैं क्योंकि "s" से हम जानते हैं कि Y, "q r" नोड में रूटेड सबट्री के दाईं ओर है।
लेवल लिंक्ड (2,4)-ट्रीज़ के लिए निर्माण सीधे लेवल लिंक्ड (a, b)-ट्रीज़ तक सामान्यीकृत होता है जिन्हें एक्सटर्नल मेमोरी (External Memory) में लागू किया जा सकता है। a = 2b और b का चयन करके जैसे कि एक आंतरिक नोड एक्सटर्नल मेमोरी में एक ब्लॉक में फिट हो, हम एक्सटर्नल मेमोरी फिंगर सर्च ट्रीज़ प्राप्त करते हैं जो O(1) मेमोरी ट्रांसफर में इंसर्शन और डिलीशन का समर्थन करते हैं, और O(log_b n) मेमोरी ट्रांसफर के साथ फिंगर खोज।
