جلسه سوم داده‌های حجیم (درخت جستجو در مدل I/O)

اگر مثل حالت معمولی یک BST بسازیم زمان متناسب با log N می‌شود که زیاد است. ما می‌خواهیم به log_B N برسانیمش. (احتمالاً چون با روشی مثل آخر جلسه‌ی قبل می‌شود ثابت کرد که کران پایینش این است.)

برای این کار از روشی به نام BFS Blocking استفاده می‌کنیم که همان طور که از اسمش پیداست مشابه BFS درخت را بلوک‌بندی می‌کند. این درخت جواب بهینه را به ما می‌دهد که O(log_B N) برای کوئری (ارتفاع درخت) است و برای جستجوی یک بازه و گزارش کردن نقاط آن O( log_B N+ T/B) است. (T تعداد عناصر بازه = اندازه خروجی)

ایراد: برای به روز رسانی این درخت باید مثل AVL-tree زحمت زیادی کشید. در ضمن باید برگ‌ها هم بلوک‌بندی شده باشند (داده‌های آنها پشت سر هم باشد).

راه حل: استفاده از B-tree

به جای اینکه بیایم با متوازن کردن ارتفاع درخت را درست نگه داریم، کافی است روی درجه‌ی خروجی (تعداد فرزندان هر گره) شرط بگذاریم. چون این دلیل اصلی حفظ شدن ارتفاع درخت در BFS-blocking است. برای این کار قرار می‌دهیم درجه‌ی هر رأس theta(B) باشد. با این کار به B-tree می‌رسیم که عمل متوازن کردن در آن با ادغام یا جداکردن گره‌ها انجام می‌شود ولی همیشه درجه‌ی رأسها از مرتبه‌ی B است.

(a,b)-tree درختی است که در آن گره‌های یک سطح بین a تا b عنصر دارند. پس ارتفاع آن حداکثر O(log_a N) است. اگر a و b از مرتبه‌ی B باشند به همان جواب بهینه می‌رسیم. اما حالا این ساختمان داده‌ی جدید برای اضافه‌کردن و حذف کردن عنصر هم مشکلی ندارد و می‌تواند در همان زمان بهینه به این کوئری‌ها هم جواب بدهد. با ادغام و جدا کردن گره‌های میانی هر وقت که از بازه‌ی a,b خارج می‌شوند.

با تحلیل سرشکنی (amortized) می‌شود مقادیر a,b را پیدا کرد که بین دو ادغام و جداشدن به مقدار لازم فاصله باشد که سرشکن آن O(1) شود. (که چون در هر عمق انجام می‌شود لگاریتمی می‌شود).