العقد الورقية للفهرس
الغرض الأساسي من الفهرس هو توفير تمثيل مرتب للبيانات المفهرسة. غير أنه لا يمكن تخزين البيانات تتابعياً، لأن عبارة insert ستحتاج إلى نقل المدخلات التالية لإفساح مكان للمدخل الجديد، ونقل كميات كبيرة من البيانات مستهلك للوقت جداً، ما يجعل عبارة insert بطيئة جداً. والحل لهذه المشكلة هو إنشاء ترتيب منطقي مستقل عن الترتيب الفيزيائي في الذاكرة.
إن أعجبك هذا الموضوع، قد يعجبك أيضاً…
… أن تشترك في القوائم البريدية، وتحصل على ملصقات مجانية، وتشتري كتابي، أو تنضم إلى دورة تدريبية.
يُنشأ الترتيب المنطقي عبر قائمة مترابطة مزدوجة (doubly linked list). فلكل عقدة رابطان إلى مدخلين مجاورين، أشبه بسلسلة. وتُدرَج العقد الجديدة بين عقدتين قائمتين بتحديث روابطهما لتشير إلى العقدة الجديدة، ولا يهم الموقع الفيزيائي للعقدة الجديدة لأن القائمة المترابطة المزدوجة تحافظ على الترتيب المنطقي.
سُمّيت بنية البيانات قائمة مترابطة مزدوجة لأن كل عقدة تشير إلى العقدة السابقة والتالية. وهي تمكّن قاعدة البيانات من قراءة الفهرس إلى الأمام أو إلى الخلف حسب الحاجة، ومن ثم يمكن إدراج مدخلات جديدة دون نقل كميات كبيرة من البيانات؛ فكل ما يلزم تغيير بعض المؤشرات.
وتُستخدم القوائم المترابطة المزدوجة أيضاً للمجموعات (الحاويات) في كثير من لغات البرمجة.
| لغة البرمجة | الاسم |
|---|---|
| Java | java.util.LinkedList |
| .NET Framework | System.Collections.Generic.LinkedList |
| C++ | std::list |
تستخدم قواعد البيانات القوائم المترابطة المزدوجة لربط ما يسمى العقد الورقية للفهرس. وتُخزَّن كل عقدة ورقية في كتلة قاعدة بيانات أو صفحة، وهي أصغر وحدة تخزين في قاعدة البيانات. وجميع كتل الفهرس بالحجم نفسه — عادة بضعة كيلوبايتات. وتستغل قاعدة البيانات المساحة في كل كتلة إلى أقصى حد ممكن وتخزّن أكبر عدد ممكن من مدخلات الفهرس في كل كتلة. ويعني ذلك أن ترتيب الفهرس محفوظ على مستويين مختلفين: مدخلات الفهرس داخل كل عقدة ورقية، والعقد الورقية بعضها إزاء بعض عبر قائمة مترابطة مزدوجة.
الشكل 1.1 العقد الورقية للفهرس وبيانات الجدول المقابلة
يوضح الشكل 1.1 العقد الورقية للفهرس وصلتها ببيانات الجدول. يتألف كل مدخل فهرس من الأعمدة المفهرسة (المفتاح، العمود 2) ويشير إلى صف الجدول المقابل (عبر ROWID أو RID). وخلافاً للفهرس، تُخزَّن بيانات الجدول في بنية كومة (heap) وغير مرتبة إطلاقاً؛ فلا توجد علاقة بين الصفوف المخزنة في كتلة الجدول نفسها، ولا أي اتصال بين الكتل.