طرق الفهرسة والوصول

الفهارس وطرق الوصول هي هياكل البيانات المساعدة — وبشكل رئيسي أشجار B+ وفهارس التجزئة — التي تتيح لقاعدة البيانات تحديد موقع الصفوف المتطابقة دون مسح جدول بأكمله، مما يوفر مسارات الوصول السريعة التي يعتمد عليها المحسّن.

Definition

الفهرس هو بنية بيانات مساعدة على سمة واحدة أو أكثر من سمات العلاقة التي تربط قيم المفاتيح بمواقع الصفوف المتطابقة، مما يتيح الاسترجاع في وقت أقل خطيًا من حجم الجدول؛ طريقة الوصول هي الآلية التي يستخدمها الاستعلام لقراءة البيانات، مثل المسح الكامل أو مسح الفهرس.

Scope

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

Core questions

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

Key concepts

• فهرس شجرة B+
• فهرس التجزئة
• فهرس مجمع مقابل غير مجمع
• الفهارس الأساسية والثانوية
• فهارس كثيفة ومتفرقة
• البحث عن النطاق والمساواة
• التجزئة القابلة للتوسيع والخطية
• تكلفة صيانة الفهرس

Key theories

فهارس شجرة B+

شجرة B+ هي شجرة بحث متوازنة وعالية التفرع تخزن المفاتيح بترتيب فرز مع جميع مراجع البيانات في الأوراق؛ وهي تدعم استعلامات المساواة والنطاق والمسح المرتب في إدخال/إخراج لوغاريتمي وتبقى متوازنة تحت عمليات الإدراج والحذف.

الفهارس المجمعة مقابل غير المجمعة

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

فهارس التجزئة

تربط الفهارس القائمة على التجزئة المفاتيح بالدلاء لعمليات البحث عن المساواة في وقت ثابت متوقع ولكنها لا تدعم استعلامات النطاق؛ وتسمح المخططات الديناميكية مثل التجزئة القابلة للتوسيع والخطية لها بالنمو بسلاسة مع البيانات.

Clinical relevance

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

History

قدم باير ومكرايت شجرة B في عام 1972 للحفاظ على فهارس مرتبة كبيرة على القرص؛ وأصبح متغير شجرة B+، الذي يحتفظ بجميع البيانات في الأوراق، فهرس قاعدة البيانات القياسي، كما تم مسحه في كتاب كومر عام 1979 'شجرة B المنتشرة'. تطورت طرق الوصول القائمة على التجزئة ومخططات التجزئة الديناميكية بالتوازي، وتظل كلتا العائلتين أساسيتين لكل محرك علائقي.

Key figures

• Rudolf Bayer
• Edward McCreight
• Douglas Comer

Seminal works

• bayer1972
• comer1979
• ramakrishnan2003

Frequently asked questions

لماذا تستخدم أشجار B+ بدلاً من أشجار البحث الثنائية في قواعد البيانات؟

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

متى يجب أن أستخدم فهرس تجزئة بدلاً من شجرة B+؟

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