شجرة B

📅 آخر تحديث: ٢٦ يوليو ٢٠٢٦
✍️ نُشر في: ٢٦ يوليو ٢٠٢٦
📷 يحتوي على 19 صور
الموسوعة الحرة

في علم الحاسوب ، تُعدّ شجرة B بنية بيانات شجرية ذاتية التوازن، تحافظ على البيانات مُرتبةً وتتيح عمليات البحث والوصول التسلسلي والإضافات والحذف في زمن لوغاريتمي . تُعمّم شجرة B شجرة البحث الثنائية ، مما يسمح للعقدة الواحدة بأن يكون لها أكثر من فرعين. [ 2 ]

بفضل السماح بوجود عدد أكبر من الأبناء تحت عقدة واحدة مقارنةً بشجرة البحث الثنائية ذاتية التوازن ، تُقلل شجرة B من ارتفاع الشجرة وتضع البيانات في عدد أقل من الكتل المنفصلة. يُعد هذا الأمر بالغ الأهمية للأشجار المخزنة في وحدات التخزين الثانوية (مثل محركات الأقراص)، حيث تتميز هذه الأنظمة بزمن استجابة مرتفع نسبيًا وتتعامل مع كتل بيانات كبيرة نسبيًا ، ومن هنا يأتي استخدام شجرة B في قواعد البيانات وأنظمة الملفات . ويظل هذا ميزة رئيسية عند تخزين الشجرة في الذاكرة، حيث تعتمد أنظمة الحاسوب الحديثة بشكل كبير على ذاكرة التخزين المؤقت لوحدة المعالجة المركزية . وبالمقارنة مع القراءة من ذاكرة التخزين المؤقت، فإن القراءة من الذاكرة بعد فقدان البيانات من ذاكرة التخزين المؤقت تستغرق وقتًا طويلًا. [ 3 ] [ 4 ]

تاريخ

أثناء عملهما في مختبرات أبحاث بوينغ ، ابتكر رودولف باير وإدوارد إم. مكريت أشجار B لإدارة صفحات الفهرس بكفاءة للملفات الكبيرة ذات الوصول العشوائي. وكان افتراضهما الأساسي أن الفهارس ستكون ضخمة للغاية بحيث لا يمكن استيعاب سوى أجزاء صغيرة من الشجرة في الذاكرة الرئيسية. نُشرت ورقة باير ومكريت البحثية بعنوان " تنظيم وصيانة الفهارس المرتبة الكبيرة " [ 1 ] لأول مرة في يوليو 1970، ثم نُشرت لاحقًا في مجلة "أكتا إنفورماتيكا" [ 5 ] .

لم يوضح باير وماكريت قط ما الذي يرمز إليه حرف B ، إن كان له معنى أصلاً؛ وقد اقتُرحت معانٍ مثل بوينغ ، ومتوازن ، وبين ، وعريض ، وكثيف ، وباير . [ 6 ] [ 7 ] [ 8 ] وعندما سُئل ماكريت: "أريد أن أعرف ما الذي يرمز إليه حرف B في B-Tree"، أجاب [ 7 ] :

الجميع يفعل ذلك!

إذن، ليس لديك أدنى فكرة عما يمكن أن يتحول إليه حديث الغداء. كنا أنا ورودي نتناول الغداء، وكان علينا أن نُطلق على الأمر اسمًا... كنا نعمل في شركة بوينغ آنذاك، لكن لم يكن بإمكاننا استخدام الاسم دون استشارة المحامين. لذا، ها هو الاسم يبدأ بحرف الباء.

الأمر يتعلق بتوازن B. وهناك B أخرى.

كان رودي هو المؤلف الرئيسي. كان رودي (باير) يكبرني بعدة سنوات، وكان لديه... منشورات أكثر بكثير مما لدي. لذا فهذا حرف ب آخر.

وهكذا، على مائدة الغداء، لم نتوصل أبداً إلى حل بشأن ما إذا كان هناك واحد من تلك الخيارات أكثر منطقية من البقية.

ما يحب رودي قوله هو أنه كلما فكرت أكثر في معنى حرف B في B-Tree، كلما فهمت أشجار B بشكل أفضل!

تعريف

وفقًا لتعريف كنوت ، فإن شجرة B من الرتبة m هي شجرة تحقق الخصائص التالية: [ 9 ]

  1. تحتوي كل عقدة على عدد أقصى من الأبناء m .
  2. كل عقدة، باستثناء الجذر والأوراق، لها على الأقل ⌈ m /2⌉ من الأبناء.
  3. تحتوي العقدة الجذرية على طفلين على الأقل ما لم تكن ورقة.
  4. تظهر جميع الأوراق على نفس المستوى.
  5. تحتوي العقدة غير الطرفية التي تحتوي على k من الأبناء على k - 1 من المفاتيح.

تعمل مفاتيح كل عقدة غير طرفية كقيم فاصلة تقسم فروعها. على سبيل المثال، إذا كانت لعقدة داخلية ثلاث عقد فرعية (أو فروع فرعية)، فيجب أن يكون لها مفتاحان: 1 و 2 . ستكون جميع القيم في الفرع الأيسر أقل من 1 ، وجميع القيم في الفرع الأوسط بين 1 و 2 ، وجميع القيم في الفرع الأيمن أكبر من 2 .

العقد الداخلية
العقد الداخلية (وتُعرف أيضًا بالعقد الجوهرية ) هي جميع العقد باستثناء العقد الطرفية والعقدة الجذرية. وعادةً ما تُمثَّل كمجموعة مُرتبة من العناصر ومؤشرات الأبناء. تحتوي كل عقدة داخلية على حد أقصى U من الأبناء وحد أدنى L من الأبناء. وبالتالي، يكون عدد العناصر دائمًا أقل بواحد من عدد مؤشرات الأبناء (يتراوح عدد العناصر بين L - 1 و U - 1). يجب أن تكون قيمة U إما 2L أو 2L - 1؛ لذلك، تكون كل عقدة داخلية ممتلئة إلى النصف على الأقل. تشير العلاقة بين U و L إلى إمكانية ضم عقدتين نصف ممتلئتين لتكوين عقدة صالحة، كما يمكن تقسيم عقدة ممتلئة إلى عقدتين صالحتين (إذا كان هناك مساحة كافية لدفع عنصر واحد إلى العقدة الأب). تُتيح هذه الخصائص إمكانية حذف وإضافة قيم جديدة إلى شجرة B مع تعديل الشجرة للحفاظ على خصائصها.
العقدة الجذرية
يبلغ عدد أبناء العقدة الجذرية الحد الأعلى نفسه لعدد أبناء العقد الداخلية، ولكن ليس لها حد أدنى. على سبيل المثال، عندما يكون عدد العناصر في الشجرة بأكملها أقل من L − 1، ستكون العقدة الجذرية هي العقدة الوحيدة في الشجرة التي ليس لها أبناء على الإطلاق.
العقد الورقية
في مصطلحات كنوت، تُعتبر العقد "الورقية" هي كائنات/أجزاء البيانات الفعلية. أما العقد الداخلية التي تقع على مستوى واحد أعلى من هذه العقد الورقية، فهي ما يُطلق عليه مؤلفون آخرون اسم "الأوراق": إذ تخزن هذه العقد المفاتيح فقط (بحد أقصى m - 1، وبحد أدنى m / 2 - 1 إذا لم تكن العقدة الجذرية) والمؤشرات (مؤشر واحد لكل مفتاح) إلى العقد التي تحمل كائنات/أجزاء البيانات.

يمكن لشجرة B ذات العمق n +1 أن تستوعب ما يقارب U ضعف عدد العناصر التي تستوعبها شجرة B ذات العمق n ، ولكن تكلفة عمليات البحث والإدراج والحذف تزداد مع عمق الشجرة. وكما هو الحال مع أي شجرة متوازنة، فإن التكلفة تنمو بوتيرة أبطأ بكثير من عدد العناصر.

تخزن بعض الأشجار المتوازنة القيم فقط في العقد الطرفية، وتستخدم أنواعًا مختلفة من العقد للعقد الطرفية والعقد الداخلية. أما أشجار B، فتحتفظ بالقيم في كل عقدة في الشجرة باستثناء العقد الطرفية.

اختلافات في المصطلحات

لا تتسم الأدبيات المتعلقة بأشجار B بالتوحيد في مصطلحاتها. [ 10 ]

عرّف باير وماكريت (1972) [ 5 ] ، وكومر (1979) [ 2 ] ، وغيرهم، رتبة شجرة B بأنها الحد الأدنى لعدد المفاتيح في عقدة غير جذرية. ويشير فولك وزوليك [ 11 ] إلى أن المصطلحات غامضة لأن الحد الأقصى لعدد المفاتيح غير واضح. فقد تحتوي شجرة B من الرتبة 3 على 6 مفاتيح كحد أقصى أو 7 مفاتيح كحد أقصى. ويتجنب كنوت (1998) هذه المشكلة بتعريف الرتبة بأنها الحد الأقصى لعدد الأبناء (وهو أكبر بواحد من الحد الأقصى لعدد المفاتيح). [ 9 ]

يُعدّ مصطلح "الورقة" غير متسق أيضًا. فقد اعتبر باير وماكريت (1972) [ 5 ] مستوى الورقة هو أدنى مستوى للمفاتيح، بينما اعتبره كنوت مستوىً أدنى من أدنى مستوى للمفاتيح. [ 11 ] توجد خيارات تنفيذية عديدة. ففي بعض التصاميم، قد تحتوي الأوراق على سجل البيانات بأكمله؛ وفي تصاميم أخرى، قد تحتوي الأوراق على مؤشرات فقط إلى سجل البيانات. ولا تُعدّ هذه الخيارات أساسية لفكرة شجرة B. [ 12 ]

لتبسيط الأمور، يفترض معظم المؤلفين وجود عدد ثابت من المفاتيح التي تتسع لها العقدة. والافتراض الأساسي هو أن حجم المفتاح وحجم العقدة ثابتان. عمليًا، يمكن استخدام مفاتيح ذات أطوال متغيرة. [ 13 ]

وصف غير رسمي

شجرة من النوع B ( باير وماكريت 1972 ) من الرتبة 5 ( كنوث 1998 )

بنية العقدة

كما هو الحال مع الأشجار الأخرى، يمكن تمثيل أشجار B كمجموعة من ثلاثة أنواع من العقد: الجذر ، والداخلي (المعروف أيضًا باسم الداخلي)، والورقة .

لاحظ تعريفات المتغيرات التالية:

  • K - الحد الأقصى لعدد مفاتيح البحث المحتملة لكل عقدة في شجرة B. (هذه القيمة ثابتة على كامل الشجرة.)
  • pt i - المؤشر إلى عقدة فرعية تبدأ شجرة فرعية.
  • pr i - المؤشر إلى سجل يخزن البيانات.
  • k i - مفتاح البحث عند فهرس العقدة i الذي يبدأ من الصفر .

في أشجار B، يتم الاحتفاظ بالخصائص التالية لهذه العقد:

  • إذا كان k i موجودًا في أي عقدة في شجرة B، فإن k i -1 موجود في تلك العقدة حيثأنا≥1{\displaystyle i\geq 1}.
  • جميع العقد الورقية لها نفس عدد الأسلاف (أي أنها جميعها على نفس العمق).

لكل عقدة داخلية في شجرة B الشكل التالي:

بنية العقدة الداخلية
الجزء 0ك ٠pr 0الجزء 1ك 1pr 1الجزء الثاني...k K -1الجزء كpr K -1
بنية مؤشر العقدة الداخلية
الجزء 0الجزء الأولpr i
متىk 0 موجودk i -1 و k i موجودانk i -1 موجود،و k i غير موجودk i -1 و k i غير موجودينk i موجودk i غير موجود
يشير إلى الشجرة الفرعية التي تحتوي على جميع مفاتيح البحث، P t  :P t < k 0k i -1 < P t < k iP t > k i -1الجزء i فارغ.يشير إلى سجل بقيمة P r = k ipr i فارغ.

لكل عقدة طرفية في شجرة B الشكل التالي:

بنية العقدة الورقية
pr 0ك ٠pr 1ك 1...pr K -1k K -1
بنية مؤشر العقدة الطرفية
pr i عندما k i موجودpr i عندما لا يكون k i موجودًا
يشير إلى سجل بقيمة تساوي k i .هنا، pr i فارغ.

تم تلخيص حدود العقدة في الجدول أدناه:

نوع العقدةعدد المفاتيحعدد العقد الفرعية
مينالأعلىمينالأعلى
العقدة الجذرية عندما تكون عقدة طرفية0ك00
العقدة الجذرية عندما تكون عقدة داخلية1ك2 [ 14 ]ك+1{\displaystyle K+1}
العقدة الداخلية⌊ك/2⌋{\displaystyle \lfloor K/2\rfloor }ك⌈(ك+1)/2⌉≡⌊ك/2⌋+1{\displaystyle \lceil (K+1)/2\rceil \equiv \lfloor K/2\rfloor +1}ك+1{\displaystyle K+1}
عقدة الورقة⌈ك/2⌉{\displaystyle \lceil K/2\rceil }ك00

الإضافة والحذف

للحفاظ على النطاق المحدد مسبقًا للعقد الفرعية، يمكن ضم العقد الداخلية أو تقسيمها.

عادةً، يتم اختيار عدد المفاتيح بحيث يتراوح بين d و2د{\displaystyle 2d}، حيث يمثل d الحد الأدنى لعدد المفاتيح، ود+1{\displaystyle d+1}يمثل الحد الأدنى لدرجة أو عامل التفرع في الشجرة. ويضمن العامل 2 إمكانية تقسيم العقد أو دمجها.

إذا كانت العقدة الداخلية2د{\displaystyle 2d}المفاتيح، ثم يمكن إضافة مفتاح إلى تلك العقدة عن طريق تقسيم الافتراضي2د+1{\displaystyle 2d+1}يمكن تقسيم العقدة الرئيسية إلى عقدتين رئيسيتين (d) ونقل المفتاح الذي كان سيقع بينهما إلى العقدة الأصلية. تحتوي كل عقدة منقسمة على الحد الأدنى المطلوب من المفاتيح. وبالمثل، إذا كانت كل من العقدة الداخلية وجارتها تحتوي على d من المفاتيح، فيمكن حذف مفتاح من العقدة الداخلية بدمجه مع جارتها. سيؤدي حذف المفتاح إلى جعل العقدة الداخلية تحتوي على d من المفاتيح.د-1{\displaystyle d-1}المفاتيح؛ سيؤدي ضم الجار إلى إضافة d مفاتيح بالإضافة إلى مفتاح آخر يتم جلبه من والد الجار. والنتيجة هي عقدة كاملة من2د{\displaystyle 2d}مفاتيح.

يتم الحفاظ على توازن شجرة B بعد الإدخال عن طريق تقسيم العقدة التي قد تكون ممتلئة بشكل زائد، من2د+1{\displaystyle 2d+1}يتم تقسيم المفاتيح إلى فرعين من نوع d -key، ثم يُضاف مفتاح القيمة الوسطى إلى الفرع الأصل. لا يزداد العمق إلا عند تقسيم الفرع الأصل، مما يحافظ على التوازن. وبالمثل، يُحافظ على توازن شجرة B بعد الحذف عن طريق دمج أو إعادة توزيع المفاتيح بين الفروع للحفاظ على الحد الأدنى لعدد المفاتيح d -key للعقد غير الجذرية. يقلل الدمج عدد المفاتيح في الفرع الأصل، مما قد يُجبره على دمج أو إعادة توزيع المفاتيح مع فروعه، وهكذا. التغيير الوحيد في العمق يحدث عندما يكون للفرع الأصل فرعان، أحدهما من نوع d والآخر (انتقاليًا).د-1{\displaystyle d-1}المفاتيح، وفي هذه الحالة يتم دمج الشقيقين والوالد، مما يقلل العمق بمقدار واحد.

سيزداد هذا العمق ببطء مع إضافة العناصر إلى الشجرة، ولكن الزيادة في العمق الإجمالي نادرة الحدوث، وتؤدي إلى أن تكون جميع العقد الورقية أبعد بعقدة واحدة عن الجذر.

مقارنة بالأشجار الأخرى

نظرًا لأنه يُسمح بنطاق من العقد الفرعية، فإن أشجار B لا تحتاج إلى إعادة التوازن بنفس وتيرة أشجار البحث الأخرى ذاتية التوازن، ولكنها قد تهدر بعض المساحة لأن العقد ليست ممتلئة تمامًا.

تتمتع أشجار B بمزايا كبيرة مقارنةً بالتطبيقات البديلة عندما يتجاوز وقت الوصول إلى بيانات عقدة ما وقت معالجة تلك البيانات بكثير، إذ يمكن حينها توزيع تكلفة الوصول إلى العقدة على عمليات متعددة داخلها. يحدث هذا عادةً عند تخزين بيانات العقدة في وحدة تخزين ثانوية ، مثل محركات الأقراص . من خلال زيادة عدد المفاتيح داخل كل عقدة داخلية ، يقل ارتفاع الشجرة، ويقل عدد عمليات الوصول المكلفة إلى العقد. بالإضافة إلى ذلك، تقل الحاجة إلى إعادة توازن الشجرة. يعتمد الحد الأقصى لعدد العقد الفرعية على المعلومات التي يجب تخزينها لكل عقدة فرعية وحجم كتلة القرص الكاملة أو حجم مماثل في وحدة التخزين الثانوية. في حين أن شرح أشجار B ذات 2-3 عقد أسهل، فإن أشجار B العملية التي تستخدم وحدة تخزين ثانوية تحتاج إلى عدد كبير من العقد الفرعية لتحسين الأداء.

المتغيرات

قد يشير مصطلح شجرة B إلى تصميم محدد أو فئة عامة من التصاميم. بالمعنى الضيق، تخزن شجرة B المفاتيح في عقدها الداخلية، ولكن ليس بالضرورة أن تخزنها في سجلات الأوراق. تشمل الفئة العامة أنواعًا مختلفة مثل شجرة B+ ، وشجرة B * ، وشجرة B *+ .

  • في شجرة B+ ، لا تخزن العقد الداخلية أي مؤشرات إلى السجلات؛ لذا تُخزن جميع مؤشرات السجلات في العقد الطرفية. إضافةً إلى ذلك، قد تتضمن العقدة الطرفية مؤشرًا إلى العقدة الطرفية التالية لتسريع الوصول التسلسلي. [ 2 ] نظرًا لأن العقد الداخلية في شجرة B+ تحتوي على عدد أقل من المؤشرات، يمكن لكل عقدة استيعاب عدد أكبر من المفاتيح، مما يجعل الشجرة أقل عمقًا وبالتالي أسرع في البحث.
  • تُوازن شجرة B * عدد أكبر من العقد الداخلية المتجاورة للحفاظ على كثافة أكبر للعقد الداخلية. [ 2 ] يضمن هذا النوع أن تكون العقد غير الجذرية ممتلئة بنسبة 2/3 على الأقل بدلاً من 1/2. [ 15 ] بما أن الجزء الأكثر تكلفة في عملية إدراج عقدة في شجرة B هو تقسيم العقدة، تُصمم أشجار B * لتأجيل عملية التقسيم لأطول فترة ممكنة. [ 16 ] وللحفاظ على ذلك، بدلاً من تقسيم العقدة فور امتلائها، تُشارك مفاتيحها مع عقدة مجاورة. تُعد عملية التوسيع هذه أقل تكلفة من التقسيم لأنها تتطلب فقط نقل المفاتيح بين العقد الموجودة، دون الحاجة إلى تخصيص ذاكرة لعقدة جديدة. [ 16 ] عند الإدراج، يتم أولاً التحقق مما إذا كانت العقدة تحتوي على مساحة فارغة، وإذا كان الأمر كذلك، يُدرج المفتاح الجديد في العقدة. مع ذلك، إذا كانت العقدة ممتلئة (أي تحتوي على m − 1 مفتاحًا، حيث m هو ترتيب الشجرة باعتباره الحد الأقصى لعدد المؤشرات إلى الأشجار الفرعية من عقدة واحدة)، فيجب التحقق مما إذا كانت العقدة الشقيقة اليمنى موجودة ولديها مساحة فارغة. إذا كانت العقدة الشقيقة اليمنى تحتوي على j < m − 1 مفتاحًا، فسيتم إعادة توزيع المفاتيح بين العقدتين الشقيقتين بالتساوي قدر الإمكان. لهذا الغرض، تُعتبر m − 1 مفتاحًا من العقدة الحالية، والمفتاح الجديد المُضاف، ومفتاح واحد من العقدة الأب، و j مفتاحًا من العقدة الشقيقة، بمثابة مصفوفة مرتبة من m + j + 1 مفتاحًا. تُقسم المصفوفة إلى نصفين بحيث تبقى ⌊ ( m + j + 1)/ 2⌋ مفتاحًا في العقدة الحالية، ويُضاف المفتاح التالي (الأوسط) إلى العقدة الأب، وتذهب المفاتيح المتبقية إلى العقدة الشقيقة اليمنى. [ 16 ] (قد ينتهي المطاف بالمفتاح المُضاف حديثًا في أي من المواقع الثلاثة). الوضع مشابه عندما يكون الشقيق الأيمن ممتلئًا والشقيق الأيسر غير ممتلئ. [ 16 ] عندما تكون كلتا العقدتين الشقيقتين ممتلئتين، يتم تقسيم العقدتين (العقدة الحالية وإحدى العقد الشقيقة) إلى ثلاث عقد، ويتم نقل مفتاح إضافي إلى أعلى الشجرة إلى العقدة الأب. [ 16 ] إذا كانت العقدة الأب ممتلئة، فإن عملية الإضافة/التقسيم تنتشر باتجاه العقدة الجذرية. [ 16 ] مع ذلك، فإن حذف العقد أكثر تعقيدًا من إضافتها.
  • تجمع شجرة B *+ بين ميزات شجرة B+ الرئيسية وشجرة B * معًا. [ 17 ]
  • يمكن تحويل أشجار B إلى أشجار إحصائية ترتيبية للسماح بعمليات بحث سريعة عن السجل رقم N بترتيب المفتاح، أو حساب عدد السجلات بين أي سجلين، والعديد من العمليات الأخرى ذات الصلة. [ 18 ]

استخدام شجرة B في قواعد البيانات

وقت البحث عن الملفات المصنفة

يمكن وصف خوارزميات الفرز والبحث بعدد عمليات المقارنة التي يجب إجراؤها باستخدام ترميز الترتيب . على سبيل المثال، يمكن إجراء بحث ثنائي في جدول مُرتب يحتوي على N سجلًا في حوالي ⌈ log 2 N ⌉ مقارنة. إذا كان الجدول يحتوي على 1,000,000 سجل، فيمكن تحديد موقع سجل معين بـ 20 مقارنة على الأكثر: ⌈ log 2 (1,000,000) ⌉ = 20 .

لطالما حُفظت قواعد البيانات الضخمة على محركات الأقراص. يتجاوز الوقت اللازم لقراءة سجل من محرك الأقراص بكثير الوقت اللازم لمقارنة المفاتيح بمجرد توفر السجل، وذلك بسبب زمن البحث وتأخير الدوران. قد يتراوح زمن البحث بين 0 و20 مللي ثانية أو أكثر، ويبلغ متوسط ​​تأخير الدوران حوالي نصف فترة الدوران. بالنسبة لمحرك أقراص بسرعة 7200 دورة في الدقيقة، تبلغ فترة الدوران 8.33 مللي ثانية. أما بالنسبة لمحرك أقراص مثل Seagate ST3500320NS، فيبلغ زمن البحث بين المسارات 0.8 مللي ثانية، ويبلغ متوسط ​​زمن البحث للقراءة 8.5 مللي ثانية. [ 19 ] ولتبسيط الأمر، نفترض أن القراءة من القرص تستغرق حوالي 10 مللي ثانية.

إن الوقت اللازم لتحديد موقع سجل واحد من بين مليون سجل في المثال أعلاه سيكون 20 عملية قراءة من القرص، تستغرق كل منها 10 مللي ثانية، وهو ما يعادل 0.2 ثانية.

يتم تقليل وقت البحث لأن السجلات الفردية تُجمع معًا في كتلة قرص . قد يبلغ حجم كتلة القرص 16 كيلوبايت. إذا كان حجم كل سجل 160 بايت، فيمكن تخزين 100 سجل في كل كتلة. كان وقت قراءة القرص المذكور أعلاه خاصًا بكتلة كاملة. بمجرد أن يصبح رأس القراءة/الكتابة في مكانه، يمكن قراءة كتلة قرص واحدة أو أكثر بتأخير بسيط. مع وجود 100 سجل في كل كتلة، لا تحتاج المقارنات الست الأخيرة تقريبًا إلى أي قراءات من القرص، حيث تتم جميع المقارنات ضمن كتلة القرص الأخيرة المقروءة.

لزيادة سرعة البحث، يجب تقليل الوقت اللازم لإجراء أول 13 إلى 14 مقارنة (والتي تتطلب كل منها الوصول إلى القرص).

أداء المؤشر

يمكن استخدام فهرس شجرة B لتحسين الأداء. يُنشئ فهرس شجرة B بنية شجرية متعددة المستويات تُقسّم قاعدة البيانات إلى كتل أو صفحات ذات حجم ثابت. يُمكن استخدام كل مستوى من هذه الشجرة لربط تلك الصفحات عبر عنوان، مما يسمح لصفحة (تُعرف بالعقدة أو الصفحة الداخلية) بالإشارة إلى صفحة أخرى ذات صفحات طرفية في أدنى مستوى. عادةً ما تكون إحدى الصفحات هي نقطة بداية الشجرة، أو "الجذر". من هنا يبدأ البحث عن مفتاح معين، مُتتبعًا مسارًا ينتهي بصفحة طرفية. ستكون معظم الصفحات في هذه البنية صفحات طرفية تُشير إلى صفوف مُحددة في الجدول.

نظرًا لأن كل عقدة (أو صفحة داخلية) يمكن أن تحتوي على أكثر من فرعين، فإن فهرس شجرة B عادةً ما يكون أقصر ارتفاعًا (المسافة من الجذر إلى أبعد ورقة) من فهرس شجرة البحث الثنائية. في المثال أعلاه، قلّصت عمليات قراءة القرص الأولية نطاق البحث بمقدار النصف. يمكن تحسين ذلك بإنشاء فهرس مساعد يحتوي على السجل الأول في كل كتلة قرص (يُسمى أحيانًا فهرسًا متفرقًا ). سيكون حجم هذا الفهرس المساعد 1% من حجم قاعدة البيانات الأصلية، ولكن يمكن البحث فيه بسرعة. سيُخبرنا العثور على إدخال في الفهرس المساعد أي كتلة نبحث فيها في قاعدة البيانات الرئيسية؛ بعد البحث في الفهرس المساعد، سيتعين علينا البحث في تلك الكتلة فقط من قاعدة البيانات الرئيسية - بتكلفة قراءة قرص إضافية.

في المثال أعلاه، سيحتوي الفهرس على 10000 مدخل، وسيتطلب 14 مقارنة كحد أقصى لعرض النتيجة. وكما هو الحال في قاعدة البيانات الرئيسية، ستُجرى المقارنات الست الأخيرة تقريبًا في الفهرس المساعد على نفس كتلة القرص. ويمكن البحث في الفهرس بحوالي ثماني عمليات قراءة من القرص، والوصول إلى السجل المطلوب بتسع عمليات قراءة.

يمكن تكرار عملية إنشاء فهرس مساعد لإنشاء فهرس مساعد للفهرس المساعد. سيؤدي ذلك إلى إنشاء فهرس مساعد-مساعد لا يحتاج إلا إلى 100 مدخل، ويمكن تخزينه في كتلة قرص واحدة.

بدلاً من قراءة 14 كتلة قرص للعثور على السجل المطلوب، نحتاج فقط إلى قراءة 3 كتل. هذا التقسيم هو الفكرة الأساسية وراء إنشاء شجرة B، حيث تُشكّل كتل القرص تسلسلاً هرمياً من المستويات لتكوين الفهرس. قراءة الكتلة الأولى (والوحيدة) من فهرس 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 هي التنفيذ القياسي للفهرسة في جميع قواعد البيانات العلائقية تقريبًا ، وتستخدمها أيضًا العديد من قواعد البيانات غير العلائقية. [ 20 ]

الإضافات والحذف

إذا لم تتغير قاعدة البيانات ، فإن إنشاء الفهرس يصبح بسيطًا، ولا يحتاج الفهرس إلى أي تعديل. أما إذا طرأت تغييرات، فإن إدارة قاعدة البيانات وفهرسها تتطلب عمليات حسابية إضافية.

يُعدّ حذف السجلات من قاعدة البيانات عملية سهلة نسبيًا. إذ يمكن أن يبقى الفهرس كما هو، ويُمكن ببساطة وضع علامة "محذوف" على السجل. وتبقى قاعدة البيانات مرتبة. أما إذا كان هناك عدد كبير من عمليات الحذف المؤجلة ، فإن البحث والتخزين يصبحان أقل كفاءة. [ 21 ]

قد تكون عمليات الإضافة بطيئة للغاية في الملفات التسلسلية المرتبة، نظرًا لضرورة توفير مساحة للسجل المُضاف. فإضافة سجل قبل السجل الأول تتطلب إزاحة جميع السجلات إلى الأسفل بمقدار خانة واحدة، وهي عملية مكلفة للغاية وغير عملية. أحد الحلول هو ترك بعض المساحات الفارغة. فبدلًا من تكديس جميع السجلات في كتلة واحدة، يمكن أن تحتوي الكتلة على مساحة فارغة تسمح بعمليات الإضافة اللاحقة. وتُعلّم هذه المساحات كما لو كانت سجلات "محذوفة".

تُعدّ عمليات الإضافة والحذف سريعة طالما توفرت مساحة كافية على الكتلة. إذا لم تتسع الكتلة لعملية الإضافة، فيجب البحث عن مساحة فارغة على كتلة مجاورة وتعديل الفهارس المساعدة. في أفضل الأحوال، تتوفر مساحة كافية في مكان قريب لتقليل إعادة تنظيم الكتل إلى أدنى حد. بدلاً من ذلك، يمكن استخدام بعض كتل القرص غير المتسلسلة. [ 20 ]

الاستخدام في قواعد البيانات

تستخدم شجرة B جميع الأفكار المذكورة أعلاه. وعلى وجه الخصوص، شجرة B:

  • يحافظ على ترتيب المفاتيح بشكل منظم لتسهيل عملية التصفح التسلسلي.
  • يستخدم فهرسًا هرميًا لتقليل عدد عمليات قراءة القرص
  • يستخدم الكتل الممتلئة جزئيًا لتسريع عمليات الإضافة والحذف.
  • يحافظ على توازن المؤشر باستخدام خوارزمية تكرارية

بالإضافة إلى ذلك، تقلل شجرة B من الهدر من خلال ضمان امتلاء العقد الداخلية بنسبة النصف على الأقل. ويمكن لشجرة B التعامل مع عدد غير محدود من عمليات الإضافة والحذف. [ 20 ]

أفضل وأسوأ الارتفاعات

ليكن h ≥ –1 ارتفاع شجرة B الكلاسيكية (انظر قسم المصطلحات في قسم هياكل البيانات الشجرية  لمعرفة تعريف ارتفاع الشجرة). وليكن n ≥ 0 عدد المدخلات في الشجرة. وليكن m الحد الأقصى لعدد الأبناء الذين يمكن أن يمتلكهم أي عقدة. يمكن أن تحتوي كل عقدة على m − 1 مفتاحًا على الأكثر .

يمكن إثبات (بالاستقراء مثلاً) أن شجرة B ذات ارتفاع h، مع امتلاء جميع عقدها بالكامل، تحتوي على n = m h + 1 – 1 مدخلاً. وبالتالي، فإن أفضل ارتفاع (أي أدنى ارتفاع) لشجرة B هو:

حمأنان=⌈سجلم⁡(ن+1)⌉-1{\displaystyle h_{\mathrm {min} }=\lceil \log _{m}(n+1)\rceil -1}

يتركد{\displaystyle d}ليكن هذا الحد الأدنى لعدد الأبناء الذين يجب أن تمتلكهم عقدة داخلية (غير جذرية). بالنسبة لشجرة B عادية،د=⌈م/2⌉.{\displaystyle d=\left\lceil m/2\right\rceil .}

يقدم كل من Comer (1979) و Cormen et al. (2001) أسوأ حالة ارتفاع (أقصى ارتفاع) لشجرة B على النحو التالي: [ 22 ]

حمأx=⌊سجلد⁡ن+12⌋.{\displaystyle h_{\mathrm {max} }=\left\lfloor \log _{d}{\frac {n+1}{2}}\right\rfloor .}

الخوارزميات

يشبه البحث البحث في الشجرة الثنائية. بدءًا من الجذر، يتم اجتياز الشجرة بشكل متكرر من الأعلى إلى الأسفل. في كل مستوى، يقلص البحث نطاقه إلى مؤشر الفرع (الشجرة الفرعية) الذي يشمل نطاقه قيمة البحث. يُحدد نطاق الشجرة الفرعية بالقيم، أو المفاتيح، الموجودة في عقدة الأصل. تُعرف هذه القيم المحددة أيضًا بقيم الفصل.

يُستخدم البحث الثنائي عادةً (ولكن ليس بالضرورة) داخل العقد للعثور على قيم الفصل وشجرة الأبناء ذات الأهمية.

الإدخال

مثال على إدخال شجرة B مع كل تكرار. تحتوي عقد شجرة B هذه على 3 أبناء على الأكثر (رتبة كنوت 3).

تبدأ جميع عمليات الإضافة من عقدة طرفية. لإضافة عنصر جديد، ابحث في الشجرة للعثور على العقدة الطرفية التي تريد إضافة العنصر الجديد إليها. أضف العنصر الجديد إلى تلك العقدة باتباع الخطوات التالية:

  1. إذا احتوت العقدة على عدد عناصر أقل من الحد الأقصى المسموح به، فهناك مساحة للعنصر الجديد. أضف العنصر الجديد إلى العقدة مع الحفاظ على ترتيب عناصرها.
  2. وإلا، إذا كانت العقدة ممتلئة، فقم بتقسيمها بالتساوي إلى عقدتين، كما يلي:
    1. يتم اختيار وسيط واحد من بين عناصر الورقة والعنصر الجديد الذي يتم إدخاله.
    2. يتم وضع القيم الأقل من الوسيط في العقدة اليسرى الجديدة، ويتم وضع القيم الأكبر من الوسيط في العقدة اليمنى الجديدة، مع اعتبار الوسيط بمثابة قيمة فاصلة.
    3. تُدرج قيمة الفصل في العقدة الأب، مما قد يؤدي إلى تقسيمها، وهكذا. إذا لم يكن للعقدة عقدة أب (أي إذا كانت العقدة هي الجذر)، فأنشئ جذرًا جديدًا فوق هذه العقدة (مما يزيد من ارتفاع الشجرة).

إذا امتد التقسيم حتى الجذر، فإنه يُنشئ جذرًا جديدًا بقيمة فاصلة واحدة وابنين، ولذلك لا ينطبق الحد الأدنى لحجم العقد الداخلية على الجذر. الحد الأقصى لعدد العناصر في كل عقدة هو U - 1. عند تقسيم عقدة، ينتقل عنصر واحد إلى العقدة الأب، ويُضاف عنصر واحد. لذا، يجب أن يكون من الممكن تقسيم الحد الأقصى لعدد العناصر U - 1 إلى عقدتين صحيحتين. إذا كان هذا العدد فرديًا، فإن U = 2L ، وتحتوي إحدى العقدتين الجديدتين على ( U - 2) / 2 = L - 1 عنصرًا، وبالتالي فهي عقدة صحيحة، وتحتوي الأخرى على عنصر إضافي، وبالتالي فهي صحيحة أيضًا. إذا كان U - 1 زوجيًا، فإن U = 2L - 1، لذا يوجد 2L - 2 عنصرًا في العقدة. نصف هذا العدد هو L - 1، وهو الحد الأدنى لعدد العناصر المسموح به في كل عقدة.

تدعم خوارزمية بديلة المرور مرة واحدة على الشجرة من الجذر إلى العقدة التي ستُضاف إليها البيانات، مع تقسيم أي عقد ممتلئة تُصادف في الطريق بشكل استباقي. هذا يمنع الحاجة إلى استدعاء العقد الأبوية إلى الذاكرة، وهو ما قد يكون مكلفًا إذا كانت العقد موجودة على وحدة تخزين ثانوية. مع ذلك، لاستخدام هذه الخوارزمية، يجب أن نكون قادرين على إرسال عنصر واحد إلى العقدة الأبوية وتقسيم العناصر المتبقية (U − 2) إلى عقدتين صحيحتين، دون إضافة عنصر جديد. يتطلب هذا أن تكون U = 2L بدلاً من U = 2L − 1، وهو ما يفسر سبب فرض بعض الكتب الدراسية لهذا الشرط عند تعريف أشجار B.

الحذف

هناك استراتيجيتان شائعتان للحذف من شجرة B.

  1. حدد موقع العنصر واحذفه، ثم أعد هيكلة الشجرة للاحتفاظ بثوابتها، أو
  2. قم بتمرير واحد لأسفل الشجرة، ولكن قبل الدخول (زيارة) عقدة، أعد هيكلة الشجرة بحيث بمجرد مصادفة المفتاح المراد حذفه، يمكن حذفه دون الحاجة إلى أي إعادة هيكلة أخرى.

تستخدم الخوارزمية أدناه الاستراتيجية السابقة.

هناك حالتان خاصتان يجب مراعاتهما عند حذف عنصر ما:

  1. العنصر الموجود في عقدة داخلية هو فاصل لعقدها الفرعية.
  2. قد يؤدي حذف عنصر ما إلى وضع عقدته تحت الحد الأدنى لعدد العناصر والأبناء.

الإجراءات المتبعة في هذه الحالات مذكورة أدناه.

الحذف من عقدة طرفية

  1. ابحث عن القيمة المراد حذفها.
  2. إذا كانت القيمة موجودة في عقدة فرعية، فما عليك سوى حذفها من العقدة.
  3. في حالة حدوث نقص في البيانات، أعد توازن الشجرة كما هو موضح في قسم "إعادة التوازن بعد الحذف" أدناه.

الحذف من عقدة داخلية

يعمل كل عنصر في العقدة الداخلية كقيمة فاصلة بين شجرتين فرعيتين؛ لذا نحتاج إلى إيجاد بديل للفصل. لاحظ أن أكبر عنصر في الشجرة الفرعية اليسرى لا يزال أصغر من الفاصل. وبالمثل، فإن أصغر عنصر في الشجرة الفرعية اليمنى لا يزال أكبر من الفاصل. يقع كلا العنصرين في عقد طرفية، ويمكن لأي منهما أن يكون الفاصل الجديد بين الشجرتين الفرعيتين. الخوارزمية موضحة أدناه:

  1. اختر فاصلًا جديدًا (إما أكبر عنصر في الشجرة الفرعية اليسرى أو أصغر عنصر في الشجرة الفرعية اليمنى)، وقم بإزالته من عقدة الورقة التي يوجد بها، واستبدل العنصر المراد حذفه بالفاصل الجديد.
  2. حذفت الخطوة السابقة عنصرًا (الفاصل الجديد) من عقدة طرفية. إذا كانت هذه العقدة الطرفية الآن ناقصة (أي تحتوي على عدد أقل من العقد المطلوبة)، فأعد توازن الشجرة بدءًا من تلك العقدة الطرفية.

إعادة التوازن بعد الحذف

تبدأ عملية إعادة التوازن من ورقة وتتجه نحو الجذر حتى تتوازن الشجرة. إذا أدى حذف عنصر من عقدة إلى تقليل حجمها عن الحد الأدنى، فيجب إعادة توزيع بعض العناصر لرفع عدد العقد إلى الحد الأدنى. عادةً، تتضمن إعادة التوزيع نقل عنصر من عقدة شقيقة تحتوي على عدد عقد أكبر من الحد الأدنى. تُسمى عملية إعادة التوزيع هذه بالتدوير . إذا لم تتمكن أي عقدة شقيقة من الاحتفاظ بعنصر، فيجب دمج العقدة الناقصة مع عقدة شقيقة. يؤدي الدمج إلى فقدان العقدة الأب لعنصر فاصل، مما قد يجعلها ناقصة وتحتاج إلى إعادة توازن. قد تستمر عملية الدمج وإعادة التوازن حتى الجذر. بما أن الحد الأدنى لعدد العناصر لا ينطبق على الجذر، فإن جعل الجذر هو العقدة الناقصة الوحيدة لا يُشكل مشكلة. خوارزمية إعادة توازن الشجرة هي كما يلي:

  • إذا كان هناك شقيق أيمن للعقدة الناقصة ويحتوي على أكثر من الحد الأدنى لعدد العناصر، فقم بالتدوير إلى اليسار.
    1. انسخ الفاصل من الأصل إلى نهاية العقدة الناقصة (يتحرك الفاصل إلى الأسفل؛ تحتوي العقدة الناقصة الآن على الحد الأدنى من العناصر)
    2. استبدل الفاصل في الأصل بالعنصر الأول من الشقيق الأيمن (يفقد الشقيق الأيمن عقدة واحدة ولكنه لا يزال يحتوي على الحد الأدنى من العناصر على الأقل).
    3. أصبحت الشجرة الآن متوازنة.
  • وإلا، إذا كان الشقيق الأيسر للعقدة الناقصة موجودًا ويحتوي على أكثر من الحد الأدنى لعدد العناصر، فقم بالتدوير إلى اليمين.
    1. انسخ الفاصل من الأصل إلى بداية العقدة الناقصة (يتحرك الفاصل إلى الأسفل؛ تحتوي العقدة الناقصة الآن على الحد الأدنى من العناصر)
    2. استبدل الفاصل في الأصل بالعنصر الأخير من الشقيق الأيسر (يفقد الشقيق الأيسر عقدة واحدة ولكنه لا يزال يحتوي على الحد الأدنى من العناصر على الأقل).
    3. أصبحت الشجرة الآن متوازنة.
  • وإلا، إذا كان لدى كلا الشقيقين المباشرين الحد الأدنى من العناصر فقط، فقم بدمجهما مع شقيق آخر يحيط بهما الفاصل المأخوذ من والدهما.
    1. انسخ الفاصل إلى نهاية العقدة اليسرى (قد تكون العقدة اليسرى هي العقدة الناقصة، أو قد تكون العقدة الشقيقة التي تحتوي على أقل عدد من العناصر).
    2. انقل جميع العناصر من العقدة اليمنى إلى العقدة اليسرى (العقدة اليسرى الآن تحتوي على الحد الأقصى من العناصر، والعقدة اليمنى فارغة).
    3. قم بإزالة الفاصل من العنصر الأب مع ابنه الأيمن الفارغ (يفقد العنصر الأب عنصرًا).
      • إذا كان الأصل هو الجذر ولم يعد يحتوي على أي عناصر، فقم بتحريره واجعل العقدة المدمجة هي الجذر الجديد (يصبح الشجر أقل عمقًا).
      • وإلا، إذا كان العنصر الأصل يحتوي على عدد أقل من العدد المطلوب من العناصر، فأعد موازنة العنصر الأصل [ 23 ]
ملاحظة : تختلف عمليات إعادة التوازن بالنسبة لأشجار B+ (على سبيل المثال، يختلف التدوير لأن الأصل لديه نسخة من المفتاح) وشجرة B * (على سبيل المثال، يتم دمج ثلاثة أشقاء في شقيقين).

الوصول التسلسلي

على الرغم من أن قواعد البيانات التي يتم تحميلها حديثًا تميل إلى امتلاك سلوك تسلسلي جيد، إلا أن الحفاظ على هذا السلوك يصبح أكثر صعوبة مع نمو قاعدة البيانات، مما يؤدي إلى المزيد من عمليات الإدخال/الإخراج العشوائية وتحديات الأداء. [ 24 ]

الإنشاءات الأولية

من الحالات الخاصة الشائعة إضافة كمية كبيرة من البيانات المصنفة مسبقًا إلى شجرة B فارغة في البداية. مع أنه من الممكن ببساطة إجراء سلسلة من عمليات الإدخال المتتالية، إلا أن إدخال البيانات المصنفة ينتج عنه شجرة تتكون بالكامل تقريبًا من عقد نصف ممتلئة. بدلًا من ذلك، يمكن استخدام خوارزمية "تحميل مجمع" خاصة لإنتاج شجرة أكثر كفاءة ذات عامل تفرع أعلى.

عند فرز المدخلات، تكون جميع عمليات الإضافة على الحافة اليمنى للشجرة، وبالتحديد عند تقسيم أي عقدة، نضمن عدم حدوث أي عمليات إضافة أخرى في النصف الأيسر. عند التحميل المجمع، نستغل هذه الخاصية، وبدلاً من تقسيم العقد الممتلئة بالتساوي، نقسمها بشكل غير متساوٍ قدر الإمكان: نترك العقدة اليسرى ممتلئة تمامًا وننشئ عقدة يمنى بدون مفاتيح وعقدة فرعية واحدة (مخالفةً لقواعد شجرة B المعتادة).

في نهاية عملية التحميل المجمع، تتكون الشجرة بالكامل تقريبًا من عقد ممتلئة تمامًا؛ العقدة الوحيدة التي قد تكون أقل امتلاءً في أقصى اليمين من كل مستوى هي العقدة الموجودة في أقصى اليمين. ولأن هذه العقد قد تكون أيضًا أقل امتلاءً من النصف ، ولإعادة تطبيق قواعد شجرة B العادية، يتم دمج هذه العقد مع أشقائها اليسرى (الممتلئة مضمونًا) وتقسيم المفاتيح لإنتاج عقدتين ممتلئتين على الأقل بنسبة النصف. العقدة الوحيدة التي لا يوجد لها شقيق أيسر ممتلئ هي الجذر، والذي يُسمح له بأن يكون أقل امتلاءً من النصف.

في أنظمة الملفات

بالإضافة إلى استخدامها في قواعد البيانات، تُستخدم شجرة B (أو متغيراتها  ) أيضًا في أنظمة الملفات للسماح بالوصول العشوائي السريع إلى أي كتلة في ملف معين. تكمن المشكلة الأساسية في تحويل كتلة الملفأنا{\displaystyle i}تحويل العنوان إلى عنوان كتلة القرص.

تطلبت بعض أنظمة التشغيل القديمة، وبعض الأنظمة المتخصصة للغاية، من التطبيق تحديد الحجم الأقصى للملف عند إنشائه. ويمكن بعد ذلك تخصيص الملف على شكل كتل متجاورة على القرص. في هذه الحالة، يتم تحويل عنوان كتلة الملف.أنا{\displaystyle i}يقوم نظام التشغيل ببساطة بإضافة عنوان كتلة الملف إلى عنوان كتلة القرص.أنا{\displaystyle i}إلى عنوان أول كتلة قرصية تُشكّل الملف. المخطط بسيط، لكن لا يمكن أن يتجاوز حجم الملف حجمه عند إنشائه.

تسمح جميع أنظمة التشغيل الحديثة والشائعة بنمو حجم الملف. وقد لا تكون كتل القرص الناتجة متجاورة، لذا فإن ربط الكتل المنطقية بالكتل الفيزيائية أكثر تعقيدًا.

على سبيل المثال، استخدم نظام MS-DOS جدول تخصيص ملفات بسيطًا (FAT). يحتوي جدول FAT على مدخل لكل كتلة قرص، [ ملاحظة 1 ] ويحدد هذا المدخل ما إذا كانت كتلته مستخدمة بواسطة ملف، وإذا كان الأمر كذلك، فما هي الكتلة التالية (إن وجدت) لنفس الملف. لذا، يتم تمثيل تخصيص كل ملف كقائمة مرتبطة في الجدول. للعثور على عنوان القرص لكتلة الملفأنا{\displaystyle i}يجب على نظام التشغيل (أو أداة القرص) تتبع قائمة الملفات المرتبطة في جدول تخصيص الملفات (FAT) بالتسلسل. والأسوأ من ذلك، أنه للعثور على كتلة قرص فارغة، يجب عليه مسح جدول تخصيص الملفات بالتسلسل. بالنسبة لنظام MS-DOS، لم يكن ذلك عائقًا كبيرًا نظرًا لصغر حجم الأقراص والملفات، وقلة عدد إدخالات جدول تخصيص الملفات، وقصر سلاسل الملفات نسبيًا. في نظام الملفات FAT12 (المستخدم في الأقراص المرنة والأقراص الصلبة القديمة)، لم يتجاوز عدد الإدخالات 4080 إدخالًا [ ملاحظة 2 ] ، وكان جدول تخصيص الملفات عادةً موجودًا في الذاكرة. مع ازدياد سعة الأقراص، بدأت بنية جدول تخصيص الملفات تواجه تحديات. على قرص كبير يستخدم جدول تخصيص الملفات، قد يكون من الضروري إجراء عمليات قراءة من القرص لمعرفة موقع كتلة الملف المراد قراءتها أو كتابتها.

استخدم نظام TOPS-20 شجرة من المستوى 0 إلى 2 تشبه شجرة B. تتكون كتلة القرص من 512 كلمة، كل منها 36 بت. إذا كان حجم الملف 512 كلمة (2^ 9 )، فإن دليل الملف يشير إلى تلك الكتلة الفعلية. أما إذا كان حجم الملف 2^ 18 كلمة، فإن الدليل يشير إلى فهرس مساعد؛ وتكون كلمات هذا الفهرس الـ 512 إما فارغة (أي أن الكتلة غير مخصصة) أو تشير إلى العنوان الفعلي للكتلة. وإذا كان حجم الملف 2^ 27 كلمة، فإن الدليل يشير إلى كتلة تحتوي على فهرس مساعد مزدوج؛ ويكون كل مدخل إما فارغًا أو يشير إلى فهرس مساعد مزدوج. بالتالي، يمكن تحديد موقع كتلة القرص الفعلية لملف بحجم 2^ 27 كلمة من خلال قراءتين للقرص، ثم قراءتها في القراءة الثالثة.

تستخدم أنظمة الملفات HFS+ و APFS الخاصة بشركة Apple ، و NTFS الخاصة بشركة Microsoft ، [ 25 ] و AIX (jfs2) وبعض أنظمة ملفات Linux ، مثل Bcachefs و Btrfs و ext4 ، أشجار B.

تُستخدم أشجار B * في أنظمة الملفات HFS و Reiser4 .

يستخدم نظام ملفات HAMMER الخاص بنظام DragonFly BSD شجرة B+ معدلة. [ 26 ]

أداء

تنمو شجرة B بشكل أبطأ مع ازدياد حجم البيانات، مقارنةً بخطية القائمة المتصلة. وبالمقارنة مع قائمة التخطي ، فإن كلا البنيتين لهما نفس الأداء، لكن شجرة B تتوسع بشكل أفضل مع ازدياد قيمة n . أما شجرة T ، لأنظمة قواعد البيانات في الذاكرة الرئيسية ، فهي مشابهة ولكنها أكثر إحكامًا.

الاختلافات

الوصول المتزامن

أظهر ليمان وياو [ 27 ] أنه يمكن تجنب جميع عمليات قفل القراءة (وبالتالي تحسين الوصول المتزامن بشكل كبير) عن طريق ربط كتل الشجرة في كل مستوى بمؤشر "التالي". ينتج عن ذلك بنية شجرية تنحدر فيها عمليات الإضافة والبحث من الجذر إلى الورقة. ولا تُطلب عمليات قفل الكتابة إلا عند تعديل كتلة الشجرة. وهذا يزيد من تزامن الوصول من قِبل عدة مستخدمين، وهو اعتبار مهم لقواعد البيانات و/أو طرق تخزين ISAM الأخرى القائمة على شجرة B. أما التكلفة المرتبطة بهذا التحسين فهي عدم إمكانية إزالة الصفحات الفارغة من شجرة B أثناء العمليات العادية. (توجد استراتيجيات لتنفيذ دمج العقد [ 28 ] [ 29 ] ).

يبدو أن براءة الاختراع الأمريكية رقم 5283894، الممنوحة عام 1994، تُظهر طريقةً لاستخدام "أسلوب الوصول الفوقي" [ 30 ] للسماح بالوصول المتزامن إلى شجرة B+ وتعديلها دون استخدام الأقفال. تعتمد هذه التقنية على الوصول إلى الشجرة "تصاعديًا" لكلٍ من عمليات البحث والتحديث، وذلك باستخدام فهارس إضافية في الذاكرة تُشير إلى الكتل في كل مستوى من ذاكرة التخزين المؤقت للكتل. لا حاجة لإعادة تنظيم البيانات عند الحذف، ولا توجد مؤشرات "التالي" في كل كتلة كما في دراسة ليمان وياو.

الخوارزميات المتوازية

بما أن أشجار B متشابهة في بنيتها مع أشجار الأحمر والأسود ، فإنه يمكن تطبيق الخوارزميات المتوازية لأشجار الأحمر والأسود على أشجار B أيضًا.

شجرة القيقب

شجرة القيقب هي شجرة من نوع B تم تطويرها للاستخدام في نواة لينكس لتقليل التنازع على الأقفال في إدارة الذاكرة الافتراضية. [ 31 ] [ 32 ] [ 33 ]

شجرة (أ، ب)

تُعد أشجار (أ، ب) تعميمًا لأشجار ب. تتطلب أشجار ب أن تحتوي كل عقدة داخلية على حد أدنى من⌊ك/2⌋+1{\displaystyle \lfloor K/2\rfloor +1}الأطفال وبحد أقصىك{\displaystyle K}الأطفال، لقيمة محددة مسبقًا منك{\displaystyle K}على النقيض من ذلك، تسمح شجرة (أ، ب) بتحديد الحد الأدنى لعدد الأبناء لعقدة داخلية بشكل منخفض تعسفي. في شجرة (أ، ب)، يكون لكل عقدة داخلية ما بين أ و ب من الأبناء، وذلك لقيم محددة مسبقًا لـ أ و ب .

انظر أيضاً

ملحوظات

  1. ↑ بالنسبة لنظام FAT، ما يُسمى هنا "كتلة القرص" هو ما يُطلق عليه في وثائق FAT اسم "المجموعة"، وهي عبارة عن مجموعة ثابتة الحجم من قطاع قرص فعلي كامل أو أكثر متجاور . ولأغراض هذا النقاش، لا يوجد فرق جوهري بين المجموعة والقطاع الفعلي.
  2. ↑ تم حجز اثنين من هذه الأرقام لأغراض خاصة، لذلك فإن 4078 فقط يمكن أن تمثل فعليًا كتل القرص (المجموعات).

مراجع

  1. 1 2 باير، ر.؛ مكريت، إ. (يوليو 1970). "تنظيم وصيانة الفهارس المرتبة الكبيرة" (ملف PDF) . وقائع ورشة عمل ACM SIGFIDET (الآن SIGMOD) لعام 1970 حول وصف البيانات والوصول إليها والتحكم فيها - SIGFIDET '70 . مختبرات بوينغ للأبحاث العلمية. ص  107. doi : 10.1145/1734663.1734671 . S2CID 26930249 . 
  2. 1 2 3 4 كومر 1979 .
  3. ↑ "BTreeMap في std::collections - Rust" . doc.rust-lang.org .
  4. ↑ "أبسيل / حاويات أبسيل" . abseil.io .
  5. 1 2 3 باير وماكريت 1972 .
  6. ↑ كومر 1979 ، ص 123 الحاشية 1.
  7. 1 2 وينر، بيتر ج. (30 أغسطس 2013). "4- إدوارد م مكريت" – عبر فيميو.
  8. ↑ "مركز ستانفورد للتطوير المهني" . scpd.stanford.edu . مؤرشف من الأصل بتاريخ 2014-06-04 . تم الاطلاع عليه بتاريخ 2011-01-16 .
  9. 1 2 كنوت 1998 ، ص 483.
  10. ↑ Folk & Zoellick 1992 ، ص 362.
  11. 1 2 Folk & Zoellick 1992 ، ص 363.
  12. تجنّب باير وماكريت (1972) هذه المسألة بقولهما إن عنصر الفهرس هو زوج (متجاور فعليًا) من ( x ، a )، حيث x هو المفتاح، و a هي معلومة مرتبطة به. قد تكون هذه المعلومة مؤشرًا إلى سجل أو سجلات في عملية وصول عشوائي، لكن ماهيتها لم تكن مهمة. يذكر باير وماكريت (1972) : "بالنسبة لهذه الورقة، لا تُعدّ المعلومة المرتبطة ذات أهمية إضافية". 
  13. ↑ Folk & Zoellick 1992 ، ص 379.
  14. ^ نافاث، رامز المصري، شمكانت ب. (2010). أساسيات أنظمة قواعد البيانات ( الطبعة السادسة). أبر سادل ريفر، نيوجيرسي: تعليم بيرسون. ص 652 – 660. ISBN   9780136086208.{{cite book}}: صيانة CS1: أسماء متعددة: قائمة المؤلفين ( رابط )
  15. ↑ كنوت 1998 ، ص 488.
  16. 1 2 3 4 5 6 توماسيفيتش، ميلو (2008). الخوارزميات وهياكل البيانات . بلغراد، صربيا: أكاديميسكا ميساو. ص 274 – 275. ISBN  978-86-7466-328-8.
  17. ↑ ريجين إيه إم، شيرشاكوف إس إيه (10 سبتمبر 2019). "امتداد SQLite لنظام إدارة قواعد البيانات العلائقية لفهرسة البيانات باستخدام تعديلات شجرة B" . وقائع معهد برمجة الأنظمة التابع لأكاديمية العلوم الروسية . 31 (3). معهد برمجة الأنظمة التابع لأكاديمية العلوم الروسية (ISP RAS): 203-216 . doi : 10.15514/ispras-2019-31(3)-16 . S2CID 203144646. تاريخ الاسترجاع: 29 أغسطس 2021 . 
  18. ↑ "أشجار الفئة ب المعدودة" . www.chiark.greenend.org.uk . تاريخ الاسترجاع: 27-12-2024 .
  19. ↑ دليل المنتج: Barracuda ES.2 Serial ATA، الإصدار F، المنشور رقم 100468393 (PDF) . شركة Seagate Technology LLC. 2008. صفحة 6. 
  20. 1 2 3 كليبمان، مارتن (2017). تصميم التطبيقات كثيفة البيانات . سيباستوبول، كاليفورنيا : أورايلي ميديا . ص 80. ISBN  978-1-449-37332-0.
  21. ↑ جان جانينك. "تنفيذ الحذف في أشجار B+". القسم "4 الحذف الكسول" .
  22. ^ كومر 1979 ، ص. 127 ؛ كورمين وآخرون. 2001 ، ص 439-440  
  23. ↑ "الحذف في شجرة B" (ملف PDF) . cs.rhodes.edu . مؤرشف (ملف PDF) من الأصل بتاريخ 9 أكتوبر 2022. تم الاطلاع عليه بتاريخ 24 مايو 2022 .
  24. ↑ "أشجار B غير الواعية بالذاكرة المؤقتة" . جامعة ولاية نيويورك (SUNY) في ستوني بروك . تم الاسترجاع في 17 يناير 2011 .
  25. ↑ مارك روسينوفيتش (30 يونيو 2006). "نظرة داخلية على نظام الملفات NTFS في ويندوز 2000، الجزء الأول" . شبكة مطوري مايكروسوفت . مؤرشف من الأصل في 13 أبريل 2008. تم الاطلاع عليه بتاريخ 18 أبريل 2008 .
  26. ↑ ماثيو ديلون (21-06-2008). "نظام ملفات هامر" (ملف PDF) . مؤرشف (ملف PDF) من الأصل بتاريخ 09-10-2022.
  27. ↑ ليمان، فيليب ل.؛ ياو، س. بينغ (1981). "التأمين الفعال للعمليات المتزامنة على أشجار B" . معاملات ACM لأنظمة قواعد البيانات . 6 (4): 650-670 . doi : 10.1145/319628.319663 . S2CID 10756181 . 
  28. ↑ وانغ، بول (1 فبراير 1991). "تحليل معمق لخوارزميات شجرة B المتزامنة" (ملف PDF) . dtic.mil . مؤرشف من الأصل (ملف PDF) في 4 يونيو 2011. تم الاطلاع عليه في 21 أكتوبر 2022 .
  29. ↑ "تنزيلات - high-concurrency-btree - كود شجرة B عالية التزامن بلغة C - استضافة مشاريع GitHub" . GitHub . تم الاسترجاع في 27 يناير 2014 .
  30. ↑ "طريقة الوصول إلى بيانات تعريف فهرس شجرة B المتزامنة بدون قفل للعقد المخزنة مؤقتًا" .
  31. ↑ "تقديم أشجار القيقب [ LWN.net ] " . lwn.net .
  32. ↑ "شجرة القيقب - وثائق نواة لينكس" . docs.kernel.org .
  33. ↑ "تقديم شجرة القيقب [ LWN.net ] " . lwn.net .

المجال العام تتضمن هذه المقالة موادًا متاحة للعموم من بول إي. بلاك. "شجرة (أ، ب)" . قاموس الخوارزميات وهياكل البيانات . المعهد الوطني للمعايير والتكنولوجيا .

مصادر

أوراق أصلية

  • باير، رودولف ؛ مكريت، إي. (يوليو 1970)، تنظيم وصيانة المؤشرات المرتبة الكبيرة ، المجلد.  تقرير العلوم الرياضية والمعلوماتية رقم 20، مختبرات بوينغ للأبحاث العلمية.
  • باير، رودولف (1971). "أشجار B الثنائية للذاكرة الافتراضية". وقائع ورشة عمل ACM-SIGFIDET لعام 1971 حول وصف البيانات والوصول إليها والتحكم فيها . سان دييغو، كاليفورنيا..

التحميل بالجملة