LinuxDoc.Rubtree - способ доступа к базе данных btree
НАЗВАНИЕbtree - способ доступа к базе данных btree
СИНТАКСИС
#include
#include
ОПИСАНИЕ
Процедура dbopen - это интерфейсная библиотека для файлов
баз данных. Один из поддерживаемых форматов - это формат
файлов btree. Основное описание методов доступа к базам
данных находится в dbopen(3). Эта страница руководства
содержит только специфичную для btree информацию.
btree - это отсортированная, сбалансированная древовидная
структура, содержащия ассоциативные пары типа
"ключ/данные".
Специфичная структура данных, с помощью которой к btree
обращается dbopen, задана в следующим образом:
typedef struct {
u_long flags;
u_int cachesize;
int maxkeypage;
int minkeypage;
u_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
Минимальное количество ключей, которые могут
храниться на одной странице. Эта величина
используется для определения количества ключей,
которые были сохранены при переполнении страницы.
Т.е., если ключ или данные длиннее, чем размер
страницы, деленный на величину minkeypage, они
будут сохранены на отдельной странице. Если minkey-
page равно 0 (минимальное количество ключей не
определено), то величина принимается равной 2-м.
psize Размер (в байтах) страницы, используемой для узлов
дерева. Минимальный размер страницы - 512 байтов,
максимальный - 64 килобайта. Если psize равно 0
(размер страницы не указан), то размер страницы
получается равным размеру одного блока текущей
системы ввода/вывода.
compare
Это функция сравнения ключей. Она возвращает целое
значение, меньшее нуля, равное нулю или большее
нуля, если первый аргумент соответственно меньше,
равен или больше второго аргумента. Одна и та же
функция для сравнения должна быть использована
каждый раз при открытии базы. Если compare
указывает на NULL (функция сравнения не
определена), то ключи сравниваются лексически,
т.е., короткие ключи меньше, чем длинные.
prefix Это функция сравнения префиксов. Данная функция,
если она определена, должна возвращать количество
байтов во втором аргументе; это необходимо для
того, чтобы определить, что данный аргумент больше,
чем перый. Если аргументы равны, функция должна
вернуть значение, равное длине ключа. Отметим, что
эффективность этой функции в большой степени
зависит от типа данных, но в некоторых случаях
помогает значительно уменьшить размер дерева и
время поиска данных. Если prefix равно NULL
(функция не определена) и функция сравнения не
определена, то по умолчанию используется
лексический метод сравнения. Если prefix равно NULL
и функция сравнения определена, то сравнения
префиксов не происходит.
lorder Порядок расположения байтов, заданный для целых
чисел, хранящихся в базе данных. Число должно
отражать порядок размещения; например, для "big
endian" порядок должен обозначаться числом 4,321.
Если lorder равен 0 (порядок не определен), то
используется значение по умолчанию.
Если файл базы уже существует (и не задан флаг O_TRUNC),
то значения, определенные в параметрах flags, lorder и
psize игнорируются, приобретая значения, указанные при
создании дерева.
Последовательное сканирование дерева производится от
меньших ключей к большим.
Место, освобожденное при удалении из дерева пар
ключ/данные, в дальнейшем не "перекрывается" и может
использоваться снова. Это значит, что физический размер
базы данных может только увеличиваться. Единственное
решение - избегать чрезмерного удаления и регулярно
создавать новое дерево при помощи полного сканирования
старого.
Поиск, вставка и удаление из дерева выполняются за время O
lg по основанию N, где основание - средняя скорость
заполнения. Довольно часто вставка упорядоченных данных в
дерево дает не столь хорошие результаты, однако, данная
реализация модифицирована так, что работа упорядоченных
вставок оказывается наилучшей и во многом более быстрой,
чем обычное заполение.
КОДЫ ОШИБОК
Функции доступа к btree могут прекратить работу программы
и присвоить errno любое значение из определенных для
библиотеки процедур dbopen(3).