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

فهرس الصور النقطية هو نوع خاص من فهارس قواعد البيانات التي تستخدم الصور النقطية .

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

يرى بعض الباحثين أن فهارس الخرائط النقطية مفيدة أيضاً للبيانات ذات العدد المتوسط ​​أو حتى العالي من القيم الفريدة (مثل البيانات ذات القيم الفريدة) والتي يتم الوصول إليها بطريقة للقراءة فقط، حيث تصل الاستعلامات إلى أعمدة متعددة مفهرسة بالخرائط النقطية باستخدام عوامل التشغيل AND أو OR أو XOR بشكل مكثف. ^{[ 1 ]}

تُعد فهارس Bitmap مفيدة أيضًا في تطبيقات تخزين البيانات لربط جدول حقائق كبير بجداول أبعاد أصغر مثل تلك المرتبة في مخطط النجمة .

استكمالاً لمثال الوصول إلى الإنترنت، يمكن النظر إلى فهرس الخريطة النقطية منطقياً على النحو التالي:

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

ملاحظة: تمت مراجعة العديد من المراجع المذكورة هنا في ( جون وو (2007) ). ^{[ 2 ]} بالنسبة لأولئك الذين قد يكونون مهتمين بتجربة بعض الأفكار المذكورة هنا، فإن العديد منها مُطبق في برامج مفتوحة المصدر مثل FastBit، ^{[ 3 ]} ومكتبة Lemur Bitmap Index C++ ، ^{[ 4 ]} ومكتبة Roaring Bitmap Java، ^{[ 5 ]} ونظام Apache Hive Data Warehouse.

لأسباب تاريخية، تم تطوير ضغط الصور النقطية وضغط القوائم المعكوسة كخطوط بحث منفصلة، ​​ولم يتم الاعتراف بهما كحل لنفس المشكلة بشكل أساسي إلا لاحقًا. ^{[ 6 ]}

يمكن للبرامج ضغط كل صورة نقطية في فهرس الصور النقطية لتوفير المساحة. وقد أُجريت دراسات عديدة حول هذا الموضوع. ^{[ 7 ] [ 8 ]} مع وجود استثناءات مثل صور Roaring النقطية، ^{[ 9 ]} تستخدم خوارزميات ضغط الصور النقطية عادةً ترميز طول التشغيل ، مثل ترميز الصورة النقطية المحاذي للبايت، ^{[ 10 ]} وترميز الصورة الهجين المحاذي للكلمات، ^{[ 11 ]} وضغط الصورة الهجينة المحاذية للكلمات المقسمة (PWAH)، ^{[ 12 ]} وضغط الصورة الهجينة المحاذية للكلمات لقائمة المواضع، ^{[ 13 ]} وضغط الفهرس التكيفي (COMPAX)، ^{[ 14 ]} وضغط الصورة الهجينة المحاذية للكلمات المحسّنة (EWAH)، ^{[ 15 ]} وضغط مجموعة الأعداد الصحيحة المركبة 'N' (CONCISE). ^{[ 16 ] [ 17 ]} تتطلب طرق الضغط هذه جهدًا ضئيلاً جدًا للضغط وفك الضغط. والأهم من ذلك، أن الصور النقطية المضغوطة باستخدام BBC وWAH وCOMPAX وPLWAH وEWAH وCONCISE يمكنها المشاركة مباشرةً في عمليات البت دون الحاجة إلى فك الضغط. وهذا يمنحها مزايا كبيرة مقارنةً بتقنيات الضغط العامة مثل LZ77 . يُستخدم ضغط BBC ومشتقاته في نظام إدارة قواعد بيانات تجاري . يتميز BBC بفعاليته في تقليل أحجام الفهارس والحفاظ على أداء الاستعلامات . يقوم BBC بتشفير الصور النقطية بالبايتات ، بينما يقوم WAH بتشفيرها بالكلمات، مما يجعله أكثر توافقًا مع وحدات المعالجة المركزية الحالية . "في كل من البيانات الاصطناعية وبيانات التطبيقات الحقيقية، تستخدم مخططات محاذاة الكلمات الجديدة مساحة أكبر بنسبة 50% فقط، ولكنها تُجري العمليات المنطقية على البيانات المضغوطة أسرع بـ 12 مرة من BBC." ^{[ 18 ]} أُفيد أن صور PLWAH النقطية تشغل 50% من مساحة التخزين التي تستهلكها صور WAH النقطية، وتوفر أداءً أسرع بنسبة تصل إلى 20% في العمليات المنطقية . ^{[ 13 ]} يمكن تطبيق اعتبارات مماثلة على CONCISE ^{[ 17 ]} وEnhanced Word-Aligned Hybrid. ^{[ 15 ]}

يعتمد أداء مخططات مثل BBC وWAH وPLWAH وEWAH وCOMPAX وCONCISE على ترتيب الصفوف. يمكن لفرز معجمي بسيط أن يقلل حجم الفهرس بمقدار 9 أضعاف، مما يجعل الفهارس أسرع بعدة مرات. ^{[ 19 ]} كلما كبر حجم الجدول، زادت أهمية فرز الصفوف. كما تم اقتراح تقنيات إعادة الترتيب لتحقيق نفس نتائج الفرز عند فهرسة البيانات المتدفقة. ^{[ 14 ]}

تستخدم فهارس الخرائط النقطية الأساسية خريطة نقطية واحدة لكل قيمة مميزة. ويمكن تقليل عدد الخرائط النقطية المستخدمة باستخدام طريقة ترميز مختلفة . ^{[ 20 ] [ 21 ]} على سبيل المثال، يمكن ترميز C قيمة مميزة باستخدام log(C) من الخرائط النقطية مع الترميز الثنائي . ^{[ 22 ]}

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

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

بالنسبة للأعمدة ذات عدد القيم الكبير، يُفيد تجميع القيم في فئات، بحيث تغطي كل فئة عدة قيم، ثم إنشاء خرائط بت لتمثيل القيم في كل فئة. يُقلل هذا الأسلوب من عدد خرائط البت المستخدمة بغض النظر عن طريقة التشفير. ^{[ 23 ]} مع ذلك، لا تستطيع الفهارس المُجمّعة الإجابة إلا على بعض الاستعلامات دون فحص البيانات الأساسية. على سبيل المثال، إذا غطت فئة ما النطاق من 0.1 إلى 0.2، فعندما يطلب المستخدم جميع القيم الأقل من 0.15، تُعتبر جميع الصفوف التي تقع ضمن هذه الفئة نتائج محتملة، ويجب فحصها للتأكد من أنها بالفعل أقل من 0.15. تُعرف عملية فحص البيانات الأساسية بفحص المرشحين. في معظم الحالات، يكون الوقت المُستغرق في فحص المرشحين أطول بكثير من الوقت اللازم للعمل مع فهرس خريطة البت. لذلك، تُظهر الفهارس المُجمّعة أداءً غير منتظم. فقد تكون سريعة جدًا لبعض الاستعلامات، ولكنها أبطأ بكثير إذا لم يُطابق الاستعلام فئةً ما تمامًا.

طُرح مفهوم فهرس الخرائط النقطية لأول مرة من قِبل البروفيسور إسرائيل سبيغلر ورافي مايان في بحثهما "اعتبارات التخزين والاسترجاع لقواعد البيانات الثنائية"، الذي نُشر عام 1985. ^{[ 24 ]} وكان أول منتج تجاري لقواعد البيانات يُطبّق فهرس الخرائط النقطية هو طراز 204 من شركة كمبيوتر كوربوريشن أوف أمريكا . وقد نشر باتريك أونيل ورقة بحثية حول هذا التطبيق عام 1987. ^{[ 25 ]} يُعد هذا التطبيق مزيجًا بين فهرس الخرائط النقطية الأساسي (بدون ضغط) وقائمة مُعرّفات الصفوف (RID). وبشكل عام، يُنظّم الفهرس على شكل شجرة B+ . عندما يكون عدد عناصر العمود منخفضًا، تحتوي كل عقدة طرفية في شجرة B على قائمة طويلة من مُعرّفات الصفوف. في هذه الحالة، يتطلب تمثيل قوائم مُعرّفات الصفوف كخرائط نقطية مساحة أقل. وبما أن كل خريطة نقطية تُمثّل قيمة مُختلفة، فهذا هو فهرس الخرائط النقطية الأساسي. مع ازدياد عدد عناصر العمود، تصبح كل خريطة بتية متفرقة، وقد يتطلب تخزينها مساحة تخزين أكبر من تخزين المحتوى نفسه في قوائم RID. في هذه الحالة، يتم التحول إلى استخدام قوائم RID، مما يجعلها فهرسًا من نوع B+tree . ^{[ 26 ] [ 27 ]}

من أهم مزايا استخدام فهارس الخرائط النقطية أن النتائج الوسيطة الناتجة عنها هي أيضاً خرائط نقطية، ويمكن إعادة استخدامها بكفاءة في عمليات لاحقة للإجابة على استعلامات أكثر تعقيداً. تدعم العديد من لغات البرمجة هذا النوع من الفهارس كبنية بيانات مصفوفة بتية . على سبيل المثال، تحتوي لغة جافا على BitSetالفئة BitArray، بينما تحتوي لغة .NET على الفئة BitArray . ^{[ 28 ]}

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

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

${\displaystyle \mathbf {C} _{n}^{\left[{\frac {n}{2}}\right]}\equiv {\frac {n!}{\left(n-\left[{\frac {n}{2}}\right]\right)!\left[{\frac {n}{2}}\right]!}}}$[ ^{29 ] [ 30 ]​}

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

يمكن لتطبيق استراتيجية الوصول هذه على فهارس شجرة B دمج استعلامات النطاق على أعمدة متعددة. في هذه الطريقة، يتم إنشاء خريطة بت مؤقتة في الذاكرة، حيث يُمثل كل صف في الجدول بتًا واحدًا (وبالتالي، يمكن لـ 1 ميجابايت تخزين أكثر من 8 ملايين مدخل). بعد ذلك، تُدمج نتائج كل فهرس في خريطة البت باستخدام عمليات بتية . بعد تقييم جميع الشروط، تحتوي خريطة البت على القيمة "1" للصفوف التي تطابق التعبير. أخيرًا، يتم اجتياز خريطة البت واسترجاع الصفوف المطابقة. بالإضافة إلى دمج الفهارس بكفاءة، يُحسّن هذا أيضًا موضعية الوصول إلى الجدول، لأن جميع الصفوف تُجلب بالتسلسل من الجدول الرئيسي. ^{[ 31 ]} تُحذف خريطة البت الداخلية بعد الاستعلام. إذا كان عدد الصفوف في الجدول كبيرًا جدًا بحيث لا يمكن استخدام بت واحد لكل صف، يتم إنشاء خريطة بت "فاقدة" بدلاً من ذلك، حيث يُمثل كل صفحة قرص بتًا واحدًا. في هذه الحالة، تُستخدم خريطة البت فقط لتحديد الصفحات المراد جلبها؛ ثم تُطبق معايير التصفية على جميع الصفوف في الصفحات المطابقة. 

ملحوظات

فهرس

• أوكونيل، س. (2005). "ملاحظات دورة قواعد البيانات المتقدمة". ساوثهامبتون : جامعة ساوثهامبتون .{{cite journal}}يتطلب الاستشهاد بالمجلة ( مساعدة )|journal=
• أونيل، ب.؛ أونيل، إ. (2001). "مبادئ قواعد البيانات والبرمجة والأداء". سان فرانسيسكو : دار نشر مورغان كوفمان .{{cite journal}}يتطلب الاستشهاد بالمجلة ( مساعدة )|journal=
• زاكر، م.؛ فون-أمنوايسوك، س.؛ هاو، س.س. (2008). "تصميم مناسب لأنظمة مستودعات البيانات الكبيرة: فهرس الخرائط النقطية مقابل فهرس شجرة B" (ملف PDF) . المجلة الدولية للحاسبات والاتصالات . 2 (2) . تاريخ الاسترجاع: 7 يناير 2010 .