Пояснительная записка (1210525), страница 4

Просмтор этого файла доступен только зарегистрированным пользователям. Но у нас супер быстрая регистрация: достаточно только электронной почты!

Текст из файла (страница 4)

Таблица 3.3 – Таблица базы данных Tag_collections (Коллекции тегов)

Таблица "Значения тегов коллекции тегов" (таблица 3.4) является связующей, поле tag_collection_id хранит ссылку на запись в таблице "Коллекции тегов", поле tag_value_id хранит ссылку на запись в таблице "Значения тегов".

Таблица 3.4 – Таблица базы данных Tag_collection_tag_values (Значения тегов коллекции тегов)

Таблица "Изображения" (таблица 3.5) хранит информацию о изображениях, которые могут использоваться для создания сообщений. Поле is_used показывает, было ли изображение уже использовано, поле path хранит путь к файлу в ресурсах программы. Результаты хеширования изображения хранятся в отдельной таблице, т.к. в зависимости от типа хеш-функции и используемой коллекции тегов, для одного изображения может быть рассчитано большое количество хеш-сумм.

Таблица 3.5 –Таблица базы данных Images(Изображения)

Таблица "Значения хешей" (таблица 3.6) является одной из ключевых таблиц, к которой будет обращено более 90% всех запросов на чтение. Она предназначена для хранения хеш-сумм изображений, поле hash_function хранит ссылку на алгоритм хеширования, image_id ссылку на запись в таблице "Изображения", tag_collection_id связано с записью в таблице "Коллекции тегов".

Таблица 3.6 – Таблица базы данных Hash_values (Значения хешей)

Таблица "Значения хешей сообщений" (таблица 3.7) служит для связи других таблиц, поле message_id хранит ссылку на запись в таблице "Сообщения", поле hash_value_id хранит ссылку на запись в таблице "Значения хешей".

Таблица 3.7 – Таблица базы данных Message_hash_values (Значения хешей сообщений)

Таблица "Индексы сообщений" (таблица 3.8) необходима для хранения номеров ключевых байт, которые являются составной частью ключа, необходимого для создания и чтения сообщений.

Таблица 3.8 – Таблица базы данных Message_indexes (Индексы сообщений)

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

Таблица 3.9 –Таблица базы данных Words(Слова)

На рисунке 3.5. изображена схема базы данных, отображающая таблицы, первичные ключи, и связи между ними.

Рисунок 3.5 – Диаграмма базы данных

Как было отмечено в описании метода, ключевую роль в быстродействии программы будет занимать поиск необходимого значения хеш-функции. Это значение, в первоначальном виде представляет собой массив байт, однако способов эффективного поиска записей с определенными значения в конкретных позициях в такой структуре данных не существует. Поэтому, необходимо считывать все записи из таблицы, и производить поиск необходимых значений в памяти программы. При использовании такого подхода, скорость работы будет тем ниже, чем больше записей хранится в таблице. Используя рассчитанную ранее вероятность, для сокрытия данных хотя в двух байтах хеш-суммы необходимо более 100 000 записей. Учитывая этот факт, становится очевидным, что описанный выше подход для практической реализации неприемлем.

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

На рисунке 3.6. изображен пример SQL запроса, извлекающего запись с определенным значение хеш-функции.

Рисунок 3.6 – Запрос на выборку значения хеш-функции

Как видно из плана выполнения изображенного на рисунке 3.7, используется последовательный поиск значений (Seq Scan), время выполнения которого составило 1,4 секунды. Это время существенно ниже, чем необходимое для последовательного поиска в памяти приложения. Тем не менее, для сообщения размером порядка 20-30 байт потребуется около 40 секунд, что все еще достаточно медленно.

Рисунок 3.7 – План выполнения SQL запроса

Одним из способов ускорения запросов в реляционных база данных, является использование индексов.

Индекс представляет собой отдельную физическую структуру данных, которая позволяет получать быстрый доступ к одной или нескольким строкам данных. Таким образом, правильная настройка индексов является ключевым аспектом улучшения производительности запросов.

Если для таблицы отсутствует подходящий индекс, для выборки строк система использует метод сканирования таблицы. Выражение сканирование таблицы означает, что система последовательно извлекает и исследует каждую строку таблицы (от первой до последней), и помещает строку в результирующий набор, если для нее удовлетворяется условие поиска в предложении WHERE. Таким образом, все строки извлекаются в соответствии с их физическим расположением в памяти. Этот метод менее эффективен, чем доступ с использованием индексов.

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

Это свойство индексов играет очень важную роль, поскольку количество операций ввода/вывода, требуемых для прохода по страницам индексов, значительно меньше, чем количество операций ввода/вывода, требуемых для прохода по соответствующим страницам данных. Иными словами, для сканирования таблицы, потребовалось бы намного больше операций ввода/вывода, чем для сканирования индекса этой таблицы.

Для полнотекстового поиска в PostgreSQL существуют специальные GIN и GIST индексы использующие триграммы.

Триграммой называется трехбуквенное сочетание слов. К примеру слово «поиск» разбивается на такие триграммы: [«__п», «_по», «пои», «оис», «иск», «ск_», «к__»], далее эти триграммы сравниваются с триграммами в базе данных.

Для ускорения поиска в данном случае подходит GIN индекс, т.к. при выполнении запросов на чтение, он является более производительным, чем GIST индекс, который к тому же позволяет производить неточный поиск, что не требуется в рамках рассматриваемой задачи.

На рисунке 3.8 изображен SQLзапрос, создающий GIN индекс для поля, хранящего значение хеш-функции.

Рисунок 3.8 – создание GIN индекса.

После создания индекса, выполним запрос аналогичный тому, что изображен на рисунке 3.6. Как видно на плане выполнения на рисунке 3.8, производится двоичный поиск по построенному индексу (Bitmap Index Scan on gin idx), время выполнения которого составило 67 миллисекунд.

Рисунок 3.9 – План выполнения SQL запроса

Таким образом, при использовании триграммного индекса скорость выполнения запроса возросла более чем в 20 раз, что подтверждает выдвинутое ранее утверждение о преимуществе в быстродействии индексированного поиска по сравнению с методом сканирования таблицы.

3.2.3 Разработка архитектуры приложения

Архитектура разрабатываемого приложения основана на использовании паттерна MVC (Model-View-Controller).

Использование этого шаблона предполагает разделение данных приложения, пользовательского интерфейса и управляющей логики на три отдельных компонента:

• модель, которая отвечает за управление данными, она сохраняет и извлекает сущности, используемые приложением;

• представление, которое несет ответственность за отображение данных, которые возвращает контроллер. С представлением тесно связано понятие шаблона, который позволяет менять внешний вид показываемой информации. В веб-приложении представление часто реализуется в виде HTML страницы;

• контроллер, который связывает модель и представление. Он получает запрос от клиента, анализирует его параметры и обращается к модели для выполнения операций над данными запроса. Далее от модели поступают запрашиваемые объекты. Затем эти объекты перенаправляются в представление, которое передаёт сформированную страницу контроллеру, который, в свою очередь, отправляет её клиенту.

Поскольку MVC не имеет строгой реализации, то существует несколько способов его реализации. Например, нет общепринятого определения, где должна располагаться бизнес-логика. Она может находиться как в контроллере, так и в модели.

В рассматриваемом случае используется реализации Spring Framework, предназначенная для создания веб-приложений. Обобщенная схема взаимодействия элементов MVC представлена на рисунке 3.10.

Характеристики

Список файлов ВКР