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

Методы и способы использования бинарного поиска для оптимизации запроса на выборку данных. Обзор php+MySQL и задача переноса условия с полей системы управления базами данных без индексов на первичные ключи, что значительно ускоряет работу запроса.

Рубрика Программирование, компьютеры и кибернетика
Вид статья
Язык русский
Дата добавления 06.03.2019
Размер файла 16,3 K

Отправить свою хорошую работу в базу знаний просто. Используйте форму, расположенную ниже

Студенты, аспиранты, молодые ученые, использующие базу знаний в своей учебе и работе, будут вам очень благодарны.

Размещено на http://www.allbest.ru/

Размещено на http://www.allbest.ru/

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

С ростом популярности СУБД его поддержка неизбежно начинает требовать всё больших и больших ресурсов[1]. Первое время с нагрузкой можно (и, несомненно, нужно) бороться путём оптимизации алгоритмов и / или архитектуры самого приложения. Однако, что делать, если всё, что можно было оптимизировать, уже оптимизировано, а приложение всё равно не справляется с нагрузкой?

И так, допустим, что оптимизация уже проведена, но приложение всё равно не справляется с нагрузкой. В таком случае решением проблемы, очевидно, может послужить разнесение его по нескольким хостам, с целью увеличения общей производительности приложения за счёт увеличения доступных ресурсов. Такой подход имеет официальное название - «масштабирование» (scale) приложения. Точнее говоря, под «масштабируемостью» (scalability) называется возможность системы увеличивать свою производительность при увеличении количества выделяемых ей ресурсов. Различают два способа масштабирования: вертикальное и горизонтальное. Вертикальное масштабирование подразумевает увеличение производительности приложения при добавлении ресурсов (процессора, памяти, диска) в рамках одного узла (хоста). Горизонтальное масштабирование характерно для распределённых приложений и подразумевает рост производительности приложения при добавлении ещё одного узла (хоста)[2].

Предположим, что каждая таблица СУБД, в среднем содержала 40 миллионов записей. При этом мы бы использовали 3 INNER JOIN. Получается, что временная таблица состояла бы из 4*4*4*10^21 = 64*10^21 записей. Это колоссальная цифра. И загружать СУБД таким запросом для сбора статистики - непозволительная роскошь.

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

Определение метода бинарного поиска

Пусть у нас имеется отсортированный массив из n элементов:

Первый элемент массива = 1

Последний элемент массива = n

Нам необходимо найти индекс элемента со значением f.

Каждый шаг заключается в том, что мы вычисляем середину массива:

Середина массива = round (Первый элемент + Последний элемент)/2

Затем вычисляем значение этого элемента и проверяем больше или меньше полученное значение в сравнении с искомым f. Диапазон поиска уменьшается в 2 раза:

Если <значение середины> > f, то

Последний элемент массива = значение середины

Иначе

Первый элемент массива = значение середины

Данные шаги повторяются пока не наступит одно из условий:

· Модуль разности значений середины и f меньше некоторого эпсилон (где эпсилон, некоторая погрешность)

· Количество итераций превысило значение log2 (количество элементов в массиве)

Таким образом, мы ускоряем поиск нужного элемента за счёт сокращения диапазонов поиска.

Практическое использование метода

Итак, предположим, что нам необходимо сделать INNER JOIN на 3 таблицы, а затем задать условие «столбец х в диапазоне между 10 и 20». Причём столбец х не имеет индекса. Это будет очень долго выполнятся. Тут и приходит на помощь это простой способ.

Берем таблицу с этим самым столбцом и применяем на ней бинарный поиск, для поиска диапазона первичных ключей, удовлетворяющих условию 10<=x<=20. Учитывая, что для подобной выборки мы будем использовать только индексы, то очень скоро мы получим нужную пару значений.

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

С этим диапазоном мы идём снова к нашему запросу, но теперь вместо условия WHERE x >= 10 AND x <= 20 мы пишем WHERE id_x BETWEEN min_id_x AND max_id_x, где min_id_x и max_id_x - значение нижнего и верхнего краёв диапазона, удовлетворяющего условию.

Что мы получаем: теперь мы делаем выборку не по некому столбцу х, а по первичному ключу. Время потраченное на обход одной таблицы сэкономлено. Аналогичную процедуру можно провести с другими условиями в запросе.

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

Пример кода на языке программирования Cи для поиска элемента x в массиве a[n], отсортированного в возрастающем порядке[2]:

size_t first = 0; /* Первый элемент в массиве */

size_t last = n; /* Элемент в массиве, СЛЕДУЮЩИЙ ЗА последним */

/* Если просматриваемый участок непустой, first<last */

size_t mid;

if (n == 0)

{

/* массив пуст */

}

else if (a[0] > x)

{

/* не найдено; если вам надо вставить его со сдвигом-то в позицию 0 */

}

else if (a [n - 1] < x)

{

/* не найдено; если вам надо вставить его со сдвигом-то в позицию n */

}

while (first < last)

{

/* ВНИМАНИЕ! В отличие от более простого (first+last)/2, этот код стоек к переполнениям.

Если first и last знаковые, возможен код (unsigned) (first+last) >> 1. */

mid = first + (last - first) / 2;

if (x <= a[mid])

{

last = mid;

}

else

{

first = mid + 1;

}

}

/* Если проверка n==0 в начале опущена - значит, тут раскомментировать! */

if (/*n!=0 &&*/ a[last] == x)

{

/* Искомый элемент найден. last - искомый индекс */

} else

{

/* Искомый элемент не найден. Но если вам вдруг надо его вставить со сдвигом, то его место - last. */

}

Практические приложения метода двоичного поиска разнообразны[3]:

· Широкое распространение в информатике применительно к поиску в структурах данных. Например, поиск в массивах данных осуществляется по ключу, присвоенному каждому из элементов массива (в простейшем случае сам элемент является ключом).

· Также его применяют в качестве численного метода для нахождения приближённого решения уравнений.

· Метод бисекции используется для поиска численных решений уравнений[4].

· Метод используется для нахождения экстремума целевой функции и в этом случае является методом условной одномерной оптимизации. Когда функция имеет вещественный аргумент, найти решение с точностью до е можно за время log 21 / е. Когда аргумент дискретен, и изначально лежит на отрезке длины N, поиск решения займёт 1 + log_2N! времени. Наконец, для поиска экстремума, скажем для определённости минимума, на очередном шаге отбрасывается тот из концов рассматриваемого отрезка, значение в котором максимально.

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

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

Во-вторых, данной способ подходит не для всех решений, т.к. строки в таблице должны быть отсортированы в некотором порядке.

Библиография

бинарный управление запрос выборка

1. «Intrusion Detection with Artificial Neural Networks (Anomaly based Intrusion Detection using Backpropagation Neural Networks)», Moazzam Hossain, ISBN 978-3-6392-1038-5, 2010 г.

2. «Snort Cookbook», Angela Orebaugh, ISBN 0596007914, 2005 г.

3. «A New Host-Based Hybrid IDS Architecture-A Mind Of Its Own (The Know-how Of Host-Based Hybrid Intrusion Detection System Architecture Using Machine Learning Algorithms With Feature Selection)», Murat Topallar, ISBN 978-3-6391-7288-1, 2010 г.

4. «Intrusion Detection System», Frederic P. Miller, ISBN 978-6-1328-6369-0, 2010 г.

Размещено на Allbest.ru


Подобные документы

  • Возможности системы управления базами данных Access. Структура простейшей базы данных: свойства ее полей, типы данных, безопасность и режим работы. Определение связей между таблицами в базе данных. Использование запроса на выборку, макроса и отчетов.

    курсовая работа [1,7 M], добавлен 05.12.2010

  • Общие сведения о системах управления базами данных MS Access. Использование языка QBE для создания запросов на выборку данных. Параметрические и перекрестные запросы. Запросы с автоподстановкой, на выборку дубликатов и записей, не имеющих соответствия.

    курсовая работа [32,8 K], добавлен 03.06.2015

  • Преимущества и недостатки роботизированной сварки. Характеристика видов систем управления базами данных. Информационная модель сварочного робота, системы управления роботом сварочных клещей. Критерии выбора робота и структура запроса на выборку.

    курсовая работа [3,3 M], добавлен 22.12.2014

  • Составление таблицы согласно образцу в программе MS Excel. Создание данных таблицы базы данных. Введение формул в программе MS Excel. Установление связи между таблицами. Создание запроса на выборку данных из одной таблицы с помощью мастер запросов.

    контрольная работа [4,0 M], добавлен 17.04.2016

  • Проектирование базы данных, предназначенной для автоматизации библиотеки аудиокниг. Запрос на выборку с условием отбора, с созданием вычисляемого поля. Создание формы с круговой диаграммой на основе запроса на выборку. Проектирование форм и отчетов базы.

    контрольная работа [6,2 M], добавлен 06.01.2013

  • Основные понятия информационных баз данных. Реляционная модель данных. Создание с помощью программы СУБД Access таблиц "Оптовый магазин", их сортировка по различным критериям. Введение многотабличного запроса на выборку с обновлением записей и отчетом.

    контрольная работа [25,6 K], добавлен 26.02.2009

  • Разработка программы на языке С#, которая будет заниматься построением бинарного дерева для исходных данных и их редактированием, поиском информации о товарах по заданному ключу. Графические схемы алгоритмов поиска и удаления элемента бинарного дерева.

    курсовая работа [796,9 K], добавлен 22.02.2016

  • Логическое моделирование данных. Структура реляционных данных. Ограничения, которые должны выполняться в любой реляционной базе данных. Запрос на выборку с параметром, перекрестные запросы. Создание запроса в режиме SQL. Создание формы при помощи мастера.

    курсовая работа [1,2 M], добавлен 09.09.2012

  • Краткая характеристика, главные преимущества и область применения MS Access. Базы данных и системы управления базами данных. Описание пошагового создания базы данных, таблиц, форм, запроса и отчета. Особенности и функциональные возможности MS Access.

    курсовая работа [3,4 M], добавлен 23.09.2010

  • Структура многотабличных баз данных, создание и редактирование таблиц в MS Access, установка связей между таблицами, фильтрация и сортировка данных, создание БД "Месторождения нефти". Составление форм, запроса на выборку по разным полям и отчетов.

    лабораторная работа [531,5 K], добавлен 13.02.2012

Работы в архивах красиво оформлены согласно требованиям ВУЗов и содержат рисунки, диаграммы, формулы и т.д.
PPT, PPTX и PDF-файлы представлены только в архивах.
Рекомендуем скачать работу.