Cdb (программное обеспечение) - cdb (software)

Для использования в других целях см. CDB (значения).

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

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

Структура

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

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

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

Формат

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

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

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

Библиотека

Официальный код библиотеки cdb: всеобщее достояние: отдельные исходные файлы отмечены как таковые и также доступны в открытом доступе djbdns упаковка. Однако остальная часть пакета cdb раньше была безлицензионное программное обеспечение, что означает, что он должен распространяться дословно. Необычное лицензирование и простота формата побудили других повторно реализовать библиотеку и выпустить ее на более общих условиях, таких как библиотека TinyCDB Майкла Токарева, доступная в открытом доступе.[2]

В 2009 году все cdb были переданы в общественное достояние.[3]

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

Рекомендации

  1. ^ Спецификация CDB
  2. ^ «TinyCDB - постоянная база данных». www.corpit.ru. Получено 2016-12-12.
  3. ^ «Часто задаваемые вопросы от дистрибьюторов».

внешняя ссылка