Лучинин З.С. Структура данных для документо-ориентированных баз данных

Аннотация: В статье приводится подход, который позволяет уменьшить нагрузку при запросах к нереляционной СУБД, благодаря использованию алгоритмов деревовидных структур хранения данных. Производительность операций по обработке данных различна в зависимости от используемых структур данных. Исследование древовидных структур, таких как B + деревья, объединения деревьев в журнальную структуру или фрактальные деревья показало, что в алгоритмах с их использованием операции с данными осуществляются быстрее, чем в MySQL. В работе рассмотрен алгоритм LSM дерева в применении к документо-ориентированным базам данных. Описана работа алгоритма при выполнении основных операций (создание, чтение, редактирование и удаление) с данными. В основу предложенного алгоритма работы с индексом ставят B деревья или B+ деревья. Недостатками данных структур являются трудоемкость балансировки дерева при добавлении нового значения в индекс и ресурсоемкость, так как индекс хранится в оперативной памяти. Дерево слияния со структурой журнала (Log-Structured Merge-Trees, LSM) является структурой данных, обеспечивающей низкую стоимость операции индексирования и высокую скорость добавления и удаления данных Алгоритм на основе LSM-дерева можно использовать при горизонтальном масштабировании. Каждый узел образует отсортированную последовательность данных по ключу. Диапазон ключей каждого сервера хранится на мастер-сервере, что позволяет без дополнительных запросов обратиться к серверу, на котором хранятся запрашиваемые данные. Таким образом, достигается увеличение скорости поиска данных и балансировка нагрузки по доступным серверам.

Ключевые слова:

Abstract: One of the main tasks of artificial intelligence is to simplify the process of human-computer interaction by providing, in particular, the opportunity to communicate in natural language via natural language interface – software that accepts text message in natural language and either translate it into some formal language, or performs some actions based on the message received. In order to understand the meaning of the text the system needs to parse each word of a sentence and analyze the interrelation between the words. Parsing words in agglutinative languages at the first glance seems quite complicated, since such languages are characterized by a variety of derivational and inflectional affixes. However, the affixes in agglutinative languages express only one meaning, which leads to stringing affixes for different grammatical meanings. Another feature of the affixes is that they may be adjoined to the base from both sides. Also in agglutinative languages there’s usually no different types of declension and conjugation. One of the agglutinative languages is Bashkir languages, for which the Bashmorph software for automatic morphology analysis is created. The Bashmorph can determine the meaning of the entered word and detect its form, case and mood, check if it is plural or singular. Based on such program the frequency dictionaries, automatic translators, search engines can be built. Technical progress poses new challenges, brings new terms and changes the environment. All these changes are reflected in language which is a mean of communication between people, and in the future, between man and machine. Creation of natural language interfaces for agglutinative languages is an important task for preservation and further development of such languages.

Keywords: