ИМЯ¶

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

БИБЛИОТЕКА¶

Стандартная библиотека языка C (libc, -lc)

СИНТАКСИС¶

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

ОПИСАНИЕ¶

Примечание: На этой странице описаны интерфейсы, предоставляемые до glibc 2.1. Начиная с glibc 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

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

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 или более поздней) в отношении авторского права, но БЕЗ КАКИХ-ЛИБО ГАРАНТИЙ.

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