ИМЯ

btree - метод доступа к базе данных двоичного дерева

LIBRARY

Standard C library (libc, -lc)

СИНТАКСИС

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

ОПИСАНИЕ

Note well: This page documents interfaces provided up until glibc 2.1. Since glibc 2.2, glibc no longer provides these interfaces. Probably, you are looking for the APIs provided by the libdb library instead.

Функция 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 (порядок не определён), то используется значение по умолчанию, принятое на машине.

If the file already exists (and the O_TRUNC flag is not specified), the values specified for the arguments flags, lorder, and psize are ignored in favor of the values used when the tree was created.

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

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

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

ОШИБКИ

Функции метода доступа btree могут завершиться с ошибкой и присвоить errno любое значение из определённых для библиотеки функций dbopen(3).

ОШИБКИ

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

СМОТРИТЕ ТАКЖЕ

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.

ПЕРЕВОД

Русский перевод этой страницы руководства разработал Artyom Kunyov <artkun@guitarplayer.ru>, Azamat Hackimov <azamat.hackimov@gmail.com>, Dmitriy Ovchinnikov <dmitriyxt5@gmail.com>, Dmitry Bolkhovskikh <d20052005@yandex.ru>, ITriskTI <ITriskTI@gmail.com>, Yuri Kozlov <yuray@komyakino.ru> и Иван Павлов <pavia00@gmail.com>

Этот перевод является свободной программной документацией; он распространяется на условиях общедоступной лицензии GNU (GNU General Public License - GPL, https://www.gnu.org/licenses/gpl-3.0.html версии 3 или более поздней) в отношении авторского права, но БЕЗ КАКИХ-ЛИБО ГАРАНТИЙ.

Если вы обнаружите какие-либо ошибки в переводе этой страницы руководства, пожалуйста, сообщите об этом разработчику по его адресу электронной почты или по адресу списка рассылки русских переводчиков.