इस खंड में हम बताते हैं कि कैसे (2,4) -पेड़ स्तरीय लिंक की शुरूआत द्वारा कुशल उंगली खोजों का समर्थन कर सकते हैं। इस खंड में बताए गए विचार ऊंचाई-संतुलित पेड़ों के अधिक सामान्य वर्ग के लिए भी लागू होते हैं, जिन्हें (ए, बी) -ट्री, बी ≥ 2 ए के लिए दर्शाया गया है।
ए (2,4) -ट्री को ऊंचाई-संतुलित खोज पेड़ के रूप में परिभाषित किया जाता है जहां सभी पत्तियों की गहराई समान होती है और सभी आंतरिक नोड्स में दो, तीन या चार डिग्री होती है। तत्वों को पत्तियों पर संग्रहीत किया जाता है, और आंतरिक नोड्स केवल खोजों को निर्देशित करने के लिए खोज कुंजी संग्रहीत करते हैं। चूंकि प्रत्येक आंतरिक नोड में कम से कम दो डिग्री होती है, यह इस प्रकार है कि एक (2,4) -ट्री की ऊंचाई ओ (लॉग एन) है और ओ (लॉग एन) समय में खोजों का समर्थन करता है। (2,4)-पेड़ों की एक महत्वपूर्ण संपत्ति यह है कि एक उंगली द्वारा प्रदान किया गया सम्मिलन और विलोपन ओ (1) समय को परिशोधित करता है (यह संपत्ति (2, 3) -ट्री द्वारा साझा नहीं की जाती है, जहां एम सम्मिलन के अनुक्रम मौजूद हैं और हटाने के लिए (m log m) समय की आवश्यकता होती है)। इसके अलावा एक (2,4) - एम पत्तियों वाले पेड़ को एम 1 और एम 2 आकार के दो पेड़ों में परिशोधित ओ (लॉग मिन (एम 1, एम 2)) समय में विभाजित किया जा सकता है। इसी तरह एम1 और एम2 आकार के दो (2,4)-पेड़ों को परिशोधित ओ (लॉग मिनट (एम 1, एम 2)) समय में जोड़ा जा सकता है।
उंगलियों की खोजों का समर्थन करने के लिए, (2,4) - पेड़ों को स्तर लिंक के साथ संवर्धित किया जाता है, जैसे कि समान गहराई वाले सभी नोड्स एक साथ डबल लिंक्ड सूची में जुड़े होते हैं। निम्न आंकड़ा स्तर लिंक के साथ संवर्धित एक (2,4) -ट्री प्रदर्शित करता है। याद रखें कि सभी किनारे द्विदिश लिंक का प्रतिनिधित्व करते हैं। अतिरिक्त स्तर के लिंक्स (2,4)-पेड़ों के सम्मिलन, विलोपन, विभाजन और जुड़ने के दौरान संरक्षित करने के लिए सरल हैं।
X से Y तक एक उंगली की खोज को पूरा करने के लिए, हम पहले जांचते हैं कि Y, X के बाएं या दाएं है। व्यापकता के नुकसान के बिना मान लें कि Y, X के दाईं ओर है। हम जांच करते समय X से रूट की ओर जाते हैं। पथ और उनके दाहिने पड़ोसियों पर नोड्स वी जब तक यह स्थापित नहीं हो जाता है कि वाई वी या वी के दाहिने पड़ोसी पर निहित उपट्री के भीतर निहित है। ऊर्ध्वगामी खोज को फिर समाप्त कर दिया जाता है और y के लिए अधिकतम दो अधोमुखी खोज क्रमशः V और/या V के दाहिने पड़ोसी पर शुरू की जाती है। चित्र 1 में j से t तक उंगली की खोज के दौरान जिन बिंदुओं का अनुसरण किया जाता है उन्हें मोटी रेखाओं द्वारा दर्शाया जाता है।
O(log d) खोज समय इस अवलोकन का अनुसरण करता है कि यदि हम नोड V के माता-पिता के लिए ऊपर की खोज को आगे बढ़ाते हैं तो Y, V′ के दाहिने पड़ोसी के सबसे बाएं उपप्रकार के दाईं ओर है, अर्थात d में कम से कम घातीय है ऊंचाई अब तक पहुंच गई है।
चित्र 1 में हम "l n" लेबल वाले आंतरिक नोड से "h" लेबल वाले नोड की ओर बढ़ते हैं क्योंकि "s" से हम जानते हैं कि Y नोड "q r" पर सबट्रीरूर्ड के दाईं ओर है।
लेवल लिंक्ड (2,4)-ट्रीज़ के लिए कंस्ट्रक्शन सीधे लेवल लिंक्ड (ए, बी) -ट्रीज़ को सामान्यीकृत करता है जिसे बाहरी मेमोरी में लागू किया जा सकता है। ए =2 बी और बी का चयन करके जैसे कि एक आंतरिक नोड बाहरी मेमोरी में एक ब्लॉक में फिट बैठता है, हम ओ (1) मेमोरी ट्रांसफर में सम्मिलन और विलोपन का समर्थन करने वाले बाहरी मेमोरी फिंगर सर्च ट्री प्राप्त करते हैं, और ओ (लॉगब एन) मेमोरी ट्रांसफर के साथ फिंगर सर्च करते हैं। ।