Виды индексов:

Содержание

Слайд 2

Индексы в СУБД

Индексы в СУБД

Слайд 3

Поиск с использованием индекса SELECT * FROM customers WHERE email_address='vassya@spbu.ru' +

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

SELECT * FROM customers WHERE email_address='vassya@spbu.ru' +
SELECT *

FROM customers WHERE email_address > 'v' +
SELECT * FROM customers WHERE email_address LIKE 'vassya' +
SELECT * FROM customers WHERE email_address LIKE '%@spbu.ru' -
Слайд 4

Reverse index SELECT email_address FROM customers WHERE email_address LIKE '%@yahoo.com'. CREATE

Reverse index

SELECT email_address FROM customers WHERE email_address LIKE '%@yahoo.com'.
CREATE INDEX test_indexi

ON customers (email_address) REVERSE;
SELECT email_address FROM customers WHERE reverse(email_address) LIKE reverse('%@yahoo.com'); (moc.oohay@%)
Слайд 5

Reverse index Reverse index – это тоже B-tree индекс но с

Reverse index

Reverse index – это тоже B-tree индекс но с реверсированным

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

Reverse index

Reverse index

Слайд 7

Поиск документов по содержащимся в них словам WHERE Field1 like ‘алгоритм%’

Поиск документов по содержащимся в них словам

WHERE Field1 like ‘алгоритм%’ Использует индекс
WHERE

Field1 like ‘%алгоритм%’ Полное сканирование таблицы
Слайд 8

Inverted index Документ (текстовое поле) – это последовательность слов D1: w1

Inverted index

Документ (текстовое поле) – это последовательность слов
D1: w1 w2 w3

w1 w4 w2
D2: w1 w7 w8 w9 w5
D3: w1 w7 w3 w2 w8
Слайд 9

Поиск документов по содержащимся в них словам W1: d1 d2 d3

Поиск документов по содержащимся в них словам

W1: d1 d2 d3
W2: d1

d3
W3: d1
W5: d2
Слайд 10

Для FULL TEXT индекса Выбрать столбцы таблицы или индексированного представления Построить

Для FULL TEXT индекса

Выбрать столбцы таблицы или индексированного представления
Построить для таблицы

индекс по одному полю, которое не позволяет дубликатов и нулевых значений
Построить каталог
А потом уже строить полнотекстовый индекс…
Слайд 11

Полнотекстовый индекс FULLTEXT В полнотекстовый индекс включается один или несколько символьных

Полнотекстовый индекс FULLTEXT

В полнотекстовый индекс включается один или несколько символьных столбцов

в таблице.
Эти столбцы могут иметь тип данных:
char, varchar, nchar, nvarchar, text, ntext, image, xml и varbinary(max).
Каждому столбцу может соответствовать определенный язык (из 50-ти возможных).
Английский 1033,
Русский 1049.
Слайд 12

Процесс индексирования Создание полнотекстового каталога Создание полнотекстового индекса Заполнение полнотекстового индекса

Процесс индексирования

Создание полнотекстового каталога
Создание полнотекстового индекса
Заполнение полнотекстового индекса

Слайд 13

Создание каталога CREATE FULLTEXT CATALOG catalog_name Полнотекстовый каталог — это логическое понятие, обозначающее группу полнотекстовых индексов.

Создание каталога

CREATE FULLTEXT CATALOG catalog_name
Полнотекстовый каталог — это логическое понятие, обозначающее

группу полнотекстовых индексов.
Слайд 14

Создание полнотекстового каталога Полнотекстовый каталог — это логическое понятие, обозначающее группу

Создание полнотекстового каталога

Полнотекстовый каталог — это логическое понятие, обозначающее группу полнотекстовых

индексов.
CREATE FULLTEXT CATALOG test_catalog
CREATE UNIQUE INDEX ui_1 ON customers (id) индекс с одним уникальным столбцом, NOT NULL
Слайд 15

Создание полнотекстового индекса CREATE FULLTEXT INDEX ON customers (email_address) KEY INDEX ui_1 ON test_catalog

Создание полнотекстового индекса

CREATE FULLTEXT INDEX ON customers (email_address) KEY INDEX ui_1 ON

test_catalog
Слайд 16

Создание FULL TEXT индекса CREATE FULLTEXT INDEX ON table_name [ (

Создание FULL TEXT индекса

CREATE FULLTEXT INDEX ON table_name
[ ( {

column_name
[ TYPE COLUMN type_column_name ]
[ LANGUAGE language_term ]
[ STATISTICAL_SEMANTICS ]
} [ ,...n]
) ]
KEY INDEX index_name
Слайд 17

Создание полнотекстового индекса CREATE FULLTEXT INDEX ON customers ( email_address language

Создание полнотекстового индекса

CREATE FULLTEXT INDEX ON customers ( email_address language 1033 , cust_name

language 1049) KEY INDEX ui_1 ON test_catalog WITH CHANGE_TRACKING MANUAL|AUTO , STOPLIST = OFF|SYSTEM|My_stop_list
Слайд 18

Полнотекстовый индекс

Полнотекстовый индекс

Слайд 19

Процесс полнотекстового индексирования Фильтрацию, разбиение по словам Удаление стоп-слов и нормализация

Процесс полнотекстового индексирования

Фильтрацию, разбиение по словам
Удаление стоп-слов и нормализация токенов
Преобразует

конвертированные данные в инвертированный список слов
Заполнение полнотекстового индекса.
Слайд 20

Заполнение индекса значениями (обновление) MANUAL – вручную ALTER FULLTEXT INDEX ON

Заполнение индекса значениями (обновление)

MANUAL – вручную ALTER FULLTEXT INDEX ON customers START FULL POPULATION
AUTO автоматически, но

это не значит, что они будут немедленно отражаться в полнотекстовом индексе.
Слайд 21

Список стоп-слов По умолчанию индекс сопоставляется с системным стоп-листом “system”, по

Список стоп-слов

По умолчанию индекс сопоставляется с системным стоп-листом “system”, по этому

стоп-листу не будут находиться , например, числовые значение(раз, два и т.д.)
alter fulltext index on MyTable1 set stoplist= myStoplist
Слайд 22

Список стоп-слов CREATE FULLTEXT STOPLIST myStoplist [FROM SYSTEM STOPLIST]; ALTER FULLTEXT

Список стоп-слов

CREATE FULLTEXT STOPLIST myStoplist [FROM SYSTEM STOPLIST];
ALTER FULLTEXT STOPLIST MyStoplist

ADD 'en' LANGUAGE 'Spanish';
ALTER FULLTEXT STOPLIST MyStoplist ADD 'en' LANGUAGE 'French';
Слайд 23

Обработка полнотекстовых запросов разбиение по словам расширение тезауруса морфологический поиск обработка стоп-слов поиск в индексе ранжирование

Обработка полнотекстовых запросов

разбиение по словам
расширение тезауруса
морфологический поиск
обработка стоп-слов
поиск в индексе
ранжирование

Слайд 24

Поиск в полнотекстовом индексе В полнотекстовых запросах не учитывается регистр букв.

Поиск в полнотекстовом индексе

В полнотекстовых запросах не учитывается регистр букв.
Все

полнотекстовые запросы используют предикаты (CONTAINS и FREETEXT) и функции (CONTAINSTABLE и FREETEXTTABLE)
Слайд 25

Запросы с полнотекстовым индексом: Самый простой способ – это использование freetext

Запросы с полнотекстовым индексом:

Самый простой способ – это использование freetext и

CONTAINS
select * from Production.ProductDescription where freetext(Description,'bike')
select * from Production.ProductDescription where CONTAINS (Description,'bike')
Слайд 26

CONTAINS Предикат, используемый в предложении WHERE для и проверки точного или

CONTAINS

Предикат, используемый в предложении WHERE для и проверки точного или нечеткого

совпадения с отдельными словами, расстояния между словами или взвешенных совпадений.
CONTAINS ( { column_name | * } , 'condition')
слова или фразы;
префикса слова или фразы;
слова около другого слова;
Слайд 27

FREETEXT Этот предикат используется в предложении WHERE для поиска значений, которые

FREETEXT

Этот предикат используется в предложении WHERE для поиска значений, которые соответствуют

условию поиска по смыслу, а не написанию.
FREETEXT ( { column_name | * } , 'string' )
Разбивает строку на отдельные слова
Формирует словоформы.
Определяет список расширений или замен на основании совпадений в тезаурусе.
Слайд 28

Виды запросов Простое выражение. Префиксные выражения. Производное выражение. Выражения с учетом расположения. Синонимы. Взвешенное выражение.

Виды запросов

Простое выражение.
Префиксные выражения.
Производное выражение.
Выражения с учетом расположения.
Синонимы.
Взвешенное выражение.

Слайд 29

Простое выражение Одно или несколько конкретных слов или фраз в одном

Простое выражение

Одно или несколько конкретных слов или фраз в одном или

нескольких столбцах.
{ AND | & } | { AND NOT | &! } | { OR | | }
SELECT Comments FROM ProductReview
WHERE CONTAINS(Comments, 'ужасно');
… CONTAINS(Comments, 'ужасно OR плохо'); …CONTAINS((Absract,Article), 'indexing');
Слайд 30

Префиксные выражения Слова, начинающиеся заданным текстом, или фразы с такими словами.

Префиксные выражения

Слова, начинающиеся заданным текстом, или фразы с такими словами.
… CONTAINS(Comments,

' ужасн*'); … CONTAINS(Comments, ' "ужасн*" '); …CONTAINS(Name, '"chain*" OR "full*"');
…CONTAINS(Name, '"C#" AND NOT "JAVA " '
…CONTAINS(Name, '"C#" AND NOT "JAVA " '
Слайд 31

Префиксные выражения Если параметр является фразой, то каждое содержащееся во фразе

Префиксные выражения

Если параметр является фразой, то каждое содержащееся во фразе слово

считается отдельным префиксом.
"local wine*" => «local winery», «locally wined and dined»
Слайд 32

Выражения с учетом расположения Слова или фразы, находящиеся рядом с другими

Выражения с учетом расположения

Слова или фразы, находящиеся рядом с другими словами

или фразами.
CONTAINS(*,‘NEAR (значение, выражения)‘)
CONTAINS(*,‘NEAR ((значение, выражения),1)‘)
Слайд 33

Выражения с учетом расположения NEAR ( { search_term [ ,…n ]

Выражения с учетом расположения

NEAR ( { search_term [ ,…n ] |(search_term [ ,…n ] ) [, [, ] ]
CONTAINS(column_name, 'NEAR

((Monday,, Wednesday), MAX, TRUE)')
CONTAINS(column_name, 'NEAR ((Monday,, Wednesday), 5)')
Слайд 34

FREETEXT Разбивает строку на отдельные слова согласно границам слов (пословное разбиение).

FREETEXT

Разбивает строку на отдельные слова согласно границам слов (пословное разбиение).
Формирует словоформы

(а также производит выделение основы слова).
Определяет список расширений или замен для термов на основании совпадений в тезаурусе.
Слайд 35

FREETEXT Словоформы конкретного слова. Синонимические формы конкретного слова. SELECT * FROM t3 WHERE freetext(s,'рама')

FREETEXT

Словоформы конкретного слова.
Синонимические формы конкретного слова.
SELECT * FROM t3 WHERE freetext(s,'рама')

Слайд 36

Взвешенное выражение Слова или фразы со взвешенными значениями () SELECT *

Взвешенное выражение

Слова или фразы со взвешенными значениями ()
SELECT * from CONTAINSTABLE

( table3 –имя таблицы , * – имена столбцов для поиска , 'ISABOUT (drive WEIGHT(0.9) , auto WEIGHT(0.1)) ', 10 ) ORDER BY RANK;
Результат: ранжированная таблица (ключ, ранг)
Слайд 37

Полнотекстовый индекс FULLTEXT Загрузка данных в таблицу, уже имеющую индекс FULLTEXT, будет более медленной.

Полнотекстовый индекс FULLTEXT

Загрузка данных в таблицу, уже имеющую индекс FULLTEXT,

будет более медленной.
Слайд 38

Индексы на основе битовых карт Подходят для столбцов с низкой избирательностью.

Индексы на основе битовых карт

Подходят для столбцов с низкой избирательностью.
Создаются быстро.
Занимают

мало места.
Размер индекса на основе битовых карт существенно зависит от распределения данных.
Слайд 39

Индексы на основе битовых карт create bitmap index ind_4 on table_1(field1)

Индексы на основе битовых карт

create bitmap index ind_4 on table_1(field1)
В индекс

входят:
Для каждого значения индексируемого столбца – одна строка, состоящая из значения столбца и битовой последовательности
битовая последовательность имеет длину по количеству строк таблицы, в которой 1 означает, что в данной строке атрибут принимает заданное значение
Слайд 40

Индексы на основе битовых карт

Индексы на основе битовых карт

Слайд 41

create bitmap index ind_4 on table_1(рост): Высокий 0010001000 Средний 1101110100 Ниже среднего 0000000011

create bitmap index ind_4 on table_1(рост):

Высокий 0010001000
Средний 1101110100
Ниже среднего 0000000011

Слайд 42

create bitmap index ind_5 on table_1(Цвет волос): Блондинка 1100010000 Шатенка 0010000100 Брюнетка 0000101001 Рыжая 0001000010

create bitmap index ind_5 on table_1(Цвет волос):

Блондинка 1100010000
Шатенка 0010000100
Брюнетка 0000101001
Рыжая 0001000010

Слайд 43

Блондинка среднего роста: Блондинка 1100010000 Средний 1101110100 Побитовое умножение 1100010000

Блондинка среднего роста:

Блондинка 1100010000
Средний 1101110100
Побитовое умножение 1100010000

Слайд 44

Появилась Мальвина: Блондинка 1100010000 Шатенка 0010000100 Брюнетка 0000101001 Рыжая 0001000010 Голубые волосы 00000000001

Появилась Мальвина:

Блондинка 1100010000
Шатенка 0010000100
Брюнетка 0000101001
Рыжая 0001000010
Голубые волосы 00000000001

Слайд 45

Индексы на основе битовых карт Индексы на основе битовых карт обычно

Индексы на основе битовых карт

Индексы на основе битовых карт обычно выбираются

стоимостным оптимизатором, если для выполнения запроса можно использовать несколько таких индексов.
Изменения столбцов, входящих в индексы на основе битовых карт, а также вставки и удаления данных могут вызывать существенные конфликты блокировок.
Изменения столбцов, входящих в индексы на основе битовых карт, а также вставки и удаления данных могут весьма существенно "ухудшать" индексы.
Слайд 46

Hash-индекс Выбираем количество участков, в которых будем размещать записи. Подбираем функцию

Hash-индекс

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

от ключевого столбца будет выдавать номер участка.
В памяти храним таблицу адресов участков
Слайд 47

Создание hash-индекса CREATE INDEX имя_индекса USING HASH ON имя_таблицы (имя_столбца)

Создание hash-индекса

CREATE INDEX имя_индекса USING HASH ON имя_таблицы (имя_столбца)

Слайд 48

Слайд 49

Hash-индекс Для размещения таблицы отводится заданное количество участков Есть функция hash(key)=n,

Hash-индекс

Для размещения таблицы отводится заданное количество участков
Есть функция hash(key)=n, где

n – номер участка
В памяти хранится таблица адресов участков
Доступ к данным за одно обращение к диску
Слайд 50

Недостатки hash-индексов Таблица адресов участков может быть слишком велика Если в

Недостатки hash-индексов

Таблица адресов участков может быть слишком велика
Если в один участок

попало слишком много записей, придется выделять дополнительный блок.
Проблема – неравномерность размещения записей, возникновение коллизий
Слайд 51

Коллизии

Коллизии

Слайд 52

Функции Hash Деление Мультипликативный метод

Функции Hash

Деление
Мультипликативный метод

Слайд 53

Функции Hash деление Размер таблицы hashTableSize - простое число. Хеширующее значение

Функции Hash деление

Размер таблицы hashTableSize - простое число.
Хеширующее значение hashValue,

изменяющееся от 0 до (hashTableSize - 1), равно остатку от деления ключа на размер хеш-таблицы.
Увеличиваем число участков в два раза
Слайд 54

Функции Hash мультипликативный метод Размер таблицы hashTableSize есть степень 2n. Значение

Функции Hash мультипликативный метод

Размер таблицы hashTableSize есть степень 2n.
Значение

key умножается на константу, затем от результата берется n бит.
В качестве такой константы Кнут рекомендует золотое сечение (sqrt(5) - 1)/2 = 0.6180339887499.
Слайд 55

Функции Hash для строк переменной длины Аддитивный метод – преобразовываем слова

Функции Hash для строк переменной длины

Аддитивный метод – преобразовываем слова в

числа, складываем и берем остаток деления по модулю 256.
Метод ИЛИ
Слайд 56

Слайд 57

Слайд 58

Пространственные типы данных geometry используется для планарных или евклидовых данных geography,

Пространственные типы данных

 geometry используется для планарных или евклидовых данных
geography, который используется

для хранения эллиптических данных, таких как координаты GPS широты и долготы
Слайд 59

Пространственные типы данных geometry используется для планарных или евклидовых данных geography,

Пространственные типы данных

 geometry используется для планарных или евклидовых данных
geography, который используется

для хранения эллиптических данных, таких как координаты GPS широты и долготы
объекты geography должны помещаться в одном полушарии, расстояние обычно вычисляется в метрах
Слайд 60

Пространственные типы данных Point MultiPoint LineString MultiLineString Polygon

Пространственные типы данных

Point
MultiPoint
LineString
MultiLineString
Polygon

Слайд 61

R-дерево Избавляемся от формы – окружаем фигуру min ограничивающим прямоугольником (oid,

R-дерево

Избавляемся от формы – окружаем фигуру min ограничивающим прямоугольником (oid, Rectangle), oid

– ссылка на запись
Слайд 62

Иерархия R-дерева Окружаем фигуры ограничивающими прямоугольниками (cp, Rectangle) При переполнении делим пополам

Иерархия R-дерева

Окружаем фигуры ограничивающими прямоугольниками
(cp, Rectangle)
При переполнении делим пополам

Слайд 63

R-дерево

R-дерево

Слайд 64

R-дерево - недостатки Не удается избежать перекрытий – необходим просмотр нескольких веток

R-дерево - недостатки

Не удается избежать перекрытий – необходим просмотр нескольких веток

Слайд 65

Критерии разделения узла Минимальная площадь Минимальное перекрытие Минимальные границы

Критерии разделения узла

Минимальная площадь
Минимальное перекрытие
Минимальные границы

Слайд 66

Минимальная площадь

Минимальная площадь

Слайд 67

Минимальное перекрытие

Минимальное перекрытие

Слайд 68

Минимальные границы

Минимальные границы

Слайд 69

Spatial grid

Spatial grid

Слайд 70

Spatial grid CREATE SPATIAL INDEX GEOMETRY_GRID | GEOGRAPHY_GRID BOUNDING_BOX (для GEOMETRY_GRID)

Spatial grid

CREATE SPATIAL INDEX
GEOMETRY_GRID | GEOGRAPHY_GRID
BOUNDING_BOX (для GEOMETRY_GRID) xmin, ymin, xmax, ymax
GRIDS

- плотность сетки на каждом уровне LEVEL_1 - LEVEL_4
Слайд 71

Spatial grid 4 уровня вложенности

Spatial grid

4 уровня вложенности

Слайд 72

Spatial grid CREATE SPATIAL INDEX SIndx ON SpatialTable(geometry_col) WITH ( BOUNDING_BOX

Spatial grid

CREATE SPATIAL INDEX SIndx
ON SpatialTable(geometry_col)
WITH (
BOUNDING_BOX =

( 0, 0, 500, 200 ),
GRIDS = ( LEVEL_4 = HIGH, LEVEL_3=MEDIUM ) );
Слайд 73

Spatial grid

Spatial grid

Слайд 74

Тесселяция Декомпозиция индексированного пространства в cеточную иерархию Считывание данных для пространственного

Тесселяция

Декомпозиция индексированного пространства в cеточную иерархию
Считывание данных для пространственного объекта по

строкам
Вставка объекта в cеточную иерархию (тесселяция)
Устанавливая связь между объектом и набором сеточных ячеек