B-tree

از ویکیپدیا، دانشنامه آزاد
پرش به ناوبری پرش به جستجو
B-tree
تایپ کنیددرخت (ساختار داده)
اختراع شد1970 [1]
اختراع شده توسطرودلف بایر ، ادوارد ام. مک کریت
پیچیدگی زمانی در نماد O بزرگ
الگوریتم میانگین بدترین حالت
فضا O( n ) O( n )
جستجو کردن O (log n ) O (log n )
درج کنید O (log n ) O (log n )
حذف O (log n ) O (log n )

در علوم کامپیوتر ، B-tree یک ساختار داده درختی خود متعادل کننده است که داده های مرتب شده را حفظ می کند و امکان جستجو، دسترسی متوالی، درج و حذف را در زمان لگاریتمی فراهم می کند . درخت B درخت جستجوی دودویی را تعمیم می‌دهد و به گره‌هایی با بیش از دو فرزند اجازه می‌دهد. [2] برخلاف دیگر درختان جستجوی باینری خود متعادل کننده ، B-tree برای سیستم‌های ذخیره‌سازی که بلوک‌های نسبتاً بزرگی از داده‌ها را می‌خوانند و می‌نویسند، مانند پایگاه‌های داده و سیستم‌های فایل، مناسب است .

مبدا

درختان B توسط رودولف بایر و ادوارد ام. مک‌کریت در حین کار در آزمایشگاه تحقیقاتی بوئینگ به منظور مدیریت مؤثر صفحات فهرست برای فایل‌های بزرگ با دسترسی تصادفی اختراع شدند. فرض اصلی این بود که شاخص‌ها آنقدر حجیم هستند که تنها تکه‌های کوچک درخت می‌توانند در حافظه اصلی جای بگیرند. مقاله بایر و مک کریت، سازماندهی و نگهداری شاخص های بزرگ سفارش داده شده ، [1] ابتدا در جولای 1970 منتشر شد و بعداً در Acta Informatica منتشر شد . [3]

بایر و مک کریت هرگز توضیح ندادند که B مخفف چه چیزی است: بوئینگ ، متعادل ، گسترده ، پرپشت و بایر پیشنهاد شده است. [4] [5] [6] مک کریت گفته است که "هرچه بیشتر به معنای B در درختان B فکر کنید، درختان B را بهتر درک می کنید." [5]

تعریف

طبق تعریف کنوت ، یک درخت B از مرتبه m درختی است که ویژگی های زیر را برآورده می کند: [7]

  1. هر گره حداکثر m فرزند دارد.
  2. هر گره داخلی حداقل ⌈ m /2⌉ فرزند دارد.
  3. هر گره بدون برگ حداقل دو فرزند دارد.
  4. همه برگها در یک سطح ظاهر می شوند و هیچ اطلاعاتی ندارند.
  5. یک گره بدون برگ با k فرزند حاوی کلیدهای k -1 است.

کلیدهای هر گره داخلی به عنوان مقادیر جداسازی عمل می کنند که زیردرخت های آن را تقسیم می کنند. به عنوان مثال، اگر یک گره داخلی دارای 3 گره فرزند (یا زیردرخت) باشد، باید 2 کلید داشته باشد : یک و یک 2 . همه مقادیر در سمت چپ ترین زیردرخت کمتر از 1 ، همه مقادیر در زیردرخت میانی بین 1 و 2 خواهند بود ، و همه مقادیر در سمت راست ترین زیردرخت بزرگتر از 2 خواهند بود.

گره های داخلی
گره های داخلی (همچنین به عنوان گره های داخلی شناخته می شوند) همه گره ها هستند به جز گره های برگ و گره ریشه. آنها معمولاً به عنوان مجموعه ای مرتب از عناصر و اشاره گرهای فرزند نشان داده می شوند. هر گره داخلی دارای حداکثر U فرزند و حداقل L فرزند است. بنابراین، تعداد عناصر همیشه 1 کمتر از تعداد نشانگرهای فرزند است (تعداد عناصر بین L -1 و U -1 است). U باید 2 L یا 2 L -1 باشد. بنابراین هر گره داخلی حداقل تا نیمه پر است. رابطه بین U و Lبه این معنی است که دو گره نیمه پر را می توان برای ایجاد یک گره قانونی به هم متصل کرد و یک گره کامل را می توان به دو گره قانونی تقسیم کرد (اگر فضایی برای فشار دادن یک عنصر به سمت بالا به سمت والد وجود داشته باشد). این ویژگی ها حذف و درج مقادیر جدید در درخت B و تنظیم درخت برای حفظ ویژگی های درخت B را امکان پذیر می کند.
گره ریشه
تعداد فرزندان گره ریشه همان حد بالای گره های داخلی است، اما محدودیت پایینی ندارد. برای مثال، زمانی که عناصر کمتر از L -1 در کل درخت وجود داشته باشد، ریشه تنها گره در درخت خواهد بود که اصلاً فرزندی ندارد.
گره های برگ
در اصطلاح Knuth، گره های برگ هیچ اطلاعاتی را حمل نمی کنند. گره‌های داخلی که یک سطح بالاتر از برگ‌ها قرار دارند، همان‌هایی هستند که توسط نویسندگان دیگر «برگ» نامیده می‌شوند: این گره‌ها فقط کلیدها را ذخیره می‌کنند (حداکثر m -1 و حداقل m /2-1 اگر ریشه نباشند) و اشاره گر به گره هایی که هیچ اطلاعاتی ندارند.

یک B-tree با عمق n +1 می تواند حدود U برابر تعداد موارد B-tree با عمق n باشد ، اما هزینه عملیات جستجو، درج و حذف با عمق درخت افزایش می یابد. مانند هر درخت متعادل، هزینه بسیار کندتر از تعداد عناصر رشد می کند.

برخی از درختان متعادل مقادیر را فقط در گره های برگ ذخیره می کنند و از انواع مختلف گره ها برای گره های برگ و گره های داخلی استفاده می کنند. درختان B مقادیر را در هر گره درخت به جز گره های برگ نگه می دارند.

تفاوت در اصطلاح

ادبیات درختان B از نظر اصطلاحات یکسان نیست. [8]

Bayer و McCreight (1972)، [3] Comer (1979)، [2] و دیگران ترتیب B-tree را به عنوان حداقل تعداد کلیدها در یک گره غیر ریشه تعریف می کنند. [9] اشاره می کند که اصطلاحات مبهم است زیرا حداکثر تعداد کلیدها مشخص نیست. یک سفارش 3 B-tree ممکن است حداکثر 6 کلید یا حداکثر 7 کلید داشته باشد. کنوت (1998) با تعریف ترتیب حداکثر تعداد فرزندان (که یک عدد بیشتر از حداکثر تعداد کلیدها است) از مشکل جلوگیری می کند. [7]

اصطلاح برگ نیز ناسازگار است. بایر و مک کریت (1972) [3] سطح برگ را پایین ترین سطح کلیدها در نظر گرفتند، اما کنوت سطح برگ را یک سطح زیر پایین ترین کلیدها در نظر گرفت. [10] بسیاری از گزینه های اجرایی ممکن وجود دارد. در برخی طرح‌ها، برگ‌ها ممکن است کل رکورد داده را در خود نگه دارند. در طرح‌های دیگر، برگ‌ها ممکن است فقط نشانگرهای رکورد داده را نگه دارند. این انتخاب ها برای ایده درخت B اساسی نیستند. [11]

برای سادگی، اکثر نویسندگان فرض می کنند تعداد ثابتی از کلیدها وجود دارد که در یک گره قرار می گیرند. فرض اصلی این است که اندازه کلید ثابت است و اندازه گره ثابت است. در عمل، کلیدهای طول متغیر ممکن است به کار گرفته شوند. [12]

توضیحات غیر رسمی

B-tree ( Bayer & McCreight 1972 ) درجه 5 ( Knuth 1998 ).

در درختان B، گره‌های داخلی ( غیر برگ ) می‌توانند تعداد متغیری از گره‌های فرزند را در محدوده از پیش تعریف شده داشته باشند. هنگامی که داده درج یا از یک گره حذف می شود، تعداد گره های فرزند آن تغییر می کند. به منظور حفظ محدوده از پیش تعریف شده، گره های داخلی ممکن است به هم متصل یا تقسیم شوند. از آنجایی که گستره ای از گره های فرزند مجاز است، درختان B به تکرار درختان جستجوی خود متعادل کننده نیازی به تعادل مجدد ندارند، اما ممکن است مقداری فضا را هدر دهند، زیرا گره ها کاملاً پر نیستند. مرزهای پایین و بالایی تعداد گره های فرزند معمولاً برای یک پیاده سازی خاص ثابت می شوند. به عنوان مثال، در یک درخت 2-3 (گاهی اوقات به عنوان درخت 2-3 B شناخته می شود )، هر گره داخلی ممکن است تنها 2 یا 3 گره فرزند داشته باشد.

هر گره داخلی درخت B شامل تعدادی کلید است. کلیدها به عنوان مقادیر جداسازی عمل می کنند که درختان فرعی آن را تقسیم می کنند . به عنوان مثال، اگر یک گره داخلی دارای 3 گره فرزند (یا زیردرخت) باشد، باید 2 کلید داشته باشد:و. تمام مقادیر در سمت چپ ترین زیردرخت کمتر از، تمام مقادیر در زیردرخت میانی بین خواهد بودو، و تمام مقادیر در سمت راست ترین زیردرخت بزرگتر از.

معمولاً تعداد کلیدها به گونه ای انتخاب می شود که بین آنها متفاوت باشدو، جایی کهحداقل تعداد کلیدها وحداقل درجه یا عامل انشعاب درخت است. در عمل، کلیدها بیشترین فضا را در یک گره اشغال می کنند. ضریب 2 تضمین می کند که گره ها می توانند تقسیم یا ترکیب شوند. اگر یک گره داخلی داشته باشدکلیدها، سپس افزودن یک کلید به آن گره را می توان با تقسیم فرضی انجام دادگره کلیدی به دو قسمتگره های کلیدی و انتقال کلیدی که در وسط قرار داشت به گره والد. هر گره تقسیم دارای حداقل تعداد کلید مورد نیاز است. به طور مشابه، اگر یک گره داخلی و همسایه آن هر کدام داشته باشندکلیدها، سپس یک کلید ممکن است از گره داخلی با ترکیب آن با همسایه خود حذف شود. حذف کلید باعث می شود گره داخلی دچار مشکل شودکلیدها؛ پیوستن به همسایه را اضافه می کندکلیدها به اضافه یک کلید دیگر از والدین همسایه پایین آورده شده است. نتیجه یک گره کاملاً کامل استکلیدها

تعداد شاخه ها (یا گره های فرزند) از یک گره یک عدد بیشتر از تعداد کلیدهای ذخیره شده در گره خواهد بود. در یک درخت B 2-3، گره های داخلی یا یک کلید (با دو گره فرزند) یا دو کلید (با سه گره فرزند) را ذخیره می کنند. B-tree گاهی اوقات با پارامترها توصیف می شود-یا به سادگی با بالاترین ترتیب انشعاب،.

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

با اضافه شدن عناصر به درخت، این عمق به آرامی افزایش می‌یابد، اما افزایش عمق کلی به ندرت اتفاق می‌افتد و باعث می‌شود که تمام گره‌های برگ یک گره دیگر از ریشه دورتر باشند.

هنگامی که زمان دسترسی به داده های یک گره بسیار بیشتر از زمان صرف شده برای پردازش آن داده است، درختان B نسبت به پیاده سازی های جایگزین مزایای قابل توجهی دارند، زیرا در این صورت هزینه دسترسی به گره ممکن است طی چندین عملیات درون گره مستهلک شود. این معمولاً زمانی اتفاق می‌افتد که داده‌های گره در ذخیره‌سازی ثانویه مانند درایوهای دیسک هستند. با به حداکثر رساندن تعداد کلیدها در هر گره داخلی ، ارتفاع درخت کاهش می‌یابد و تعداد دسترسی‌های گره گران قیمت کاهش می‌یابد. علاوه بر این، تعادل مجدد درخت کمتر اتفاق می افتد. حداکثر تعداد گره های فرزند بستگی به اطلاعاتی دارد که باید برای هر گره فرزند و اندازه یک بلوک کامل دیسک ذخیره شود .یا اندازه مشابه در ذخیره سازی ثانویه. در حالی که توضیح ۲ تا ۳ درخت B آسان‌تر است، درخت‌های B عملی با استفاده از ذخیره‌سازی ثانویه به تعداد زیادی گره فرزند برای بهبود عملکرد نیاز دارند.

انواع

اصطلاح B-tree ممکن است به یک طرح خاص اشاره داشته باشد یا ممکن است به یک کلاس کلی از طرح ها اشاره کند. در مفهوم محدود، درخت B کلیدها را در گره‌های داخلی خود ذخیره می‌کند، اما نیازی نیست آن کلیدها را در رکوردهای برگ‌ها ذخیره کند. کلاس کلی شامل تغییراتی مانند درخت B+ ، درخت B * و درخت B *+ است.

  • در درخت B+ ، کپی‌هایی از کلیدها در گره‌های داخلی ذخیره می‌شوند. کلیدها و سوابق در برگها ذخیره می شوند. علاوه بر این، یک گره برگ ممکن است یک اشاره گر به گره برگ بعدی برای سرعت بخشیدن به دسترسی متوالی داشته باشد. [2]
  • درخت B * گره های داخلی مجاور بیشتری را متعادل می کند تا گره های داخلی را متراکم تر نگه دارد. [2] این نوع تضمین می کند که گره های غیر ریشه به جای 1/2، حداقل 2/3 پر هستند. [13] از آنجایی که پرهزینه ترین بخش عملیات درج گره در درخت B، شکافتن گره است، درختان B * برای به تعویق انداختن عملیات تقسیم تا زمانی که می توانند ساخته می شوند. [14] برای حفظ این امر، به جای اینکه یک گره بلافاصله پس از پر شدن آن تقسیم شود، کلیدهای آن با یک گره در کنار آن به اشتراک گذاشته می شود. این عملیات ریختن هزینه کمتری نسبت به تقسیم دارد، زیرا فقط به جابجایی کلیدها بین گره های موجود نیاز دارد، نه تخصیص حافظه برای یک گره جدید. [14]برای درج ابتدا بررسی می شود که آیا گره مقداری فضای خالی در خود دارد یا خیر و اگر چنین است، کلید جدید فقط در گره درج می شود. با این حال، اگر گره پر است (دارای کلیدهای m − 1 ، که m ترتیب درخت به عنوان حداکثر تعداد اشاره‌گر به زیردرخت‌های یک گره است)، باید بررسی شود که آیا خواهر و برادر مناسب وجود دارد و فضای خالی دارد یا خیر. . اگر خواهر و برادر سمت راست دارای کلیدهای j < m − 1 باشند، کلیدها تا حد امکان به طور مساوی بین دو گره خواهر و برادر توزیع می شوند. برای این منظور، کلیدهای m - 1 از گره فعلی، کلید جدید درج شده، یک کلید از گره والد و کلیدهای j از گره خواهر و برادر به عنوان یک آرایه مرتب از گره دیده می شوند.m + j + 1 کلید. آرایه به نصف تقسیم می‌شود، به طوری که ( m + j + 1)/2 پایین‌ترین کلیدها در گره فعلی باقی می‌مانند، کلید بعدی (وسط) در والد وارد می‌شود و بقیه به خواهر یا برادر راست می‌روند. [14] (کلید تازه وارد شده ممکن است در هر یک از سه مکان به پایان برسد.) وضعیت زمانی که خواهر و برادر سمت راست پر است و سمت چپ آن نیست، مشابه است. [14] هنگامی که هر دو گره خواهر و برادر پر هستند، آنگاه دو گره (گره فعلی و یک خواهر یا برادر) به سه تقسیم می‌شوند و یک کلید دیگر به بالای درخت، به گره والد منتقل می‌شود. [14] اگر والد پر باشد، عملیات spill/split به سمت گره ریشه منتشر می شود.[14] حذف گره ها تا حدودی پیچیده تر از درج کردن آن است.
  • درخت B *+ ویژگی های درخت اصلی B+ و درخت B * را با هم ترکیب می کند. [15]
  • درخت‌های B را می‌توان به درخت‌های آماری سفارش تبدیل کرد تا امکان جستجوی سریع برای رکورد N به ترتیب کلید، یا شمارش تعداد رکوردها بین هر دو رکورد، و سایر عملیات‌های مرتبط دیگر فراهم شود. [16]

استفاده از درخت B در پایگاه داده

زمان جستجوی فایل مرتب شده

معمولاً الگوریتم‌های مرتب‌سازی و جستجو با تعداد عملیات مقایسه‌ای مشخص می‌شوند که باید با استفاده از نشانه‌گذاری ترتیب انجام شوند . به عنوان مثال ، جستجوی دودویی یک جدول مرتب شده با N رکورد را می توان تقریباً در مقایسه ⌈ log 2 N انجام داد. اگر جدول دارای 1,000,000 رکورد بود، یک رکورد خاص را می توان با حداکثر 20 مقایسه پیدا کرد: ⌈ log 2 (1,000,000) ⌉ = 20 .

پایگاه داده های بزرگ از گذشته بر روی درایوهای دیسک نگهداری می شدند. زمان خواندن یک رکورد در درایو دیسک بسیار بیشتر از زمان لازم برای مقایسه کلیدها پس از در دسترس بودن رکورد است. زمان خواندن یک رکورد از درایو دیسک شامل زمان جستجو و تاخیر چرخشی است. زمان جستجو ممکن است 0 تا 20 یا بیشتر میلی ثانیه باشد و تاخیر چرخشی به طور متوسط ​​حدود نیمی از دوره چرخش است. برای یک درایو 7200 RPM، دوره چرخش 8.33 میلی ثانیه است. برای درایوهایی مانند Seagate ST3500320NS، زمان جستجوی مسیر به مسیر 0.8 میلی ثانیه و متوسط ​​زمان جستجوی خواندن 8.5 میلی ثانیه است. [17] برای سادگی، فرض کنید خواندن از روی دیسک حدود 10 میلی ثانیه طول می کشد.

پس ساده لوحانه، زمان تعیین یک رکورد از یک میلیون، 20 بار خواندن دیسک در 10 میلی ثانیه در هر خواندن دیسک، که 0.2 ثانیه است، طول می کشد.

زمان چندان بد نخواهد بود زیرا رکوردهای فردی با هم در یک بلوک دیسک گروه بندی می شوند . یک بلوک دیسک ممکن است 16 کیلوبایت باشد. اگر هر رکورد 160 بایت باشد، می توان 100 رکورد را در هر بلوک ذخیره کرد. زمان خواندن دیسک بالا در واقع برای یک بلوک کامل بود. هنگامی که سر دیسک در موقعیت خود قرار گرفت، یک یا چند بلوک دیسک را می توان با تاخیر کمی خواند. با 100 رکورد در هر بلوک، 6 یا بیشتر مقایسه آخر نیازی به خواندن دیسک ندارند—مقایسه ها همه در آخرین خوانده شده بلوک دیسک هستند.

برای سرعت بخشیدن به جستجو، 13 تا 14 مقایسه اول (که هر کدام نیاز به دسترسی به دیسک داشتند) باید تسریع شود.

ایندکس به جستجو سرعت می بخشد

یک شاخص درختی B یک ساختار درختی چند سطحی ایجاد می کند که پایگاه داده را به بلوک ها یا صفحات با اندازه ثابت تقسیم می کند. هر سطح از این درخت را می توان برای پیوند دادن آن صفحات از طریق یک مکان آدرس مورد استفاده قرار داد و به یک صفحه (که به عنوان یک گره یا صفحه داخلی شناخته می شود) اجازه می دهد تا به صفحه دیگر با صفحات برگ در پایین ترین سطح ارجاع دهد. یک صفحه معمولاً نقطه شروع درخت یا «ریشه» است. از اینجاست که جستجو برای یک کلید خاص آغاز می شود و مسیری را طی می کند که به یک برگ ختم می شود. اکثر صفحات در این ساختار صفحات برگ هستند که در نهایت به ردیف های جدول خاص اشاره می کنند.

بهبود قابل توجهی در عملکرد را می توان با شاخص B-tree ایجاد کرد. از آنجا که هر گره (یا صفحه داخلی) می تواند بیش از دو فرزند داشته باشد، یک شاخص درخت B معمولاً ارتفاع کوتاه تری (فاصله ریشه تا دورترین برگ) نسبت به درخت جستجوی باینری دارد. در مثال بالا، خواندن اولیه دیسک محدوده جستجو را به میزان دو برابر کاهش داد. با ایجاد یک نمایه کمکی که حاوی اولین رکورد در هر بلوک دیسک است (که گاهی اوقات به آن شاخص پراکنده می گویند، می توان این شاخص را بطور قابل ملاحظه ای بهبود بخشید.). این فهرست کمکی 1% از اندازه پایگاه داده اصلی خواهد بود، اما می توان آن را با سرعت بیشتری جستجو کرد. یافتن یک ورودی در فهرست کمکی به ما می گوید کدام بلوک را در پایگاه داده اصلی جستجو کنیم. پس از جستجوی نمایه کمکی، ما باید فقط آن یک بلوک از پایگاه داده اصلی را جستجو کنیم - با هزینه خواندن یک دیسک بیشتر. این شاخص دارای 10000 ورودی است، بنابراین حداکثر 14 مقایسه طول می کشد. مانند پایگاه داده اصلی، شش یا بیشتر مقایسه آخر در فهرست کمکی در همان بلوک دیسک خواهد بود. فهرست را می توان در حدود هشت خواندن دیسک جستجو کرد و رکورد مورد نظر را می توان در 9 خواندن دیسک مشاهده کرد.

ترفند ایجاد یک نمایه کمکی را می توان برای ایجاد یک نمایه کمکی به نمایه کمکی تکرار کرد. این یک شاخص aux-aux را ایجاد می کند که تنها به 100 ورودی نیاز دارد و در یک بلوک دیسک قرار می گیرد.

به جای خواندن 14 بلوک دیسک برای یافتن رکورد مورد نظر، فقط باید 3 بلوک را بخوانیم. این مسدود کردن ایده اصلی ایجاد B-tree است، جایی که دیسک بلوک‌های پر کردن سلسله مراتبی از سطوح را برای ایجاد شاخص می‌کند. خواندن و جستجوی اولین (و تنها) بلوک شاخص aux-aux که ریشه درخت است، بلوک مربوطه را در aux-index در سطح زیر مشخص می کند. خواندن و جستجوی آن بلوک aux-index، بلوک مربوطه را برای خواندن مشخص می کند، تا زمانی که سطح نهایی که به سطح برگ معروف است، رکوردی را در پایگاه داده اصلی شناسایی کند. به جای 150 میلی ثانیه، فقط 30 میلی ثانیه برای به دست آوردن رکورد نیاز داریم.

شاخص های کمکی مشکل جستجو را از یک جستجوی دودویی که نیاز به تقریباً log 2 N خواندن دیسک دارد به یک مورد نیاز دارد که فقط به log b می خواند N دیسک می خواند که در آن b عامل مسدود کننده است (تعداد ورودی در هر بلوک: b = 100 ورودی در هر بلوک در ما مثال؛ log 100 1,000,000 = 3 خوانده شده).

در عمل، اگر پایگاه داده اصلی به طور مکرر جستجو شود، نمایه aux-aux و بسیاری از نمایه aux ممکن است در حافظه پنهان دیسک قرار گیرند ، بنابراین خواندن دیسک را متحمل نمی شوند. B-tree به عنوان پیاده‌سازی شاخص استاندارد در تقریباً همه پایگاه‌های داده رابطه‌ای باقی می‌ماند و بسیاری از پایگاه‌های داده غیررابطه‌ای نیز از آنها استفاده می‌کنند. [18]

درج و حذف

اگر پایگاه داده تغییر نکند، کامپایل ایندکس ساده است و ایندکس هرگز نیازی به تغییر ندارد. اگر تغییراتی وجود داشته باشد، مدیریت پایگاه داده و فهرست آن پیچیده تر می شود.

حذف رکوردها از پایگاه داده نسبتاً آسان است. ایندکس می تواند ثابت بماند و رکورد فقط به عنوان حذف شده علامت گذاری شود. پایگاه داده به ترتیب مرتب شده باقی می ماند. اگر تعداد زیادی حذف تنبل وجود داشته باشد، جستجو و ذخیره سازی کارآمدتر می شوند. [19]

درج‌ها می‌توانند در یک فایل متوالی مرتب شده بسیار آهسته باشند زیرا باید فضایی برای رکورد درج شده ایجاد شود. درج یک رکورد قبل از اولین رکورد مستلزم جابجایی همه رکوردها به پایین است. چنین عملیاتی برای عملی بودن بسیار گران است. یک راه حل این است که برخی فضاها را رها کنید. به جای بسته بندی متراکم تمام رکوردها در یک بلوک، بلوک می تواند فضای خالی داشته باشد تا امکان درج های بعدی را فراهم کند. آن فضاها به گونه ای علامت گذاری می شوند که گویی رکوردهای "حذف شده" هستند.

هر دو درج و حذف سریع هستند تا زمانی که فضای روی یک بلوک در دسترس باشد. اگر یک درج روی بلوک قرار نمی‌گیرد، باید فضای خالی در بلوک نزدیک پیدا شود و شاخص‌های کمکی تنظیم شوند. امید این است که فضای کافی در این نزدیکی وجود داشته باشد، به طوری که بسیاری از بلوک ها نیازی به سازماندهی مجدد نداشته باشند. همچنین ممکن است از برخی بلوک‌های دیسک خارج از ترتیب استفاده شود. [18]

مزایای استفاده از درخت B برای پایگاه داده

B-tree از تمام ایده هایی که در بالا توضیح داده شد استفاده می کند. به طور خاص، درخت B:

  • کلیدها را به ترتیب مرتب شده برای پیمایش متوالی نگه می دارد
  • از یک شاخص سلسله مراتبی برای به حداقل رساندن تعداد خواندن دیسک استفاده می کند
  • از بلوک های نیمه کامل برای سرعت بخشیدن به درج و حذف استفاده می کند
  • شاخص را با یک الگوریتم بازگشتی متعادل نگه می دارد

علاوه بر این، B-tree با اطمینان از پر بودن گره های داخلی حداقل ضایعات را به حداقل می رساند. یک B-tree می تواند تعداد دلخواه درج و حذف را مدیریت کند. [18]

بهترین حالت و بدترین ارتفاع

فرض کنید h ≥ -1 ارتفاع درخت B کلاسیک باشد (به درخت (ساختار داده) § اصطلاحات برای تعریف ارتفاع درخت مراجعه کنید). بگذارید n ≥ 0 تعداد ورودی های درخت باشد. بگذارید m حداکثر تعداد فرزندانی باشد که یک گره می تواند داشته باشد. هر گره می تواند حداکثر m -1 کلید داشته باشد.

می توان (به عنوان مثال با استقرا) نشان داد که یک درخت B با ارتفاع h با تمام گره های آن کاملاً پر شده دارای n = m h +1 –1 ورودی است. بنابراین، بهترین ارتفاع موردی (یعنی حداقل ارتفاع) درخت B این است:

اجازه دهیدحداقل تعداد فرزندانی باشد که یک گره داخلی (غیر ریشه) باید داشته باشد. برای یک درخت B معمولی،

کامر (1979) و کورمن و همکاران. (2001) بدترین حالت (حداکثر ارتفاع) درخت B را به عنوان [20] نشان می دهد.

الگوریتم ها

جستجو

جستجو شبیه به جستجوی درخت جستجوی دودویی است. با شروع از ریشه، درخت به صورت بازگشتی از بالا به پایین طی می شود. در هر سطح، جستجو میدان دید خود را به نشانگر فرزند (درخت فرعی) کاهش می دهد که محدوده آن شامل مقدار جستجو می شود. محدوده یک زیردرخت با مقادیر یا کلیدهای موجود در گره والد آن تعریف می شود. این مقادیر محدود کننده به عنوان مقادیر جداسازی نیز شناخته می شوند.

جستجوی دودویی معمولاً (اما نه لزوما) در گره ها برای یافتن مقادیر جداسازی و درخت فرزند مورد علاقه استفاده می شود.

درج

مثال درج درخت AB با هر تکرار. گره های این درخت B حداکثر 3 فرزند دارند (نظم Knuth 3).

همه درج ها از یک گره برگ شروع می شوند. برای درج یک عنصر جدید، درخت را جستجو کنید تا گره برگ را پیدا کنید که در آن عنصر جدید باید اضافه شود. عنصر جدید را با مراحل زیر در آن گره وارد کنید:

  1. اگر گره دارای تعداد عناصر کمتر از حداکثر مجاز باشد، در این صورت جا برای عنصر جدید وجود دارد. عنصر جدید را با مرتب نگه داشتن عناصر گره در گره وارد کنید.
  2. در غیر این صورت گره پر است، آن را به طور مساوی به دو گره تقسیم کنید تا:
    1. یک میانه واحد از بین عناصر برگ و عنصر جدیدی که در حال درج است انتخاب می شود.
    2. مقادیر کمتر از میانه در گره سمت چپ جدید و مقادیر بزرگتر از میانه در گره راست جدید قرار می گیرند و میانه به عنوان یک مقدار جداسازی عمل می کند.
    3. مقدار جداسازی در والد گره درج می شود که ممکن است باعث تقسیم آن و غیره شود. اگر گره والد ندارد (یعنی گره ریشه بود)، یک ریشه جدید بالای این گره ایجاد کنید (ارتفاع درخت را افزایش دهید).

اگر شکاف تا ریشه پیش برود، یک ریشه جدید با یک مقدار جداکننده و دو فرزند ایجاد می کند، به همین دلیل است که کران پایین در اندازه گره های داخلی روی ریشه اعمال نمی شود. حداکثر تعداد عناصر در هر گره U -1 است. هنگامی که یک گره تقسیم می شود، یک عنصر به والد منتقل می شود، اما یک عنصر اضافه می شود. بنابراین، باید بتوان حداکثر تعداد U -1 عناصر را به دو گره قانونی تقسیم کرد. اگر این عدد فرد باشد، آنگاه U = 2 L و یکی از گره های جدید حاوی عناصر ( U -2)/2 = L -1 است، و از این رو یک گره قانونی است، و دیگری حاوی یک عنصر دیگر است، و از این رو است. قانونی نیز اگر U −1 زوج باشد، U =2 استL -1، بنابراین 2 L- 2 عنصر در گره وجود دارد. نیمی از این عدد L -1 است که حداقل تعداد عناصر مجاز در هر گره است.

یک الگوریتم جایگزین از یک عبور واحد از درخت از ریشه به گره ای که درج در آن انجام می شود پشتیبانی می کند، و هر گره کاملی را که در راه با آن مواجه می شود به طور پیشگیرانه تقسیم می کند. این امر از نیاز به فراخوانی گره های والد به حافظه جلوگیری می کند، که اگر گره ها در حافظه ثانویه باشند ممکن است گران باشد. با این حال، برای استفاده از این الگوریتم، باید بتوانیم یک عنصر را به والد ارسال کنیم و عناصر U- 2 باقیمانده را به دو گره قانونی تقسیم کنیم، بدون اینکه عنصر جدیدی اضافه کنیم. این به جای U = 2 L - 1 به U = 2 L نیاز دارد ، که دلیل این است که چرا برخی [ کدام؟ ] کتاب های درسی این الزام را در تعریف درختان B تحمیل می کنند.

حذف

دو استراتژی محبوب برای حذف از درخت B وجود دارد.

  1. مورد را بیابید و حذف کنید، سپس درخت را بازسازی کنید تا متغیرهای آن، OR را حفظ کند
  2. یک بار به پایین درخت انجام دهید، اما قبل از ورود (بازدید) از یک گره، درخت را مجدداً ساختار دهید تا هنگامی که کلید حذف شده با آن مواجه شد، بدون ایجاد نیاز به بازسازی بیشتر، بتوان آن را حذف کرد.

الگوریتم زیر از استراتژی قبلی استفاده می کند.

هنگام حذف یک عنصر دو حالت خاص وجود دارد:

  1. عنصر در یک گره داخلی یک جداکننده برای گره های فرزند آن است
  2. حذف یک عنصر ممکن است گره آن را زیر حداقل تعداد عناصر و فرزندان قرار دهد

مراحل این موارد به ترتیب زیر است.

حذف از یک گره برگ

  1. مقدار مورد نظر برای حذف را جستجو کنید.
  2. اگر مقدار در یک گره برگ است، به سادگی آن را از گره حذف کنید.
  3. اگر جریان زیر آب رخ داد، درخت را همانطور که در بخش "تعادل مجدد پس از حذف" در زیر توضیح داده شده است، دوباره متعادل کنید.

حذف از یک گره داخلی

هر عنصر در یک گره داخلی به عنوان یک مقدار جداسازی برای دو زیردرخت عمل می کند، بنابراین باید جایگزینی برای جداسازی پیدا کنیم. توجه داشته باشید که بزرگترین عنصر در زیردرخت سمت چپ هنوز کمتر از جداکننده است. به همین ترتیب، کوچکترین عنصر در زیردرخت سمت راست همچنان بزرگتر از جداکننده است. هر دوی این عناصر در گره های برگ قرار دارند و هر یک می تواند جداکننده جدیدی برای دو زیردرخت باشد. به صورت الگوریتمی در زیر توضیح داده شده است:

  1. یک جداکننده جدید (یا بزرگترین عنصر در زیردرخت سمت چپ یا کوچکترین عنصر در زیردرخت سمت راست) انتخاب کنید، آن را از گره برگ که در آن قرار دارد حذف کنید و عنصری را که قرار است حذف شود با جداکننده جدید جایگزین کنید.
  2. مرحله قبل یک عنصر (جداکننده جدید) را از یک گره برگ حذف کرد. اگر آن گره برگ اکنون کمبود دارد (کمتر از تعداد گره های لازم دارد)، سپس درخت را با شروع از گره برگ دوباره متعادل کنید.

تعادل مجدد پس از حذف

تعادل مجدد از یک برگ شروع می شود و تا زمانی که درخت متعادل شود به سمت ریشه ادامه می یابد. اگر حذف یک عنصر از یک گره آن را به کمترین اندازه رسانده باشد، برخی از عناصر باید دوباره توزیع شوند تا همه گره‌ها به حداقل برسند. معمولاً توزیع مجدد شامل جابجایی یک عنصر از گره خواهر و برادری است که تعداد گره‌های آن بیش از حداقل حداقل است. این عملیات توزیع مجدد چرخش نامیده می شود . اگر هیچ خواهر و برادری نتواند عنصری را ذخیره کند، گره ناقص باید ادغام شودبا یک خواهر و برادر ادغام باعث می شود که والد یک عنصر جداکننده را از دست بدهد، بنابراین ممکن است والد دچار کمبود شود و نیاز به تعادل مجدد داشته باشد. ادغام و تعادل مجدد ممکن است تا ریشه ادامه یابد. از آنجایی که حداقل تعداد عناصر برای ریشه اعمال نمی شود، اینکه ریشه تنها گره ناقص باشد مشکلی نیست. الگوریتم برای تعادل مجدد درخت به شرح زیر است:

  • اگر خواهر یا برادر راست گره ناقص وجود داشته باشد و بیش از حداقل تعداد عناصر داشته باشد، به چپ بچرخانید.
    1. جداکننده را از والد تا انتهای گره کمبود کپی کنید (جداکننده به سمت پایین حرکت می کند؛ گره کمبود اکنون حداقل تعداد عناصر را دارد)
    2. جداکننده در والد را با اولین عنصر خواهر یا برادر راست جایگزین کنید (خواهر یا برادر راست یک گره را از دست می دهد اما همچنان حداقل تعداد عناصر را دارد)
    3. درخت اکنون متعادل است
  • در غیر این صورت، اگر خواهر یا برادر چپ گره ناقص وجود داشته باشد و بیش از حداقل تعداد عناصر داشته باشد، به راست بچرخانید.
    1. جداکننده را از والد تا شروع گره ناقص کپی کنید (جداکننده به سمت پایین حرکت می کند؛ گره کمبود اکنون حداقل تعداد عناصر را دارد)
    2. جداکننده در والد را با آخرین عنصر خواهر یا برادر چپ جایگزین کنید (خواهر یا برادر چپ یک گره را از دست می دهد اما همچنان حداقل تعداد عناصر را دارد)
    3. درخت اکنون متعادل است
  • در غیر این صورت، اگر هر دو خواهر و برادر مستقیم فقط حداقل تعداد عناصر را داشته باشند، با خواهر یا برادری که جداکننده آنها را از والدینشان جدا می کند ادغام می شوند.
    1. جداکننده را در انتهای گره سمت چپ کپی کنید (گره سمت چپ ممکن است گره ناقص باشد یا ممکن است خواهر یا برادر با حداقل تعداد عناصر باشد)
    2. همه عناصر را از گره سمت راست به گره چپ منتقل کنید (گره چپ اکنون حداکثر تعداد عناصر را دارد و گره سمت راست خالی است)
    3. جداکننده را به همراه فرزند سمت راست خالی آن از والد حذف کنید (والد عنصری را از دست می دهد)
      • اگر والد ریشه است و اکنون هیچ عنصری ندارد، آن را آزاد کنید و گره ادغام شده را به ریشه جدید تبدیل کنید (درخت کم عمق تر می شود)
      • در غیر این صورت، اگر تعداد عناصر والد کمتر از مقدار لازم باشد، آنگاه تعادل والد را مجدداً تنظیم کنید [21]
توجه : عملیات تعادل مجدد برای درختان B+ متفاوت است (مثلاً چرخش متفاوت است زیرا والدین دارای کپی از کلید هستند) و درخت B * (به عنوان مثال، سه خواهر و برادر در دو خواهر و برادر ادغام می شوند).

دسترسی متوالی

در حالی که پایگاه‌های اطلاعاتی تازه بارگذاری‌شده رفتار متوالی خوبی دارند، حفظ این رفتار با رشد پایگاه‌داده دشوارتر می‌شود و در نتیجه I/O تصادفی‌تر و چالش‌های عملکردی بیشتر می‌شود. [22]

ساخت اولیه

یک مورد خاص رایج، اضافه کردن مقدار زیادی از داده های از پیش مرتب شده به یک درخت B در ابتدا خالی است. در حالی که انجام یک سری از درج های متوالی کاملاً ممکن است، درج داده های مرتب شده منجر به درختی می شود که تقریباً به طور کامل از گره های نیمه پر تشکیل شده است. در عوض، می توان از یک الگوریتم ویژه «بارگذاری فله» برای تولید درخت کارآمدتر با ضریب انشعاب بالاتر استفاده کرد.

وقتی ورودی مرتب شد، همه درج‌ها در سمت راست ترین لبه درخت قرار می‌گیرند، و به ویژه هر زمان که یک گره تقسیم شود، تضمین می‌کنیم که دیگر درج در نیمه چپ انجام نخواهد شد. هنگام بارگذاری انبوه، ما از این مزیت استفاده می کنیم و به جای اینکه گره های بیش از حد را به طور مساوی تقسیم کنیم، آنها را تا حد امکان به طور ناهموار تقسیم کنیم : گره سمت چپ را کاملاً پر بگذارید و یک گره سمت راست با کلیدهای صفر و یک فرزند ایجاد کنید (بر خلاف B- معمولی- قوانین درختی).

در پایان بارگذاری فله، درخت تقریباً به طور کامل از گره های کاملاً کامل تشکیل شده است. فقط سمت راست ترین گره در هر سطح ممکن است کمتر از پر باشد. از آنجایی که آن گره ها ممکن است کمتر از نیمه پر باشند، برای برقراری مجدد قوانین درخت B معمولی، چنین گره هایی را با خواهر و برادرهای چپ (تضمینی کامل) آنها ترکیب کنید و کلیدها را تقسیم کنید تا دو گره حداقل نصف پر شوند. تنها گره ای که فاقد خواهر و برادر کامل چپ است، ریشه است که مجاز است کمتر از نیمه پر باشد.

در سیستم فایل

درخت B (یا § Variants ) علاوه بر استفاده در پایگاه‌های داده، در سیستم‌های فایل نیز استفاده می‌شود تا امکان دسترسی تصادفی سریع به یک بلوک دلخواه در یک فایل خاص را فراهم کند. مشکل اصلی تبدیل بلاک فایل استآدرس در یک بلوک دیسک (یا شاید به یک بخش سر سیلندر ) آدرس.

برخی از سیستم عامل ها از کاربر می خواهند که حداکثر اندازه فایل را در هنگام ایجاد فایل اختصاص دهد. سپس فایل را می توان به عنوان بلوک های دیسک پیوسته اختصاص داد. در آن صورت، آدرس بلوک فایل را تبدیل کنیدبه آدرس بلوک دیسک، سیستم عامل به سادگی آدرس بلوک فایل را اضافه می کندبه آدرس اولین بلوک دیسک تشکیل دهنده فایل. این طرح ساده است، اما فایل نمی تواند از اندازه ایجاد شده خود بیشتر شود.

سایر سیستم عامل ها به یک فایل اجازه رشد می دهند. بلوک‌های دیسک حاصل ممکن است به هم پیوسته نباشند، بنابراین نگاشت بلوک‌های منطقی به بلوک‌های فیزیکی بیشتر دخیل است.

برای مثال، MS-DOS از یک جدول تخصیص فایل ساده (FAT) استفاده می کرد. FAT یک ورودی برای هر بلوک دیسک دارد، [یادداشت 1] و آن ورودی مشخص می کند که آیا بلوک آن توسط یک فایل استفاده می شود یا خیر، و اگر چنین است، کدام بلوک (در صورت وجود) بلوک دیسک بعدی همان فایل است. بنابراین، تخصیص هر فایل به صورت یک لیست پیوندی در جدول نشان داده شده است. به منظور پیدا کردن آدرس دیسک بلوک فایل، سیستم عامل (یا ابزار دیسک) باید به ترتیب لیست پیوندی فایل را در FAT دنبال کند. بدتر از آن، برای یافتن یک بلوک دیسک رایگان، باید به صورت متوالی FAT را اسکن کند. برای MS-DOS، این جریمه بزرگی نبود، زیرا دیسک‌ها و فایل‌ها کوچک بودند و FAT ورودی‌های کمی داشت و زنجیره‌های فایل نسبتاً کوتاهی داشت. در سیستم فایل FAT12 (که در فلاپی دیسک‌ها و دیسک‌های سخت اولیه استفاده می‌شود)، بیش از 4080 ورودی وجود نداشت و FAT معمولاً در حافظه باقی می‌ماند. با بزرگتر شدن دیسک ها، معماری FAT با جریمه ها مواجه شد. در یک دیسک بزرگ با استفاده از FAT، ممکن است لازم باشد برای خواندن یا نوشتن محل دیسک بلوک فایل، خواندن دیسک انجام شود.

TOPS-20 (و احتمالاً TENEX ) از درخت 0 تا 2 استفاده می کند که شباهت هایی به درخت B دارد [ نیاز به منبع ] . یک بلوک دیسک 512 کلمه 36 بیتی بود. اگر فایل در یک بلوک کلمه 512 (2 9 ) قرار گیرد، دایرکتوری فایل به آن بلوک دیسک فیزیکی اشاره می کند. اگر فایل در 2 18 کلمه قرار گیرد، دایرکتوری به یک شاخص aux اشاره می کند. 512 کلمه این شاخص یا NULL خواهد بود (بلوک تخصیص داده نمی شود) یا به آدرس فیزیکی بلوک اشاره می کند. اگر فایل در 227 کلمه جا می‌گرفت، دایرکتوری به بلوکی اشاره می‌کند که دارای شاخص aux-aux است. هر ورودی یا NULL خواهد بود یا به یک شاخص aux اشاره می کند. در نتیجه، دیسک فیزیکی برای 2 27 بلوک می شودفایل word می تواند در دو خواندن دیسک قرار گیرد و در سوم خوانده شود.

سیستم فایل HFS+ و APFS اپل ، NTFS مایکروسافت ، [23] AIX (jfs2) و برخی از سیستم‌های فایل لینوکس ، مانند btrfs و Ext4 ، از B-trees استفاده می‌کنند.

درختان B * در فایل سیستم های HFS و Reiser4 استفاده می شوند.

سیستم فایل HAMMER DragonFly BSD از یک درخت B+ اصلاح شده استفاده می کند. [24]

عملکرد

یک B-tree با افزایش مقدار داده، کندتر از خطی بودن یک لیست پیوندی رشد می کند. در مقایسه با فهرست پرش ، هر دو ساختار عملکرد یکسانی دارند، اما B-tree برای رشد n مقیاس بهتری دارد. T-tree ، برای سیستم های پایگاه داده حافظه اصلی ، مشابه است اما فشرده تر است.

تغییرات

دسترسی به همزمانی

Lehman و Yao [25] نشان دادند که با پیوند دادن بلوک‌های درختی در هر سطح با یک اشاره‌گر «بعدی»، می‌توان از تمام قفل‌های خواندن اجتناب کرد (و بنابراین دسترسی همزمان تا حد زیادی بهبود یافت). این منجر به ساختار درختی می شود که در آن هر دو عملیات درج و جستجو از ریشه به برگ نزول می کنند. قفل‌های نوشتن فقط زمانی لازم است که بلوک درختی اصلاح شود. این امر همزمانی دسترسی چندین کاربر را به حداکثر می‌رساند، که یک نکته مهم برای پایگاه‌های داده و/یا سایر روش‌های ذخیره‌سازی ISAM مبتنی بر درخت B است . هزینه مرتبط با این بهبود این است که صفحات خالی را نمی توان در طول عملیات عادی از btree حذف کرد. (با این حال، برای استراتژی های مختلف برای پیاده سازی ادغام گره ها و کد منبع در [27] به [ 26 ] مراجعه کنید. )

پتنت ایالات متحده 5283894، اعطا شده در سال 1994، به نظر می رسد راهی برای استفاده از "روش دسترسی متا" [28] برای اجازه دسترسی همزمان درخت B+ و اصلاح بدون قفل را نشان می دهد. این تکنیک به درخت «بالا» برای جستجو و به‌روزرسانی با استفاده از شاخص‌های اضافی در حافظه که به بلوک‌های هر سطح در حافظه پنهان بلوک اشاره می‌کنند، دسترسی پیدا می‌کند. هیچ سازماندهی مجددی برای حذف ها مورد نیاز نیست و هیچ نشانگر «بعدی» در هر بلوک مانند Lehman و Yao وجود ندارد.

الگوریتم های موازی

از آنجایی که درختان B از نظر ساختار مشابه درختان قرمز-سیاه هستند ، الگوریتم های موازی برای درختان قرمز-سیاه را می توان برای درختان B نیز اعمال کرد.

همچنین ببینید

یادداشت ها

  1. ^ برای FAT، چیزی که در اینجا "بلوک دیسک" نامیده می شود، همان چیزی است که اسناد FAT آن را "خوشه" می نامند، که یک گروه با اندازه ثابت از یک یا چند بخش کامل دیسک فیزیکی به هم پیوسته است . برای اهداف این بحث، یک خوشه تفاوت معناداری با یک بخش فیزیکی ندارد.
  2. ^ دو مورد از اینها برای مقاصد خاص رزرو شده بودند، بنابراین تنها 4078 می تواند در واقع بلوک های دیسک (خوشه ها) را نشان دهد.

منابع

  1. ^ a b Bayer, R.; McCreight, E. (ژوئیه 1970). "سازماندهی و نگهداری شاخص های بزرگ سفارش داده شده" (PDF) . مجموعه مقالات کارگاه آموزشی ACM SIGFIDET (در حال حاضر SIGMOD) در سال 1970 در مورد توضیحات، دسترسی و کنترل داده ها - SIGFIDET '70 . آزمایشگاه تحقیقات علمی بوئینگ پ. 107. doi : 10.1145/1734663.1734671 . S2CID  26930249 .
  2. ^ a b c d Comer 1979 .
  3. ^ a b c Bayer & McCreight 1972 .
  4. ^ کومر 1979 ، ص. 123 پاورقی 1.
  5. a b Weiner, Peter G. (30 اوت 2013). "4- Edward M McCreight" - از طریق Vimeo.
  6. «مرکز توسعه حرفه ای استنفورد» . scpd.stanford.edu . بایگانی شده از نسخه اصلی در 2014-06-04 . بازیابی 2011-01-16 .
  7. ^ a b Knuth 1998 ، ص. 483.
  8. ^ Folk & Zoellick 1992 , p. 362.
  9. Folk & Zoellick 1992 .
  10. ^ Folk & Zoellick 1992 , p. 363.
  11. ^ Bayer & McCreight (1972) با گفتن اینکه یک عنصر شاخص یک جفت (از نظر فیزیکی مجاور) از ( x a ) است که در آن x کلید است و a برخی از اطلاعات مرتبط است، از این موضوع اجتناب کردند. اطلاعات مرتبط ممکن است نشانگر یک رکورد یا رکوردهایی در یک دسترسی تصادفی باشد، اما اینکه چه چیزی واقعاً مهم نیست. Bayer & McCreight (1972) بیان می کند، "برای این مقاله، اطلاعات مرتبط دیگر مورد توجه نیست."
  12. ^ Folk & Zoellick 1992 , p. 379.
  13. کنوت 1998 ، ص. 488.
  14. ^ a b c d e f Tomašević، Milo (2008). الگوریتم ها و ساختارهای داده . بلگراد، صربستان: Akademska misao. صص 274-275. شابک 978-86-7466-328-8.
  15. Rigin AM، Shershakov SA (10-09-2019). "افزونه SQLite RDBMS برای نمایه سازی داده ها با استفاده از اصلاحات درختی B" . مجموعه مقالات موسسه برنامه نویسی سیستم راس . موسسه برنامه نویسی سیستم RAS (ISP RAS). 31 (3): 203-216. doi : 10.15514/ispras-2019-31(3)-16 . S2CID 203144646 . بازیابی شده در 29-08-2021 . 
  16. Counted B-Trees ، بازیابی شده در 25/01/2010
  17. ^ Seagate Technology LLC، راهنمای محصول: Barracuda ES.2 Serial ATA، Rev. F.، انتشار 100468393، 2008 [1] ، صفحه 6
  18. ^ a b c کلپمن، مارتین (2017)، طراحی برنامه های کاربردی داده فشرده ، سباستوپل ، کالیفرنیا : رسانه O'Reilly ، ص. 80، شابک 978-1-449-37332-0
  19. جان جانینک. "اجرای حذف در B+-Trees". بخش "4 حذف تنبل" .
  20. ^ کومر 1979 ، ص. 127; کورمن و همکاران 2001 ، صفحات 439-440
  21. «حذف در درخت B» (PDF) . cs.rhodes.edu . بازبینی شده در 24 مه 2022 .
  22. «Cache Oblivious B-trees» . دانشگاه ایالتی نیویورک (SUNY) در استونی بروک . بازیابی شده در 2011-01-17 .
  23. ^ مارک روسینوویچ . "داخل Win2K NTFS، قسمت 1" . شبکه توسعه دهندگان مایکروسافت بایگانی شده از نسخه اصلی در 13 آوریل 2008 . بازیابی شده در 2008-04-18 .
  24. متیو دیلون (۲۱-۰۶-۲۰۰۸). "The HAMMER Filessystem" (PDF) .
  25. ^ لمن، فیلیپ ال. یائو، اس. بینگ (1981). "قفل کردن کارآمد برای عملیات همزمان در درختان B". معاملات ACM در سیستم های پایگاه داده . 6 (4): 650-670. doi : 10.1145/319628.319663 . S2CID 10756181 . 
  26. ^ عنوان مقاله [ URL خالی PDF ]
  27. «دانلودها - btree با همزمانی بالا - کد B-Tree با همزمانی بالا در میزبانی پروژه C - GitHub» . GitHub . بازیابی شده در 2014-01-27 .
  28. «روش دسترسی متا شاخص B-tree همزمان بدون قفل برای گره‌های کش» .
عمومی

مقالات اصلی

  • بایر، رودولف ؛ McCreight, E. (ژوئیه 1970)، سازماندهی و نگهداری شاخص های بزرگ ، جلد. گزارش علوم ریاضی و اطلاعات شماره 20، آزمایشگاه های تحقیقات علمی بوئینگ.
  • بایر، رودولف (1971)، دودویی B-Trees برای حافظه مجازی ، مجموعه مقالات 1971 ACM-SIGFIDET کارگاه در مورد توصیف داده، دسترسی و کنترل، سن دیگو، کالیفرنیا.

پیوندهای خارجی

بارگیری انبوه