[МУЗЫКА]
[МУЗЫКА] Здравствуйте.
В прошлый раз мы говорили с вами о наиболее часто используемых методах
индексирования, которые используются для баз данных.
Сегодня мы поговорим про некоторые такие экзотические виды индексирования,
которые могут потребоваться в определённых ситуациях.
И поговорим также о том,
что такое оптимальное выполнение запросов и кто этим занимается в СУБД.
Пространственные типы данных.
Когда они могут понадобиться?
Мы можем захотеть хранить в нашей базе данных информацию, например,
о транспортной схеме, об остановках,
о магазинах или о других пространственных объектах.
Для этого у нас есть специфические типы данных.
Они немного зависят от СУБД,
но обычно предоставляется две возможности хранения пространственных данных.
Это геометрические данные и географические данные.
Геометрические данные используются для планарных или евклидовых данных,
а географические данные хранят данные в
виде координат широты и долготы,
так называемые эллиптические данные, которые размещают данные на полушариях.
Какие структуры мы можем создавать при помощи пространственного типа данных?
Это могут быть точки, точки, объединённые в наборы, линии,
несколько линий, объединённых в наборы, и полигоны.
Как выглядят эти элементы?
Точки.
Точки могут быть использованы для представления каких-то элементов,
не имеющих протяжённости в пространстве.
Например, это могут быть банкоматы, магазины,
остановки общественного транспорта.
Некоторые точки могут быть объединены в наборы точек.
Например, это могут быть остановки общественного транспорта,
характерные для одного маршрута.
Линии используются для представления ломаных линий.
Например, это могут быть улицы города или реки.
Несколько линий могут изображать, например,
маршруты городского транспорта на карте.
Полигон.
Это замкнутая область, имеющая протяжённость,
используется для отображения каких-то областей.
Например, это могут быть леса, поля, здания.
Как хранить эти протяжённые данные и как осуществлять поиск в них?
Какими могут быть запросы к пространственным данным?
Нам может понадобиться найти ближайший магазин, ближайший банкомат,
вычислить расстояние до какого-либо объекта,
если мы в качестве поискового запроса вводим какую-то точку в пространстве.
Или мы можем, наоборот, ввести какую-то область и понять,
какие объекты в нашу область попадают.
До этого мы использовали одномерные способы индексирования.
Сейчас же нам понадобятся пространственные.
Обычно пространственные индексы в СУБД строятся на основе R-дерева.
Как устроено R-дерево?
Основная идея заключается в том,
что вначале мы избавляемся от формы наших объектов.
Как избавиться от формы?
Мы окружаем наш объект минимальным ограничивающим прямоугольником и получаем,
что наш объект описывается уже всего двумя точками: нижней левой и правой верхней,
потому что искать объект, имеющий сложную форму, очень трудно.
И строим индекс по этим ограничивающим прямоугольникам.
Таким образом в индексную структуру попадают пары.
Это будет указатель на сам объект и ограничивающий объект — прямоугольник.
Давайте посмотрим на экране, как мы ограничили пространственные объекты
минимальным ограничивающим прямоугольником.
Мы видим, что при этом у нас может возникать ситуация,
когда одни объекты накладываются на другой.
Конечно, это создаёт определённые сложности при поиске.
На этом примере мы видим, каким образом мы избавляемся от формы, как мы ограничиваем
сложные протяжённые объекты минимальным ограничивающим прямоугольником.
Эти объекты могут пересекаться.
Как мы будем искать информацию?
Мы должны задавать запрос также либо в виде точки, либо в виде прямоугольника.
Мы хотим найти объекты, содержащие искомый образ.
Индекс для R-дерева может содержать множество прямоугольников.
Когда прямоугольники перестают помещаться в одном блоке, я имею в виду
индексные прямоугольники, то нам придётся делить индексный блок пополам.
Как происходит деление?
Мы рассматриваем все прямоугольники, попавшие в эту область,
мы берём для начала два наиболее удалённых друг от друга элемента и пытаемся
присоединить другие прямоугольники к одному или к другому,
и руководствуемся в выборе следующим критерием: мы смотрим,
какова будет площадь перекрытия вновь образующихся прямоугольников, каков
будет их периметр и каковы будут площади пустот, которые образуются при этом.
Таким образом, мы наращиваем R-дерево, структура будет похожа на B-дерево,
только мы будем делить уже протяжённые объекты, а не одномерные.
Давайте рассмотрим на примере,
как создать в среде MySQL таблицу с геометрическими объектами.
Мы создаём таблицу, которая будет содержать
идентификатор с автонумерацией и одно поле для хранения геометрических данных.
К этой таблице мы создаём также пространственный индекс,
который называется SPATIAL.
Проверим, что всё создалось.
Используем команду DESCRIBE, опишем нашу таблицу.
Результат вы можете увидеть на экране.
Разместим данные в эту таблицу.
Мы поместим в неё для примера пять точек, две ломаных линии и два полигона,
то есть площади, ограниченные многоугольниками.
Площадь нашего запроса сейчас изображена на слайде пунктирной линией.
Мы будем искать фигуры, которые попадают в выделенную пунктиром область.
На экране вы видите команды,
которые позволяют добавить точки с геометрическими данными.
Обратите внимание, что координаты точек не разделяются запятыми,
а разделены просто пробелами.
Вот мы видим, что наши объекты добавлены в таблицу.
Посмотрим, как выглядят наши геометрические объекты,
сделаем выборку из нашей таблицы.
И мы видим описания всех фигур и их координаты.
Теперь сделаем выборку значений из заданной области.
Мы определяем искомую область двумя точками: левой нижней и правой верхней.
И результат выборки мы видим на экране, что были найдены объекты,
которые попадают в искомую область.
Это оказалось две точки, одна линия и один полигон.
На этом мы рассмотрели пространственные индексы.
[БЕЗ_ЗВУКА]
