Делаем СУБД

Сейчас вроде бы нет острой необходимости создавать свои системы управления базами данных (СУБД), так как есть бесплатные варианты – вспомнить хотя бы MySQL или SQLite, но для небольших проектов они могут быть слишком избыточными. Кроме того, разрабатывать свою СУБД просто интересно. Для примера можно составить нечто вроде СУБД FoxPro в варианте для MS-DOS, которую затем можно перенести в Windows или Linux.

1. Структура базы.

Иерархические базы данных интересны, но мы поговорим о более простой структуре – реляционной, где данные хранятся в строках и полях. Строки в таблице имеют одинаковый размер, поэтому их удобно редактировать. Стандартные поля тоже имеют одинаковый размер и могут хранить значения данных разных типов: для обычной СУБД это целый, вещественный, логический типы; типы строка и «дата»; иногда используются автоинкрементный тип, ссылка на объект произвольного размера, хранящегося в отдельном файле. К примеру, база данных по фильмам:

Год Выхода, Оригинальное Название, Перевод, Размер Мб, Каталог

Дата, Строка, Строка, Размер, Строка

2012, Resident Evil 5, Обитель Зла 5, 1400, e:vdbhorrors
e5.avi

и т.д.; строк может быть много. Кстати, если каждое поле взять в кавычки и разделить запятыми, то получится текстовый документ формата CSV, который часто используется как в СУБД и электронных таблицах для подгрузки или выгрузки данных.

Строки могут иметь различную длину – от 1 символа до 255, еще можно заранее определить тип вещественных данных (сколько запятых после нуля будут использоваться). Вообще, все поля можно хранить в виде текста, но иногда имеет смысл использовать стандартный формат хранения для чисел, дат и других типов, определенных в языке программирования. В таблице нужно предусмотреть также заголовок, где будет описана таблица:

Идентификатор СУБД, версия
Дата создания и последнего редактирования
Используемая кодовая страница
Длина заголовка
Число полей
Контрольная сумма заголовка

Поле 1: имя, тип, размер плюс число знаков после запятой/длина строки (обычно 4 поля).
…
Поле N …

2. Индексные файлы

Число записей в таблице может иметь огромное значение, и имеет смысл упорядочивать их по имени поля или другим признакам. Для этого используется такой подход: сами записи хранятся «как попало», а к таблице добавляется индексный файл. В нем хранятся запросы-фильтры к таблице, а также закодированные номера строк и их пар относительно других таблиц (таблицы могут быть связаны по общему ключевому полю). Запрос может быть простым, к примеру, sort by Год Выхода + Название, select for Год Выхода <= 2005 и т.д. Эти команды составляют искусственный язык запросов, который называется язык СУБД. Часто вместо его изобретения используют язык dBase или SQL, но тут уж как кому удобнее. Индексы обычно хранятся в виде B-деревьев, но более быстрый доступ к данным представляют инвертированные списки. СУБД всегда использует индексы вместо обращения к реальным данным, если это возможно.

Тип доступа к данным (интерфейс)

Для придуманного языка СУБД можно составить свой интерфейс вроде Бейсик-среды программирования. В этом случае придется поддерживать команды создания таблиц, их редактирования (браузер таблиц), команды поиска, фильтрации, связи между таблицами. В FoxPro, к примеру, это простые команды вроде use (открыть таблицу), set filter (установить фильтр), browse (открыть браузер) и т.д. – таких команд может быть сотни, причем каждая имеет свои параметры и модификаторы. Набор таких команд хранится в текстовых файлах или в скомпилированном виде, причем доступны шифровка программы и ее компиляция вместе с исполняемой средой). Каждая команда языка поддерживается исполняемой библиотекой и обычно написана на языке Си, хотя можно взять любой язык программирования.

Для конкретных задач, где программирование не требуется (в поисковых системах на рабочих местах) вместо полноценной среды можно использовать ее подмножество, где язык запросов строго ограничен полями ввода. Соответственно, в этом случае с таблицей можно проводить не все операции, а только разрешенные – найти, отфильтровать, вывести.

Наиболее интересный способ - создание CALL-интерфейса. Для этого часто создают резидентную программу, которая находится в памяти и принимает команды от любых программ. В целях унификации для этих запросов разрабатывают карточку запроса, где перечислены все нужные поля. Эта программа берет запрос, работает с таблицами и возвращает готовый результат опять через карточку запроса. Таким образом, можно даже организовать сетевой доступ к базе данных. Простейший же случай – создание библиотеки, которая напрямую работает с базой данных: в этом случае резидентный помощник не нужен, но библиотека должна иметь много вариантов для каждого языка программирования и их версий.