компакт-диск (программное обеспечение)

Чтобы узнать о других значениях, см. CDB (значения) .

cdb , сокращение от «постоянная база данных», относится как к библиотеке , так и к формату данных, созданному Дэниелом Дж. Бернштейном . cdb на диске действует как ассоциативный массив , сопоставляя ключи со значениями, и позволяет хранить несколько значений для одного ключа. База данных констант допускает только две операции: создание и чтение. Обе операции разработаны так, чтобы быть очень быстрыми и очень надежными. Поскольку база данных не изменяется во время использования, несколько процессов могут обращаться к одной базе данных без блокировки. Кроме того, поскольку все модификации создают заменяющую базу данных, она может использовать преимущества семантики файловой системы UNIX для обеспечения гарантии надежности.

Позиции записей, длины ключей и значений, а также хеш-значения представляют собой 32-битные величины и поэтому должны умещаться в 4 гигабайта. cdb используется djbdns , fastforward , mess822 , qmail и ucspi-tcp для обеспечения высокоэффективного, надежного и простого доступа к данным.

Структура

База данных содержит весь набор данных (например, один ассоциативный массив) в одном компьютерном файле . Он состоит из трех частей: заголовка фиксированного размера, данных и набора хеш-таблиц . Поиски предназначены только для точных ключей, хотя другие типы поиска могут выполняться путем сканирования всей базы данных. Поиск осуществляется по следующему алгоритму :

• Хэшируйте ключ.
• Определите, в какой хеш-таблице и слоте эта запись . должна находиться
• Проверьте указанный слот в хеш-таблице.
  • Если слот пуст, запись не существует. Прервать поиск.
  • Если хеш слота совпадает с хешем ключа, найдите запись. Прочитайте и сравните ключ. Если они совпадают, данные найдены, поэтому завершите поиск.
  • Запись не в этом слоте. Перейдите к следующему слоту, при необходимости перейдя к началу хеш-таблицы.

При поиске ключей с несколькими значениями дополнительные значения можно найти, просто возобновив поиск в следующем слоте.

Формат

Все числа — смещения, длины и хеш-значения — представляют собой 32- битные целые числа без знака , хранящиеся в формате с прямым порядком байтов . Ключи и данные считаются непрозрачными байтовыми строками и не требуют специальной обработки.

Заголовок фиксированного размера в начале базы данных описывает 256 хеш-таблиц, указывая их положение в файле и длину в слотах. Данные хранятся в виде серии записей, каждая из которых хранит длину ключа, длину данных, ключ и данные. Нет никаких правил выравнивания или сортировки. За записями следует набор из 256 хэш-таблиц различной длины. Поскольку ноль является допустимой длиной, в базе данных может физически храниться менее 256 хеш-таблиц, но, тем не менее, считается, что их 256. Хэш-таблицы содержат ряд слотов, каждый из которых содержит хэш-значение и смещение записи. «Пустые слоты» имеют нулевое смещение.

Хэши представляют собой 32-битные целые числа без знака и начинаются со значения 5381. Для каждого байта ключа текущий хэш умножается на 33, а затем выполняется операция XOR с текущим байтом ключа. Биты переполнения отбрасываются. Слоты и таблицы тривиально вычисляются на основе хешей. Целевая таблица — это просто младшие восемь бит хеша (т. е. хэш по модулю 256), а слот внутри таблицы — это оставшиеся биты хэша по модулю длины таблицы (т. е. хэш, разделенный на 256 по модулю длины таблицы).

Библиотека

Официальный код библиотеки cdb является общедоступным : отдельные исходные файлы помечены как таковые и также доступны в общедоступном пакете djbdns . Однако остальная часть пакета cdb раньше была безлицензионным программным обеспечением , а это означает, что она должна распространяться дословно. Необычное лицензирование и простота формата побудили других повторно реализовать библиотеку и выпустить ее на более общих условиях, например, библиотеку TinyCDB Михаила Токарева, доступную в свободном доступе. Было несколько повторных реализаций, которые снимают ограничение в 4 ГиБ на размер ключа/значения, однако эти модификации несовместимы с исходным форматом, таким как CDB переменной ширины , который поддерживает исходный формат файла CDB, а также 16-битный и 64-битный формат. битовые версии.

В 2009 году весь компакт-диск стал общественным достоянием.

Примечательно, что создатель cdb не намеревается использовать cdb в качестве общей библиотеки . Это отличается практически от всех аналогичных dbm баз данных, подобных , таких как Berkeley DB . Многие из реализаций можно использовать как разделяемые библиотеки.

Внешние ссылки

• cdb cdb официальный сайт
• внутренней базы данных констант (cdb) Подробное описание формата
• Реализация и описание Содержит очень подробное описание формата в "readme.md".
• Тест QDBM. Архивировано 5 марта 2012 г. на Wayback Machine. Сравнение cdb с аналогичными пакетами.