درخت تلفیقی

چگونه عمل می‌کند؟

یک درخت ترکیبی اساساً یک B-tree با عوامل شاخه‌ای w1/5 (هر توان کوچک دیگری نیز ممکن است) است که باعث می‌شود ارتفاع درخت از (O(logw n باشد. برای این که به زمان اجرای مطلوب از لحاظ بروزرسانی و پاسخ گویی برسیم، درخت باید توانایی جستجوی یک گره با کلید w1/5 به بالا را در زمان ثابت (O(n داشته باشد. این خواسته ما با روش فشرده سازی "sketching" برآورده می‌شود. در این روش کلیدها به صورتی در می‌آید که در یک machine word جای گیرد. در واقع این روش اجازه می‌دهد که مقایسه‌ها به صورت موازی انجام گیرد. در ادامه این مقاله اجرا در یک static Fusion Tree که پاسخ گویی مطلوب را پشتیبانی می‌کند، توصیف می‌کنیم.

Sketching

Sketching تابعی است که طبق آن هر کلید w بیتی منسوب به یک node شامل k تا کلید است که در k-1 بیت فشرده شده‌است. هر کلید x می‌تواند این‌طور در نظر گرفته شود که یک مسیر کامل در یک درخت دودویی با ارتفاع w، از ریشه تا برگِ مطابق با x است. جهت تمایز دو مسیر کافی است به سر شاخه‌ها نگاه کنیم (محل انشعاب بین دو شاخه، یعنی محل اولین بیتی که دو کلید متفاوت می‌شوند). بدیهی است که k تا مسیر در کنار هم k-1 نقطه انشعاب دارند؛ بنابراین حداکثر k-1 بیت نیاز است تا بتوانیم بین هر جفت از k تا کلید تمایز قائل شویم.
خاصیت مهم تابع sketch این است که ترتیب کلیدها را حفظ می‌کند؛ بنابراین اگر x < y آنگاه (sketch(x) < sketch(y

مقایسه موازی

هدف فشرده سازی که از طریق Sketching به دست می‌آید این است که به تمام کلیدها اجازه دهیم در یک کلمه w بیتی ذخیره شوند. در گره Sketch یک گره، رشته بیتی قرار دارد: (1sketch(x₁)1sketch(x₂)...1sketch(xₖ
می‌توانیم فرض کنیم که تابع sketch دقیقاً از b بیت b ≤ r⁴، سپس هر بلوک از 1 + b ≤ w4/5 استفاده می‌کند و از آن جایی که k ≤ w1/5 کل تعداد بیت‌ها در گره sketch حداکثر w است. یک اشارهٔ مختصر: برای یک رشته بیتی s و عدد صحیح غیر منفی m, sᵐ الحاق m مرتبه s را باخودش نشان می‌دهد. اگر t هم یک رشته بیتی باشد، st الحاق t به s را نشان می‌دهد.
گره sketch جستجوی کلیدها برای هر عدد صحیح b بیتی را امکان‌پذیر می‌سازد. z = (0y)ᵏ قرار می‌دهیم که می‌تواند در زمان ثابتی محاسبه شود (ضرب y در ثابت 0ᵇ1)ᵏ)). توجه کنید که 1sketch(xᵢ) - 0y همواره مثبت است، ولی اگر sketch(xᵢ) ≥ y پیشرو خود را حفظ می‌کند؛ بنابراین می‌توانیم کوچکترین شاخص i را به طوری که sketch(xᵢ) ≥ y باشد به صورت زیر محاسبه کنیم:
1)Z را از گره sketch کم کنید.
۲)بیت‌های مقدار حاصل و ثابت 10ᵇ)ᵏ) را به صورت منطقی و بیت به بیت با هم and کن. این کار همه بیت‌ها به جز بیت پیشرو هر بلوک را پاک می‌کند.
۳)پر ارزش‌ترین بیت نتیجه را پیدا کنید.
4) i را با استفاده از این حقیقت که بیت پیشرو i امین بلوک شاخصی برابر(i(b+1 دارد محاسبه کنید.

Desketching

برای یک صف دلخواه q، مقایسه موازی شاخص i را به نحوی محاسبه می‌کند که (sketch(xᵢ₋₁) ≤ sketch(q) ≤ sketch(xᵢ
متأسفانه، تابع sketch خارج از مجموعه کلیدها به صورت کلی نمی‌تواند مرتبه زمانی اش را نگه دارد؛ بنابراین لزوماً این حالتی نیست که xᵢ₋₁ ≤ q ≤ xᵢ. آنچه که درست است این است که در میان تمام کلیدها، یا xᵢ₋₁ یا xᵢ بزرگ‌ترین پسوند مشترک را با q دارد. این به خاطر این است که هر کلید y با یک پسوند مشترک طولانی‌تر با q تعداد sketch بیت‌های مشترک بیشتری با q داردو بنابراین (sketch(y از هر (sketch(xⱼ ای به (sketch(q نزدیک تر است.
طول بزرگترین پسوند مشترک بین دو عدد صحیح w بیتی a و b می‌تواند با پیدا کردن پرارزش‌ترین بیت xor منطقی بیت به بیت بین a و b در زمان ثابت محاسبه شود. این کار سپس می‌تواند برای پوشاندن تمام پسوندها به جز بزرگ‌ترین پسوند مشترک، به کار رود.
توجه کنید که p دقیقاً جایی را که q از مجموعه کلیدها جدا می‌شود را مشخص می‌کند. اگر بیت بعدی q، ۰ باشد، successor (کوچک‌ترین عدد بزرگ‌تر از q) در زیر درخت p1 قرار دارد و اگر بیت بعدی q، ۱ باشد، آن گاه predecessor (بزرگ‌ترین عدد کوچک‌تر از q) در زیردرخت p0 قرار دارد. این حالت الگوریتم زیر را پیشنهاد می‌کند:
۱. از مقایسه موازی برای پیدا کردن شاخص i استفاده کنید، به طوری که(sketch(xᵢ₋₁) ≤ sketch(q) ≤ sketch(xᵢ
۲. بزرگترین پسوند مشترک p از q و نیز xi-1 یا xᵢ را محاسبه کنید (از هر جفت، آنچه طولانی‌تر است را بگیرید)
3.l-۱ را طول بزرگترین پسوند مشترک p بگیرید
۳٫۱. اگر l امین بیت q، ۰ است، e = p10ʷ⁻ˡ قرار دهید. از مقایسه موازی برای جستجوی successor برای (sketch(e استفاده کنید. این در واقع predecessor برای q است.
۳٫۲. اگر l امین بیت q، ۱ است، e = p10ʷ⁻ˡ قرار دهید. از مقایسه موازی برای جستجوی predecessor برای (sketch(e استفاده کنید. این در واقع successor برای q است.
۴. زمانی که یا predecessor یا successor برای q پیدا شد، محل دقیق q بین مجموعه کلیدها مشخص شده‌است.