QDBM (Quick DataBase Manager)

Материал из Национальной библиотеки им. Н. Э. Баумана
Последнее изменение этой страницы: 18:59, 21 января 2019.
QDBM
QDBM.png
Разработчики: Mikio Hirabayashi
Выпущена: 2000
Постоянный выпуск: v1.8.78 / 26 September 2016 года; 3 years ago (2016-09-26)
Написана на: C
Тип ПО: Database engine
Веб-сайт fallabs.com/qdbm

QDBM (англ. Quick DataBase Manager) - это библиотека, предназначенная для управления базами данных типа ключ-значение. В качестве ключа и значения могут использоваться как двоичные данные, так и символьная строка. Записи организованы в хеш-таблицу или B+ дерево[Источник 1].

В случае хэш-таблицы каждый ключ должен быть уникальным в базе данных, поэтому невозможно хранить две или более записей с совпадающими ключами. В базе данных предусмотрены следующие методы доступа: сохранение записи с ключом и значением, удаление записи по ключу, извлечение записи по ключу. Кроме того обеспечивается произвольный доступ к каждому ключу. Эти методы доступа аналогичны библиотекам DBM (или NDBM, GDBM), определенным в стандарте UNIX. QDBM является более высокопроизводительной альтернативой DBM.

В случае B+ дерева записи, ключи которых дублируются, могут быть сохранены. Методы доступа для хранения, удаления и извлечения аналогичны методам доступа в хэш-таблице. Записи хранятся в порядке с помощью функции сравнения, назначенной пользователем. Доступ к каждой записи возможен с помощью курсора в порядке возрастания или убывания. Согласно этому механизму реализован прямой поиск строк и поиск диапазона целых чисел.

QDBM написан на C и предоставляется как API для C, Java, Perl и Ruby. QDBM доступен на платформах, которые имеют API, соответствующий POSIX. QDBM является свободным программным обеспечением, лицензируемым в соответствии с GNU Lesser General Public License.

Лицензирование

QDBM - распространяется как свободное программное обеспечение. Пользователи могут распространять его или изменять его в соответствии с GNU Lesser General Public License[1] версии 2.1 или более поздней.

QDBM распространяется в надежде, что он будет полезен, но без каких-либо гарантий. См. GNU Lesser General Public License для получения более подробной информации.

Особенности

Особенности применения хэш базы данных

QDBM разработан с оглядкой на GDBM, но при разработке преследовались следующие три цели: более высокая скорость обработки, меньший размер файла базы данных и более простой API. Но в QDBM сохранились три ограничения традиционных DBM: процесс может обрабатывать только одну базу данных, размер ключа и значения ограничены, файл базы данных всё ещё является неплотным[Источник 2].

QDBM использует значение хэш-функции для извлечения записей. Временная сложность поиска равна O (1)[2]. То есть время, необходимое для извлечения записи, является постоянным, независимо от масштаба базы данных. То же самое относится и к записи и удалению. Коллизии значений хеша разрешаются с помощью метода цепочек. Структура данных цепочек представляет собой двоичное дерево поиска. В худшем случае временная сложность извлечения составляет O (log n).

QDBM предоставляет два режима для подключения к базе данных: reader и writer. В режиме reader можно выполнять поиск, но нельзя записывать и удалять. В режиме writer можно выполнять все методы доступа. Разграничение между процессами осуществляется путем блокировки файлов при попытке подключения. В то время, когда к базе данных подключен процесс в режиме writer, не могут подключаться другие reader или writer. Пока процесс reader подключен к базе данных, другие reader могут подключаться, а writer - нет. Благодаря этому механизму согласованность данных гарантируется при одновременных подключениях в многозадачной среде.

Традиционный DBM предоставляет два режима операций хранения: insert и replace. В случае, если ключ совпадает с уже существующей записью, операция вставки сохраняет существующее значение, а операция замены преобразует его в указанное значение. В дополнение к двум режимам, QDBM предоставляет режим concatenate. В этом режиме новое значение объединяется в конце существующего значения и сохраняется. Эта функция полезна при добавлении элемента к значению в виде массива. Более того, хотя DBM имеет метод для извлечения значения из базы данных только путем чтения всей области записи, QDBM имеет метод для извлечения части области записи. Когда значение рассматривается как массив, эта функция также полезна.

Что касается многих файловых систем, невозможно обработать файл, размер которого превышает 2 ГБ. Для решения этой проблемы QDBM предоставляет базу данных каталогов, содержащую несколько файлов базы данных. Благодаря этой функции теоретически можно обрабатывать базу данных, общий размер которой составляет до 1 ТБ. Более того, поскольку файлы базы данных могут быть развернуты на нескольких дисках, скорость операций обновления может быть улучшена с помощью RAID-0. Файлы базы данных также могут быть развернуты на нескольких файловых серверах с использованием NFS.

Особенности применения базы данных на основе B+ дерева

Хотя база данных дерева B + медленнее, чем база данных хэшей, она имеет упорядоченный доступ к каждой записи. Порядок может быть определён пользователями. Записи B+ дерева сортируются и располагаются на логических страницах. Для каждой страницы поддерживается упрощённый индекс, организованный в виде В дерева, являющегося сбалансированным деревом. Таким образом, временная сложность поиска и других операций составляет O (log n). Курсор предоставляется для доступа к каждой записи по порядку. Курсор может перейти на позицию, указанную клавишей, и может перейти вперед или назад от текущей позиции. Поскольку каждая страница организована в виде двойного связанного списка, временная сложность перемещения курсора равна O (1) .

База данных на B+ дереве, основана на вышеуказанной хеш базе данных. Поскольку каждая страница дерева B + хранится как каждая запись хеш базы данных, база данных дерева B + наследует эффективность управления хранением хеш-базы данных. Поскольку заголовок каждой записи меньше, а выравнивание каждой страницы регулируется в соответствии с размером страницы, в большинстве случаев размер файла базы данных уменьшается вдвое по сравнению с хеш базой данных. Хотя для обновления дерева B + требуется работа многих страниц, QDBM ускоряет процесс, кэшируя страницы и сокращая файловые операции. В большинстве случаев, поскольку весь упрощённый индекс кэшируется в памяти, можно извлечь запись одной или несколькими файловыми операциями.

База данных дерева B + имеет механизм транзакций. Можно выполнить серию операций между началом и концом транзакции в виде единовременного кода или отменить транзакцию и выполнить откат до состояния перед транзакцией. Даже если во время транзакции происходит сбой процесса, файл базы данных не нарушается..

В QDBM были включены библиотеки сжатия данных без потерь. Содержимое каждой страницы дерева B + сжимается и сохраняется в файле. Поскольку каждая запись на странице имеет сходные шаблоны, ожидается высокая эффективность сжатия благодаря алгоритму Лемпеля-Зива. При обработке текстовых данных размер базы данных уменьшается примерно до 25%. Если масштаб базы данных большой, а дисковый ввод-вывод является узким местом, использование сжатия значительно повышает скорость обработки.

Поддерживаемые платформы

QDBM реализован на основе синтаксиса ANSI C (C89) и использует только API, определенные в ANSI C или POSIX. Таким образом, QDBM работает на большинстве UNIX и его совместимых ОС. Что касается C API, проверка работы была выполнена на следующих платформах:

Сравнение с другими DBM

Этот сравнительный тест показывает время обработки файла базы данных. Скорость записи проверялась при сохранении 1000000 записей. Скорость чтения проверялась по скорости получения всех этих записей. И ключ и значение это 8-байтные строки вида: "00000001", "00000002"... Платформа: Linux 2.4.31 kernel, EXT2 файловая система, Pentium4 1.7 GHz CPU, 1024MB RAM.

Результаты сравнения QDBM с другими DBM[Источник 3]
Название Описание Время записи Время чтения Размер файла
QDBM Quick Database Manager 1.8.74 1,89 1,58 55257
NDBM New Database Manager 5.1 8,07 7,79 814457
GDBM GNU Database Manager 1.8.3 14,01 5,36 82788
TDB Trivial Database 1.0.6 9,64 2,22 51056
CDB Tiny Constant Database 0.75 0,87 0,80 39065
BDB Berkeley DB 4.4.20 9,62 5,62 40956
QDBM-BT-ASC B+ tree API of QDBM (ascending order) 2,37 1,78 24304
QDBM-BT-RND B+ tree API of QDBM (at random) 10,90 4,82 15362

Единицы измерения времени - секунды. Единицы измерения размера файла - килобайты.

Примечания

  1. [1] / GNU LESSER GENERAL PUBLIC LICENSE, 2007
  2. [2] / Хэш-таблица// Kvodo, 2018

Источники

  1. QDBM:Overview // QDBM: Quick Database Manager. [2000–2007]. Дата обновления: 26.10.2006. URL: https://fallabs.com/qdbm/index.html (дата обращения: 25.12.2018)
  2. Fundamental Specifications of QDBM Version 1 // QDBM: Quick Database Manager. [2000–2007]. Дата обновления: 26.10.2006. URL: https://fallabs.com/qdbm/index.html (дата обращения: 25.12.2018)
  3. QDBM: Quick Database Manager// Github. [2018]. https://github.com/winlibs/qdbm/blob/master/bros/result.xls (дата обращения: 26.12.2018)