جوهر

الموسوعة الحرة

في مجال الحوسبة، تُعدّ GiST ، أو شجرة البحث المعممة، بنية بيانات وواجهة برمجة تطبيقات (API) تُستخدم لبناء أنواع مختلفة من أشجار البحث على القرص . تُعتبر GiST تعميمًا لشجرة B+ ، حيث توفر بنية تحتية متزامنة وقابلة للاسترداد لشجرة بحث متوازنة الارتفاع دون افتراض أي شيء عن نوع البيانات المخزنة أو الاستعلامات المُنفذة. يُمكن استخدام GiST لتنفيذ مجموعة من الفهارس المعروفة بسهولة، بما في ذلك أشجار B+ ، وأشجار R ، وأشجار hB ، وأشجار RD ، وغيرها الكثير؛ كما تُتيح تطوير فهارس مُخصصة لأنواع البيانات الجديدة بسهولة. لا يُمكن استخدامها مباشرةً لتنفيذ أشجار غير متوازنة الارتفاع مثل الأشجار الرباعية أو أشجار البادئات (الأشجار)، مع أنها، مثل أشجار البادئات، تدعم الضغط، بما في ذلك الضغط مع فقدان البيانات . يُمكن استخدام GiST مع أي نوع بيانات يُمكن ترتيبه بشكل طبيعي في تسلسل هرمي من المجموعات الفائقة . لا يقتصر الأمر على قابليته للتوسيع من حيث دعم أنواع البيانات وتخطيط الشجرة، بل يسمح أيضًا لكاتب الامتداد بدعم أي شروط استعلام يختارها.

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

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

التطبيقات

إن أكثر تطبيقات GiST استخدامًا هي تلك الموجودة في قاعدة البيانات العلائقية PostgreSQL ؛ كما تم تنفيذها أيضًا في خادم Informix Universal Server، وكمكتبة مستقلة، libgist.

PostgreSQL

يتضمن تطبيق GiST الخاص بـ PostgreSQL دعمًا للمفاتيح ذات الأطوال المتغيرة، والمفاتيح المركبة، والتحكم في التزامن، والاسترداد؛ وتُورَث هذه الميزات لجميع امتدادات GiST. يوجد العديد من الوحدات البرمجية المُساهم بها والمطورة باستخدام GiST والموزعة مع PostgreSQL. على سبيل المثال:

  • rtree_gist، btree_gist - تطبيق GiST لشجرة R وشجرة B
  • intarray - دعم الفهرسة لمصفوفة أحادية البعد من نوع int4
  • tsearch2 - نوع بيانات قابل للبحث (نص كامل) مع إمكانية الوصول المفهرس
  • ltree - أنواع البيانات، وطرق الوصول المفهرسة، والاستعلامات عن البيانات المنظمة على شكل هياكل شبيهة بالشجرة
  • hstore - مخزن لبيانات (المفتاح، القيمة)
  • مكعب - نوع بيانات، يمثل مكعبات متعددة الأبعاد

يوفر تطبيق PostgreSQL GiST دعم الفهرسة لنظام المعلومات الجغرافية PostGIS ونظام المعلوماتية الحيوية BioPostgres .

مراجع