Описание модели базы данных

В большинстве задач с несколькими целями (такими как скорость работы, объем файла, пополняемость и т.д.) часто приходится оптимизировать один из параметров в ущерб другим. Так, можно создать эффективный алгоритм поиска, который, однако, потребует больших затрат ресурсов памяти, места на диске и т.д. К счастью, с базами данных дело обстоит иначе. Уменьшая объем базы, можно добиться и увеличения скорости работы. Если объём базы данных  для современных поисковых систем практически не имеет значения, то скорость работы остается существенным показателем при работе в реальном времени.
В качестве основы для разработки базы словаря Мультитран было выбрано слаборастущее сильноветвящееся несимметричное Б-дерево с плавающей длиной записи и оптимизациями, расчитанными на сохранение высоких показателей работы при пополнении базы.
Классическая модель двоичного дерева была реализована следующим образом:

• Каждая база представляет собой единственный индекс, который и содержит всю поисковую и ссылочную информацию. Таким образом, отпадает необходимость хранить и поддерживать отдельную неиндексированную базу как таковую, что экономит место и время. Для хранения разнородной информации, требующей множественной индексации, используются отдельные индексы для каждого ключевого поля.
• Информация в базе хранится в виде так называемых страниц - блоков, кратных по размеру 1024. Размер страницы задается при создании базы. В базе имеется одна корневая страница, с которой всегда начинается поиск, а также страницы более низких уровней, связанных ссылками. Записи старших уровней в качестве ссылочной информации содержат номер соответствующей им поисковой страницы. Для номера страницы отводится 2 байта, что дает максимальное количество страниц в базе: 65535.
• Используется плавающая длина записи, что особенно удобно для хранения словарной информации, для которой характерно большое количество записей переменной и сравнительно небольшой длины. Запись состоит из двух частей - индексного поля, по которому производится поиск, и информационного поля, содержащего неиндексируемую информацию. В качестве основного допущения было принято решение о максимальной длине записи, составляющей 256 символов для каждого из полей. Таким образом, исходные данные, превышающие в длину 512 символов, приходится хранить в виде поледовательности записей. Впрочем, из всех 10.000.000 записей для примерно 15 баз словаря Мультитран имеется лишь около десятка таких разделенных записей.
• Реальные данные хранятся только на самых нижних уровнях базы, в то время как промежуточные уровни заняты служебной поисковой информацией, имеющей незначительную длину по сравнению с реальными данными
• При пополнении базы в случае переполнения страницы место деления находится приблизительно в середине страницы по границе записей, имеющих наименьшую общую часть. Это обеспечивает попадание на верхние уровни базы лишь самых коротких записей, что, в свою очередь, обеспечивает незначительное увеличение объема информации на верхних уровнях при пополнении базы и слабый рост высоты Б-дерева. Именно высота Б-дерева, определяемая  количеством страниц, которое необходимо считать из базы для поиска произвольной записи, и является основным показателем скорости работы базы.

Поиск в базе

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

Добавление записей

При добавлении записи происходит ее поиск и определяется место, куда она должна быть добавлена. Место добавления записи - это всегда некоторая позиция на нижнем уровне базы. Затем определяется требуемое количество байтов для новой записи. Если на странице достаточно места, новая запись записывается в текущую страницу, на чем пополнение и заканчивается. Если, однако, места на текущей странице недостаточно, страница делится приблизительно пополам (место деления определяется по минимальной общей части двух следующих подряд записей). Первая часть страницы записывается на место первоначальной страницы. Вторая часть страницы попадает в конец файла. Полученный разделитель добавляется на верхний уровень базы, где выполняются действия, аналогичные описанным. Верхний уровень также может переполниться, тогда разделитель добавляется на еще более старший уровень. Наконец, при переполнении корневого уровня базы создается новый корневой уровень и высота базы возрастает на единицу, а скорость поиска падает на (h + 1)/h, где h - высота двоичного дерева до пополнения. Происходит это, впрочем, достаточно редко, и базам, превышающим по объему 10.000 записей и достигшим высоты 3, последующий рост практически не грозит. Этим и обеспечивается высокая скорость работы словаря Мультитран.

Удаление записей

При удалении записи она физически стирается со страницы нижнего уровня. При удалении последней записи со страницы можно было бы занести эту страницу в список свободных для последующего использования, однако, исходя из практических соображений, этот механизм не был реализован. Объем лингвистических данных чаще увеличивается, чем сокращается. В связи с этим страницы, с которых удалена последняя запись, остаются в базе и могут быть устранены последующей переиндексацией.

Ограничения модели

• Длина записи не превышает 512 байт. Если объем информации окажется больше, предусматривается разделение записи на части и хранение ее в виде последовательных записей.
• Максимальное число страниц в базе не может превышать 65535. Однако, нет ограничения на размер страницы, которая может принимать любой размер, кратный 1024. Для базы объемом в 2.000.000 записей достаточно размера страницы в 4 Кб, однако, можно создавать базы со страницами в 16 или 32 Кб.
• Отсутствие форматирования полей. Каждая запись предоставляет 255 байтов для индексной и 255 байтов для информационной части. Внутреннее форматирование записи обычно производится с помощью функций класса, порожденного от класса базы банных.
• В базе остается пустое пространство после удаления последней записи со страницы. В реальных базах это происходит достаточно редко, кроме того, освободившееся пространство может использоваться для новых записей.