جلسه ششم داده‌های حجیم: درخت بازه‌ها
۱-بعدی: هدف پیدا کردن بازه‌هایی است که شامل یک نقطه‌ی داده شده هستند.
اگر از B-tree روی دو سر بازه‌ها استفاده کنیم به زمان O(log_B N) می‌رسیم.
ایراد: باید به ازای هر بازه یک کوئری بزنیم! O(N log_B N/B) می‌شود.
راه حل: استفاده از persistent B-tree: با جاروب از چپ به راست، فرض می‌کنیم هر بازه زمان وجود یک چیز است و با شروع بازه آن را به درخت اضافه می‌کنیم و با پایان بازه آن را حذف می‌کنیم.
ایراد: نمی‌توان پس از یک بار پردازش بازه اضافه کرد. (چون درخت ایستا است.)
راه حل: از درخت بازه استفاده می‌کنیم.
درخت بازه معمولی (مدل RAM):
برای این کار سر بازه‌ها را به صورت نقطه در نظر می‌گیریم. میانه‌ی این نقاط را پیدا می‌کنیم و ریشه می‌گذاریم و بر اساس آن دو لیست راست و چپ را می‌سازیم. بازگشتی بقیه درخت را می‌سازیم.
فضا: خطی، زمان به روز رسانی: O( log n)
پرس و جو: در هر گره x را با نقطه‌ی آن مقایسه می‌کنیم، بر اساس آن به لیست راست یا چپ (هر کدام که شامل x است) مراجعه می‌کنیم و آن را پیمایش می‌کنیم. اگر به یک بازه‌ی غیرشامل آن نقطه (x) برسیم، بازگشتی مسأله را حل می‌کنیم وگرنه کل آن گره را گزارش می‌کنیم.
درخت بازه در مدل I/O:
درخت را بلوک بندی می‌کنیم و از B-tree برای نگه‌داشتن لیست‌های درون گره‌ها استفاده می‌کنیم.
ایراد: ممکن است مجبور شویم O(log N) تا I/O بزنیم در حالتی که تعداد بازه‌های متقاطع در هر گره کم (یا صفر) باشد.
راه حل: درجه‌ی رأسهای را رادیکال B کنیم. با این کار در هر گره B تا بازه داریم (شروع و پایان آنها رادیکال B حالت دارد). با این کار به جای اینکه به O(log B) تا بازه نگاه کنیم، به ۲ تا بازه نگاه می‌کنیم. (چون قبلاً باید بین کل گره‌های درون بلوک درخت جستجو می‌کردیم الآن فقط در لیست زیربازه‌ها نگاه می‌کنیم.
همان طور که در قسمت ۴ گفتیم، چون در هر گره‌ی این درخت یک داده‌ساختار ثانویه هم دارد ذخیره می‌شود، باید از Weighted B-tree استفاده کنیم.
برای گره‌های با تعداد عنصر کم از persistent B-tree استفاده می‌کنیم.
زمان کوئری در لیست یک گره چون B تا زیربازه داریم، O(B/B log_B B+T_v/B) است که یعنی O(1+T_v/B) که T_v تعداد جوابها است.
فضای کل خطی خواهد بود.
چون در هر گره از مرتبه‌های چندجمله‌ای بر حسب B عنصر داریم، زمانها تغییر نمی‌کنند. پس از B درج در B-tree یک لیست، آن را دوباره می‌سازیم. (چون هزینه‌اش کمتر می‌شود).
ممکن است مجبور شویم از داده‌ساختار زیرلیست‌ها به داده‌ساختار برای مقادیر کوچک عناصر را جابه‌جا کنیم. (به B برسد به multislab list (زیرلیست‌ها) می‌بریم و به B/2 برسد به underflow structure (برای مقادیر کوچک) می‌بریم.)
متوازن کردن آن بر اساس وزن گره (تعداد عناصر در زیردرخت با ریشه آن گره) است و مثل Weighted B-tree انجام می‌شود. فقط برای بازه‌ها، باید آنها را دوباره تقسیم کنیم و آن multislab listهایی که کامل در یکی می‌افتند نگه می‌داریم و بقیه را دیگر لازم نداریم. آنهایی که جداست را با یک پیمایش می‌شود پیدا کرد. باید پدر این گره را هم لیست بازه‌هایش را به روز کنیم چون فرزندان آن تغییر کرده‌اند که این کار را از روی تقسیم بازه‌ها انجام می‌دهیم. برای بازه‌های جدید بعد از تقسیم کردن دوباره multislab list می‌سازیم.
