এই সেকশনে আমরা ব্যাখ্যা করব কিভাবে (2,4)-ট্রি কার্যকর ফিংগার সার্চ সাপোর্ট করতে পারে লেভেল লিংক এর পরিচয় দিয়ে। এই সেকশনে ব্যাখ্যা করা আইডিয়াগুলো আরও জেনারেল ক্লাস অফ হাইট-ব্যালেন্সড ট্রি যেনে (a, b)-ট্রি-র জন্যও অ্যাপ্লাই করা হয়, b ≥ 2a-র জন্য।
একটি (2,4)-ট্রি হলো একটি হাইট-ব্যালেন্সড সার্চ ট্রি যেখানে সকল লিফ একই ডেপথে থাকে এবং সকল ইন্টারন্যাল নোড ডিগ্রি দুই, তিন বা চার। এলিমেন্টগুলো লিফে স্টোর করা থাকে, এবং ইন্টারন্যাল নোড শুধু সার্চ কী স্টোর করে সার্চ গাইড করতে। যেহেতু প্রতিটি ইন্টারন্যাল নোডের ডিগ্রি কমপক্ষে দুই, তাই ফলো করে যে একটি (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)) টাইমে। একইভাবে দুটি (2,4)-ট্রি সাইজ m1 এবং m2-এ জয়েন (কনক্যাটেনেটেড) করা যায় এমরটাইজড O(log min(m1, m2)) টাইমে।
ফিংগার সার্চ সাপোর্ট করতে, (2,4)-ট্রি অগমেন্ট করা হয় লেভেল লিংকসহ, যাতে সমান ডেপথের সকল নোড একসাথে লিংক করা থাকে একটি ডাবলি লিংকড লিস্টে। নিচের ফিগারটি একটি (2,4)-ট্রি দেখাচ্ছে যা লেভেল লিংকসহ অগমেন্টেড। মনে রাখবেন সকল এজ বাইডিরেক্টেড লিংক রিপ্রেজেন্ট করে। অতিরিক্ত লেভেল লিংকগুলো সহজে প্রিজার্ভ করা যায় ইনসার্শন, ডিলিশন, স্প্লিট এবং জয়েন অফ (2,4)-ট্রির সময়।
X থেকে Y-এ একটি ফিংগার সার্চ সম্পন্ন করতে আমরা প্রথমে চেক করি Y X-র বামে কি ডানে। ধরে নেওয়া হয় লস অফ জেনারেলিটি যে Y X-র ডানে। তারপর আমরা X থেকে রুট দিকে পাথ ট্রভার্স করি নোড V এবং তাদের ডান নেইবারের ইনস্পেক্ট করে যতক্ষণ না সেটি הוק এস্টাবলিশড যে Y কন্টেইন করা থাকে V-র সাবট্রি-তে রুটেড বা V-র ডান নেইবারের। উপওয়ার্ডস সার্চ তখন টার্মিনেট করা হয় এবং সর্বোচ্চ দুটি ডাউনওয়ার্ডস সার্চ y-র জন্য শুরু করা হয় রেসপেক্টিভলি V এবং/অথবা V-র ডান নেইবারের। ফিগার 1-এ j থেকে t-এ ফিংগার সার্চের সময় ফলো করা পয়েন্টারগুলো থিক লাইন দ্বারা ডেনোট করা হয়েছে।
O(log d) সার্চ টাইম ফলো করে এই অবজার্ভেশন থেকে যে যদি আমরা উপওয়ার্ডস সার্চ এডভ্যান্স করি নোড V-র প্যারেন্টে তবে Y V′s ডান নেইবারের লেফটমোস্ট সাবট্রির ডানে থাকে, অর্থাৎ d কমপক্ষে এক্সপোনেনশিয়াল হাইটে যা এখন পর্যন্ত পৌঁছানো হয়েছে।
ফিগার 1-এ আমরা ইন্টারন্যাল নোড "l n" থেকে "h" নোডে এডভ্যান্স করি কারণ "s" থেকে আমরা জানি যে Y "q r" নোডে রুটেড সাবট্রির ডানে।
লেভেল লিংকড (2,4)-ট্রির কনস্ট্রাকশন সরাসরি জেনারেলাইজ হয় লেভেল লিংকড (a, b)-ট্রিতে যেটি এক্সটার্নাল মেমরিতে বাস্তবায়িত হতে পারে। a = 2b এবং b সিলেক্ট করে যাতে একটি ইন্টারন্যাল নোড এক ব্লকে ফিট করে এক্সটার্নাল মেমরিতে, আমরা অর্জন করি এক্সটার্নাল মেমরি ফিংগার সার্চ ট্রি ইনসার্শন এবং ডিলিশন O(1) মেমরি ট্রান্সফারে সাপোর্ট করে, এবং ফিংগার সার্চ O(logb n) মেমরি ট্রান্সফারে।
