چرا درختهای قرمز-سیاه برای ذخیرهسازی دیسک ایدهآل نیستند
درختهای قرمز-سیاه که پیشتر در این مجموعه بحث شد، کارایی عالی O(log n) دست مییابند وقتی داده کاملاً در حافظه اصلی جا میشود، جایی که هر دسترسی گره تقریباً همان مقدار کمی زمان هزینه دارد. اما وقتی داده برای حافظه بزرگ باشد و باید روی دیسک قرار گیرد، یک مدل هزینه کاملاً متفاوت اعمال میشود: خواندن یک بلوک دیسک واحد بهمراتب طولانیتر از هر عملیات درونحافظهای طول میکشد، مشابه از نظر روحی با تفاوتهای تأخیر سلسلهمراتب حافظه که پیشتر در این مجموعه درباره معماری کامپیوتر بحث شد. در این تنظیم، تعداد دسترسیهای دیسک، نه تعداد مقایسهها، بر زمان اجرا غالب است.
ایده اصلی: درختهای پهن و کمعمق
یک B-Tree (درخت B) دسترسیهای دیسک را با کاهش چشمگیر ارتفاع درخت کمینه میکند: بهجای اینکه هر گره فقط ۲ فرزند مانند یک درخت جستجوی دودویی داشته باشد، یک گره درخت B کلیدهای زیادی نگه میدارد و میتواند صدها یا هزاران فرزند داشته باشد، متناسب با اندازه یک بلوک دیسک واحد. این یعنی یک درخت B روی میلیونها کلید ممکن است ارتفاعی فقط ۳ یا ۴ داشته باشد، که نیازمند فقط ۳ یا ۴ خواندن دیسک برای یافتن هر کلید است، در مقایسه با ارتفاع بهمراتب بیشتری که یک درخت دودویی متوازن نیاز داشت.
ویژگیهای رسمی درخت B
یک درخت B با یک Minimum Degree (درجه حداقل) t (t ≥ 2) تعریف میشود، که تعداد کلیدهایی که هر گره میتواند نگه دارد را محدود میکند.
هر گره غیر از ریشه باید
حداقل t-1 کلید داشته باشد (و بنابراین حداقل t فرزند اگر داخلی باشد)
هر گره میتواند حداکثر 2t-1 کلید داشته باشد
(و بنابراین حداکثر 2t فرزند اگر داخلی باشد)
ریشه ممکن است تا 1 کلید داشته باشد
(مگر اینکه درخت خالی باشد)
کلیدها درون یک گره به ترتیب مرتبشده ذخیره میشوند
همه برگها دقیقاً در همان عمق ظاهر میشوند
(درخت همیشه بهطور کامل ارتفاع-متوازن است)هر گره داخلی با k کلید دقیقاً k+1 فرزند دارد، و کلیدها بهعنوان جداکننده عمل میکنند: زیردرخت بین دو کلید پیاپی شامل همه مقادیری است که بین آنها میافتند، که ویژگی درخت-جستجوی-دودویی که پیشتر در این مجموعه بحث شد را به چند فرزند بهازای هر گره تعمیم میدهد.
مثال گره داخلی با 3 کلید (t=2، پس 1-3 کلید مجاز):
[10 | 20 | 30]
/ | | \
c0 c1 c2 c3
c0: همه کلیدها < 10
c1: همه کلیدها بین 10 و 20
c2: همه کلیدها بین 20 و 30
c3: همه کلیدها > 30جستجوی یک درخت B
جستجو، جستجوی درخت-جستجوی-دودویی که پیشتر در این مجموعه بحث شد را تعمیم میدهد: درون هر گره، کلیدهای مرتبشده را اسکن کن (یا جستجوی دودویی انجام بده) تا فرزند درست برای پایینرفتن پیدا شود، سپس بازگشت کن.
B-TREE-SEARCH(x, k):
i = 1
تا زمانی که i ≤ x.n و k > x.key[i]:
i = i + 1
اگر i ≤ x.n و k == x.key[i]:
(x, i) را برگردان // پیدا شد
در غیر این صورت اگر x.leaf:
NIL را برگردان // پیدا نشد
در غیر این صورت:
DISK-READ(x.c[i])
B-TREE-SEARCH(x.c[i], k) را برگرداناز آنجا که درخت ارتفاع O(logₜ n) دارد، و هر گره نیازمند یک دسترسی دیسک (یا یک اسکن درونحافظهای در سراسر تا 2t-1 کلید) است، هزینه جستجوی کل O(t logₜ n) است — تعداد کمی دسترسی دیسک گران ترکیبشده با کار سریع درونحافظهای درون هر گره.
درج: تقسیم گرههای پر در مسیر پایینرفتن
درج در یک درخت B باید حالتی را مدیریت کند که یک گره از قبل پر باشد (2t-1 کلید داشته باشد) و نتواند کلید دیگری را بدون نقض ویژگی حداکثر-کلید بپذیرد. تکنیک استاندارد یک گره پر را به دو گره Splits (تقسیم) میکند، هرکدام با t-1 کلید، و کلید میانی را به بالا در والد فشار میدهد.
B-TREE-SPLIT-CHILD(x, i):
// فرزند پر x.c[i] را نصف میکند،
// کلید میانهاش را به بالا در x منتقل میکند
z = ALLOCATE-NODE()
y = x.c[i]
z.leaf = y.leaf
z.n = t - 1
آخرین t-1 کلید y را در z کپی کن
آخرین t فرزند y را در z کپی کن (اگر برگ نباشد)
y.n = t - 1
z را بهعنوان فرزند جدید x، درست پس از y، درج کن
کلید میانه y را به بالا در x در موقعیت i منتقل کن
x.n = x.n + 1بینش کلیدی برای حفظ کارایی یک استراتژی Proactive Splitting (تقسیم پیشگیرانه) است: بهجای پایینرفتن کامل و سپس کشف اینکه یک گره پر است (که نیازمند بازگشت به عقب میبود)، الگوریتم هر گره پری که در مسیر پایینرفتن مواجه میشود را پیش از پایینرفتن به آن تقسیم میکند. این تضمین میکند تا زمانی که الگوریتم به برگ درست برای درج برسد، آن برگ تضمین میشود پر نباشد، چون والدش از قبل آن را تقسیم میکرد اگر بود.
B-TREE-INSERT(T, k):
r = T.root
اگر r.n == 2t - 1:
// ریشه پر است — درخت را یک سطح رشد میدهد
s = ALLOCATE-NODE()
T.root = s
s.leaf = FALSE
s.n = 0
s.c[1] = r
B-TREE-SPLIT-CHILD(s, 1)
B-TREE-INSERT-NONFULL(s, k)
در غیر این صورت:
B-TREE-INSERT-NONFULL(r, k)از آنجا که تقسیم پیشگیرانه در یک عبور پایینرونده واحد انجام میشود، درج فقط نیازمند O(logₜ n) دسترسی دیسک است، که با ارتفاع درخت مطابقت دارد، بدون نیاز به یک عبور بالارونده جداگانه یا بازگشت به عقب.
حذف: یک عبور پایینرونده جزئیتر
حذف از یک فلسفه پیشگیرانه مشابه پیروی میکند، اما باید موارد بیشتری را مدیریت کند: اگر کلیدی که باید حذف شود در یک گره داخلی باشد، باید با اسلاف یا جانشینش جایگزین شود (مشابه با حذف درخت-جستجوی-دودویی که پیشتر در این مجموعه بحث شد)، و اگر گرهای که الگوریتم باید به آن پایین برود فقط حداقل t-1 کلید داشته باشد، ابتدا باید یک کلید اضافه به آن داده شود، یا با قرضگرفتن یکی از یک خواهر-برادر مجاور یا با ادغام با یک خواهر-برادر، پیش از ادامه پایینرفتن. این تضمین میکند هر گرهای که در طول عبور پایینرونده بازدید میشود کلید کافی برای ازدستدادن ایمن یکی داشته باشد، که دوباره از نیاز به یک مرحله بازگشت-به-عقب جداگانه اجتناب میکند.
چرا درختهای B در سیستمهای مبتنی بر دیسک و پایگاهداده غالباند
درختهای B، و نوع رایجشان B+ Trees (که همه داده واقعی را در برگها ذخیره میکنند و از گرههای داخلی صرفاً برای پیمایش استفاده میکنند)، ستون فقرات تقریباً هر ایندکس پایگاهداده رابطهای و بسیاری سیستمفایل را تشکیل میدهند. انتخاب درجه حداقل t معمولاً طوری تنظیم میشود که یک گره واحد دقیقاً یک بلوک دیسک (اغلب ۴KB یا بزرگتر) را پر کند، که تعداد کلیدهای بررسیشده بهازای هر دسترسی دیسک را حداکثر میکند و ارتفاع درخت را برای تعداد مشخصی کلید کمینه میکند.
مثال عملی:
با t = 1000 (یک مقدار واقعبینانه برای ایندکسهای پایگاهداده)،
یک درخت B میتواند بیش از 1 میلیارد کلید را با ارتفاعی فقط 3 ایندکس کند،
یعنی هر کلیدی میتواند با حداکثر 3 خواندن دیسک پیدا شوداین کاهش چشمگیر ارتفاع در مقایسه با یک درخت جستجوی دودویی — که تقریباً ۳۰ سطح برای همان یک میلیارد کلید نیاز داشت — دقیقاً چرایی این است که درختهای B، نه درختهای قرمز-سیاه، انتخاب استاندارد هستند هروقت داده باید روی دیسک ذخیره شود نه کاملاً در حافظه نگه داشته شود.