עץ B

מתוך ויקיפדיה, האנציקלופדיה החופשית
ערך ללא מקורות
בערך זה אין מקורות ביבליוגרפיים כלל, לא ברור על מה מסתמך הכתוב וייתכן שמדובר במחקר מקורי.

אנא עזרו לשפר את אמינות הערך באמצעות הבאת מקורות לדברים ושילובם בגוף הערך בצורת קישורים חיצוניים והערות שוליים.
אם אתם סבורים כי ניתן להסיר את התבנית, ניתן לציין זאת בדף השיחה.

ערך ללא מקורות
בערך זה אין מקורות ביבליוגרפיים כלל, לא ברור על מה מסתמך הכתוב וייתכן שמדובר במחקר מקורי.

אנא עזרו לשפר את אמינות הערך באמצעות הבאת מקורות לדברים ושילובם בגוף הערך בצורת קישורים חיצוניים והערות שוליים.
אם אתם סבורים כי ניתן להסיר את התבנית, ניתן לציין זאת בדף השיחה.

במדעי המחשב, עץ Bאנגלית: B-tree) הוא מבנה נתונים בצורת עץ, הכללה של עץ חיפוש בינארי, בכך שלכל צומת יכולים להיות יותר מ-2 בנים. עץ B שומר מידע ממוין (לפי מפתח) ומאפשר חיפוש, גישה סדרתית, הוספת איברים ומחיקתם בסיבוכיות לוגרתמית.

עץ B מסדר m מקיים את התכונות הבאות:

  1. לכל צומת יש לכל היותר m ילדים.
  2. לכל צומת שאינו עלה ואינו השורש, יש לפחות ⌈m/2⌉ ילדים.
  3. אם השורש אינו עלה, יש לו לפחות 2 ילדים.
  4. צומת פנימי עם k ילדים מכיל בדיוק k-1 מפתחות.
  5. כל העלים בעומק זהה.

להבדיל מעצי חיפוש מאוזנים, עץ B מיועד לעבודה יעילה במערכות שקוראות וכותבות בלוקים גדולים של מידע. השימוש בו שכיח במסדי נתונים ובמערכות קבצים.

עץ +B הוא וריאנט של עץ B. ההבדל בין עץ B לבין עץ +B הוא בכך שבעץ +B המפתחות בצמתים הם העתק של המפתחות בעלים, ואילו בעץ B כל איבר נמצא בצומת פנימי או בעלה. בנוסף לכך בעץ +B יש בדרך כלל רשימה המקשרת בין העלים לאפשר מעבר סדרתי מהיר.


קישורים חיצוניים[עריכת קוד מקור | עריכה]

ויקישיתוף מדיה וקבצים בנושא עץ B בוויקישיתוף
  • עץ B, באתר MathWorld (באנגלית)
ערך זה הוא קצרמר בנושא מדעי המחשב. אתם מוזמנים לתרום לוויקיפדיה ולהרחיב אותו.