درخت جستجو در مدل I/O: قسمت دوم: ابعاد بالاتر (جلسه چهارم داده‌های حجیم)
در این جلسه هدف جواب دادن کوئری‌های پیدا کردن نقاط در بازه‌ی [x1,x2]*[y1,y2] است.
دو بعدی:
یک BST روی x می‌سازیم و در هر گره‌ی آن یک BST روی y می‌سازیم.
ایراد:
زمانی که می‌خواهیم درخت را روی بعد x آن متوازن کنیم، داده‌ساختارهای روی بعد y باید از اول ساخته شوند.
برای اینکه به حالت بهینه برسیم باید هزینه‌ی متوازن کردن با مجموع وزن گره‌های زیرمجموعه‌ی آن گره متناسب باشد.
درخت BB[alpha]-tree
نسبت وزن فرزند چپ و راست یک گره بین alpha,1-alpha است (alpha < 1). پس ارتفاع لگاریتم N است.
برای متوازن کردن از چرخش استفاده می‌کنیم. پیاده‌سازی آن در مدل I/O سخت است. ولی مشکل هزینه‌ی بعد دوم در متوازن کردن را حل می‌کند.
Weigh-balanced B-tree
ترکیب BB[alpha]-tree و B-tree است. به جای اینکه محدودیت درجه داشته باشیم، محدودیت وزن داریم. متوازن کردن آن مشابه B-tree با ادغام و جداسازی گره‌ها انجام می‌شود.
دو پارامتر b و k برای این درخت وجود دارد که برگها بین k/4,k عنصر دارند و گره‌های سطح l وزن بین b^l * k, 1/4*b^l *k دارند. (اصلاحیه: در پست جلسه‌ی سوم درخت (a,b) ریشه بین 2,b عنصر دارد استثناً) ریشه هم باید بیشتر از یک فرزند داشته باشد. در نتیجه‌ی این محدودیت وزن گره‌های میانی بین 1/4b,4b فرزند دارند.
بقیه (حذف و درج) مشابه قبل.
persistent tree:
می‌خواهیم امکان درج و حذف (update) روی داده‌ساختار فعلی داشته باشیم و بتوانیم برای بازه‌ای در گذشته هم پرس‌و‌جو داشته باشیم.
راه حل بدیهی: نگه داشتن یک نسخه از ساختمان داده به ازای هر زمان. (اضافه کردن یک بعد به ساختمان داده برای زمان آن)
ایراد: به روز رسانی زمانی معادل خواندن همه‌ی داده‌ها لازم دارد. زمان ساختمان داده هم به طور مشابه متناسب با خواندن توان دوم اندازه ورودی می‌شود.
راه حل بهتر: به هر عنصر یک بازه‌ی زمانی اضافه کنیم. می‌شود این بازه‌های وجود را با تکرار یک عنصر طوری ساخت که یک B-tree روی عناصر زنده داشته باشیم. برای این کار باید بلوک‌هایی که تعداد عناصر حذف شده (که آنها را فقط علامت می‌زنیم چون بعداً برای کوئری به گذشته لازمشان خواهیم داشت) زیادی دارند را به عنوان حذف شده علامت بزنیم. برای این کار بقیه عناصر بلوک حذف شده را به عنوان عنصر جدید درج می‌کنیم. وقتی یک بلوک حذف می‌شود، در پدر آن اشاره‌گرش را هم به عنوان حذف شده علامت می‌زنیم.
امیر