جلسه هفتم داده‌های حجیم: جستجوی بازه‌ای

3-sided

راه اول: جاروب صفحه

ایراد: ایستا

پویای آن در مدل RAM ممکن است.

priority search tree (مدل RAM): بر حسب x درخت دودویی جستجو است و بر حسب y هرم است. موقع پرس‌و‌جو اول روی y بعد روی x جستجو می‌کنیم.

مدل IO:

بلوک بندی کنیم.

Base-tree: Weight-balanced B-tree with branching factor B/4 & leaf parameter B on x

Bتای اول هر فرزند را نگه دارد.

برای حالت ایستا persistent B-tree

فضای خطی

برای حذف از ساخت دوباره زیردرخت استفاده کنید.

برای درج به درخت اضافه کنید و rebalance کنید.

برای تجزیه باید ریشه را به روز کنید.

پیدا کردن B تای اول باعث می‌شود زمان بر حسب تعداد اعداد زیر درخت است.