نام (NAME)

cdb - قالب فایل پایگاه‌داده ثابت (Constant DataBase)

توضیحات (DESCRIPTION)

یک پایگاهnjداده cdb یک تکnjفایل است که برای نگاشت «کلیدها» به «مقادیر» بهnjکار میnjرود و شامل رکوردهایی از جفتnjهای (key, value) است. فایل از ۳ بخش تشکیل شده است: toc (فهرست مطالب)، داده (data) و نمایه (index یا جدولnjهای درهمnjسازی).

بخش Toc دارای طول ثابت ۲۰۴۸ بایت است که شامل ۲۵۶ اشارهnjگر به جدولnjهای درهمnjسازی درون بخشnjهای نمایه است. هر اشارهnjگر از موقعیت یک جدول درهمnjسازی به بایت از ابتدای فایل و اندازه جدول درهمnjسازی بر حسب مدخلnjها تشکیل شده است؛ هر دو اعداد صحیح بدون علامت ۴ بایتی (۳۲ بیتی) به فرم little-endian هستند. طول جدول درهمnjسازی میnjتواند صفر باشد، به این معنی که جدول درهمnjسازی مربوطه خالی است.

دقیقاً پس از بخش toc، بخش داده بدون هیچnjگونه ترازسازی (alignment) قرار میnjگیرد. این بخش شامل مجموعهnjای از رکوردهاست که هرکدام شامل طول کلید، طول مقدار (داده)، خود کلید و خود مقدار هستند. مجدداً، طول کلید و مقدار اعداد صحیح بدون علامت ۴ بایتی هستند. هر رکورد بعدی بدون ترازسازی خاصی به دنبال رکورد قبلی میnjآید.

پس از بخش داده، بخش نمایه (جدولnjهای درهمnjسازی) میnjآید. این بخش باید همراه با بخش toc بررسی شود، جایی که هر یک از حداکثر ۲۵۶ جدول درهمnjسازی تعریف شدهnjاند. بخش نمایه شامل مجموعهnjای از جدولnjهای درهمnjسازی است که موقعیت شروع و طول آنnjها در بخش toc مشخص شده است. هر جدول درهمnjسازی دنبالهnjای از رکوردهاست که هرکدام دو عدد را نگه میnjدارند: مقدار درهمnjسازی (hash value) کلید و موقعیت رکورد در بخش داده (بایتnjها از ابتدای فایل تا اولین بایت از طول کلید که رکورد داده را آغاز میnjکند). اگر موقعیت رکورد صفر باشد، این یک خانه خالی در جدول درهمnjسازی است که به جایی اشاره نمیnjکند.

تابع درهمnjسازی CDB عبارت است از:

hv = ((hv << 5) + hv) ^ c

برای تکnjتک بایتnjهای c کلید، با شروع از hv = 5381.

بخش Toc بر اساس (hv % 256) نمایهnjگذاری میnjشود، یعنی مقدار هش به پیمانه ۲۵۶ (تعداد مدخلnjها در بخش toc).

برای یافتن یک رکورد، باید: نخست، مقدار درهمnjسازی (hv) کلید را محاسبه کنید. دوم، به شماره جدول درهمnjسازی یعنی hv به پیمانه ۲۵۶ نگاه کنید. اگر خالی باشد، چنین کلیدی وجود ندارد. اگر خالی نباشد، سوم، در میان خانهnjهای درون آن جدول درهمnjسازی حلقه بزنید، با شروع از خانه شماره hv تقسیم بر ۲۵۶ به پیمانه طول آن جدول، یا ((hv / 256) % htlen)، و این hv را در جدول درهمnjسازی جستجو کنید. جستجو را با رسیدن به خانه خالی (اگر موقعیت رکورد صفر باشد) یا زمانی که همه خانهnjها پیمایش شدند متوقف کنید (به جستجوی چرخشی توجه کنید که از انتهای جدول به ابتدای آن میnjپرد). هنگامی که مقدار درهمnjسازی مورد نظر در جدول درهمnjسازی یافت شد، به کلید رکورد مربوطه نگاه کرده و آن را با کلید مورد نظر مقایسه کنید. اگر همnjطول و با یکدیگر برابر باشند، رکورد پیدا شده است؛ در غیر این صورت، این کار را با خانه بعدی جدول درهمnjسازی تکرار کنید. توجه داشته باشید که ممکن است چندین رکورد با یک کلید یکسان وجود داشته باشد.

همچنین ببینید (SEE ALSO)

cdb(1), cdb(3).

نویسنده (AUTHOR)

بسته tinycdb توسط Michael Tokarev <mjt+cdb@corpit.ru> بر پایه ایدهnjها و قالب فایل مشترک با کتابخانه اصلی cdb اثر Dan Bernstein نوشته شده است.

مجوز (LICENSE)

نرمnjافزار Tinycdb تحت مجوز MIT منتشر شده است.