ОБЗОР

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

ОПИСАНИЕ

Примечание: В этой странице описаны интерфейсы, предоставляемые glibc до версии 2.1. Начиная с версии 2.2, glibc больше не поддерживает эти интерфейсы. Вероятно, вы ищите API, предоставляемое библиотекой 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

Значение флага определяется как логическое ИЛИ следующих значений:

R_DUP

Разрешает повторяющиеся ключи в дереве, т. е. разрешает вставку, если вставляемый ключ уже существует в дереве. По умолчанию, как описано в dbopen(3), если ключ уже встречается в дереве, новые данные записываются «поверх» старых; или запись прерывается, если задан флаг со значением R_NOOVERWRITE. Флаг R_DUP перекрывается флагом R_NOOVERWRITE; если R_NOOVERWRITE задан, то попытка записи одинаковых ключей приведёт к ошибке.

Если база данных содержит дубликаты ключей, порядок получения пар ключ/данные не определён при использовании функции get, однако функция seq, вызванная с установленным флагом R_CURSOR, всегда возвращает ссылку на «первый» ключ в группе идентичных ключей.

cachesize

Предлагаемый максимальный размер (в байтах) для кэша в памяти. Это значение носит только рекомендательный характер, и при попытке доступа к данным может выделиться большее количество памяти во избежании ошибок. Так как при каждом поиске проверяется корневая страница дерева, кэшируются наиболее часто используемые страницы, что уменьшает время, необходимое для доступа к данным. В дополнение к этому, физическая запись на диск откладывается настолько, насколько это возможно, что значительно уменьшает количество операций ввода/вывода. Очевидно, использование кэша увеличивает (но только увеличивает) вероятность повреждения или потери изменённых данных при отказе системы. Если значение cachesize равно 0 (т. е., размер не указан), то используется размер кэша по умолчанию.

maxkeypage

Максимальное количество ключей, которые могут храниться на одной странице. В настоящее время данная возможность не реализована.

minkeypage

Минимальное количество ключей, которые могут храниться в одной странице. Это значение используется для определения какие ключи будут сохранены в страницах переполнения (overflow pages), т. е., если ключ или данные длиннее, чем значение pagesize, поделённое на величину minkeypage, то они будут сохранены в страницах переполнения, а не в самой странице. Если значение minkeypage равно 0 (минимальное количество ключей не определено), то величина принимается равной 2.

psize

Размер страницы (в байтах), используемой для узлов дерева. Минимальный размер страницы — 512 байтов, максимальный — 64К. Если psize равно 0 (размер страницы не указан), то размер страницы выбирается на основе размера блока ввода/вывода задействованной файловой системы.

compare

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

prefix

Это функция сравнения префиксов. Данная функция, если она определена, должна возвращать количество байтов во втором аргументе; это необходимо для того, чтобы определить, что данный аргумент больше, чем первый. Если аргументы равны, функция должна вернуть значение, равное длине ключа. Отметим, что эффективность этой функции в большой степени зависит от типа данных, но в некоторых случаях помогает значительно уменьшить размер дерева и время поиска данных. Если prefix равно NULL (функция не определена) и функция сравнения не определена, то по умолчанию используется лексический метод сравнения. Если prefix равно NULL и функция сравнения определена, то сравнения префиксов не происходит.

lorder

Порядок расположения байтов, используемый при хранении целых чисел в метаданных базы данных. Число должно отражать порядок размещения в виде целого значения; например, порядок «big endian» должен обозначаться числом 4321. Если lorder равно 0 (порядок не определён), то используется значение по умолчанию, принятое на машине.

Если файл уже существует (и не задан флаг O_TRUNC), то значения, определённые в параметрах flags, lorder и psize, игнорируются, приобретая значения, указанные при создании дерева.

Последовательное сканирование дерева производится от меньших ключей к большим.

Место, освобождённое при удалении из дерева пар ключ/данные, в дальнейшем никогда не возвращается, хотя и может использоваться снова. Это значит, что физический размер базы данных может только увеличиваться. Единственное решение — избегать чрезмерного удаления и регулярно создавать новое дерево при помощи полного сканирования старого.

Поиск, вставка и удаление из дерева выполняются за время O lg по основанию N, где основание — средняя скорость заполнения. Довольно часто вставка упорядоченных данных в дерево даёт не столь хорошие результаты, однако, данная реализация изменена так, что работа упорядоченных вставок оказывается наилучшей и во многом более быстрой, чем обычное заполнение.