الاسم¶

btree - طريقة الوصول إلى قاعدة بيانات btree

المكتبة¶

مكتبة سي المعيارية (libc، -lc)

موجز¶

#include <sys/types.h> #include <db.h>

الوصف¶

ملاحظة جيدة: توثق هذه الصفحة الواجهات المقدمة حتى glibc 2.1. ومنذ الإصدار glibc 2.2، لم تعد glibc توفر هذه الواجهات. من المحتمل أنك تبحث عن واجهات برمجة التطبيقات (APIs) التي توفرها مكتبة libdb بدلاً من ذلك.

الدالة dbopen(3) هي واجهة المكتبة لملفات قاعدة البيانات. أحد تنسيقات الملفات المدعومة هي ملفات btree. الوصف العام لطرق الوصول إلى قاعدة البيانات موجود في dbopen(3)، تصف صفحة الدليل هذه فقط المعلومات الخاصة بـ btree.

هيكل بيانات btree هو هيكل شجري مرتب ومتوازن يخزن أزواج المفتاح/البيانات المرتبطة.

هيكل البيانات الخاص بطريقة الوصول إلى btree المُقدم إلى dbopen(3) يُعرّف في ملف التضمين <db.h> كالتالي:

typedef struct {


    unsigned long flags;


    unsigned int  cachesize;


    int           maxkeypage;


    int           minkeypage;


    unsigned int  psize;


    int         (*compare)(const DBT *key1, const DBT *key2);


    size_t      (*prefix)(const DBT *key1, const DBT *key2);


    int           lorder;
} BTREEINFO;

عناصر هذا الهيكل هي كما يلي:

flags

تُحَدَّد قيمة العلم عن طريق إجراء عملية OR لأي من القيم التالية:

cachesize

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

maxkeypage

الحد الأقصى لعدد المفاتيح التي ستُخزن على أي صفحة واحدة. غير مُنفذ حاليًا.

minkeypage

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

psize

حجم الصفحة هو الحجم (بالبايت) للصفحات المستخدمة للعقد في الشجرة. الحد الأدنى لحجم الصفحة هو 512 بايت والحد الأقصى لحجم الصفحة هو 64 كيبيبايت. إذا كانت psize تساوي 0 (لم يُحدد حجم صفحة)، فسيُختار حجم صفحة بناءً على حجم كتلة الإدخال/الإخراج لنظام الملفات الأساسي.

compare

Compare هي دالة مقارنة المفاتيح. يجب أن تُرجع عددًا صحيحًا أقل من، أو يساوي، أو أكبر من الصفر إذا كانت وسيطة المفتاح الأولى تُعتبر على التوالي أقل من، أو مساوية، أو أكبر من وسيطة المفتاح الثانية. يجب استخدام نفس دالة المقارنة على شجرة معينة في كل مرة تُفتح فيها. إذا كانت compare NULL (لم تُحدد دالة مقارنة)، فتُقارن المفاتيح معجميًا، مع اعتبار المفاتيح الأقصر أقل من المفاتيح الأطول.

prefix

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

lorder

ترتيب البايتات (byte order) للأعداد الصحيحة في البيانات الوصفية المخزنة لقاعدة البيانات. يجب أن يمثل الرقم الترتيب كعدد صحيح؛ على سبيل المثال، ترتيب النهاية الكبرى (big endian) سيكون الرقم 4,321. إذا كان lorder هو 0 (لم يُحدد أي ترتيب)، فسيُستخدم ترتيب المضيف الحالي.

إذا كان الملف موجودًا بالفعل (ولم يُحدد العلم O_TRUNC)، فتُتجاهل القيم المحددة للوسائط flags وlorder وpsize لصالح القيم المستخدمة عند إنشاء الشجرة.

المسح التسلسلي الأمامي للشجرة يكون من المفتاح الأصغر إلى الأكبر.

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

البحث والإدراج والحذف في btree ستكتمل جميعًا في O lg base N حيث base هو متوسط عامل الامتلاء. غالبًا، إدراج بيانات مرتبة في btrees يؤدي إلى عامل امتلاء منخفض. هذا التنفيذ عُدل لجعل الإدراج المرتب أفضل حالة، مما ينتج عنه عامل امتلاء صفحة أفضل بكثير من المعتاد.

الأخطاء¶

روتينات طريقة الوصول btree قد تفشل وتضبط errno لأي من الأخطاء المحددة لروتين المكتبة dbopen(3).

العلل¶

يُدعم ترتيب البايتات الكبير (big endian) والصغير (little endian) فقط.

انظر أيضًا¶

dbopen(3), hash(3), mpool(3), recno(3)

The Ubiquitous B-tree, Douglas Comer, ACM Comput. Surv. 11, 2 (June 1979), 121-138.

Prefix B-trees, Bayer and Unterauer, ACM Transactions on Database Systems, Vol. 2, 1 (March 1977), 11-26.

The Art of Computer Programming Vol. 3: Sorting and Searching, D.E. Knuth, 1968, pp 471-480.

ترجمة¶

تُرجمت هذه الصفحة من الدليل بواسطة زايد السعيدي <zayed.alsaidi@gmail.com>

هذه الترجمة هي وثيقة مجانية؛ راجع رخصة جنو العامة الإصدار 3 أو ما بعده للاطلاع على شروط حقوق النشر. لا توجد أي ضمانات.

إذا وجدت أي أخطاء في ترجمة صفحة الدليل هذه، يرجى إرسال بريد إلكتروني إلى قائمة بريد المترجمين: kde-l10n-ar@kde.org.