Курс знакомит слушателей с основными принципами работы со структурированными данными в реляционной модели, учит проектировать данные, описывать объекты базы данных в терминах реальной СУБД, составлять запросы на языке SQL, использовать представления, процедуры, функции и триггеры, создавать индексы, управлять конкурентным доступом к данным и манипулировать механизмом транзакций. Основу курса составляют изучение и применение языка SQL для создания, модификации объектов баз данных и управления данными в произвольной реляционной базе данных. Выполнение практических задач в рамках курса предполагает использование СУБД My SQL. В курсе рассматриваются этапы проектирования реляционных баз данных, правила составления запросов, основные методы индексирования данных. В курсе будут изучены вопросы использования транзакций и прав доступа к данным. Также курс дает обзор современных тенденций в области науки о данных в связи с появлением BigData. В заключении курса будут показаны сферы применения NoSQL баз данных и указаны современные подходы к обработке big data.
Индексы на основе битовых шкал и хеширования.
Loading...
From the course by Saint Petersburg State University
Базы данных (Databases)
54 оценки
From the lesson
Оптимизация выполнения запросов.
В этой лекции мы поговорим о дополнительных структурах индексирования – пространственных индексах, индексах на основе хеширования и битовых шкал. Также мы обсудим, каким образом строится план выполнения запросов и как надо писать запросы, чтобы они выполнялись быстрее.
Meet the Instructors
Михайлова Еленадоцент, ИО заведующего кафедрой информационно-аналитических систем СПбГУ
Кафедра информационно-аналитических систем СПбГУ
[МУЗЫКА]
[МУЗЫКА] Рассмотрим дополнительные
возможности для создания индексов, которые предоставляются некоторыми СУБД.
Это индексы на основе хеширования.
Когда мы оценивали скорость поиска при b-индексах,
то он оценивался логарифмом в зависимости от количества узлов индексного дерева.
Есть структуры, которые позволяют производить более быстрый поиск.
Как раз индексы на основе хеширования обеспечивают поиск быстрее.
На чем он основан?
Мы подбираем функцию хеширования, которую можно перевести как функцию перемешивания,
которая распределяет записи таблицы по определенным участкам.
То есть мы выбираем столбец, по которому мы производим индексирование,
и для каждого значения столбца наша функция должна вырабатывать значения,
соответствующие номеру участка.
Можно проиллюстрировать, если вспомнить наши старые бумажные записные книжки.
Нашим ключом, по которому мы распределяли записи записной книжки,
были фамилии и имена людей.
Мы брали от них первую буковку и распределяли человека на определенную
страничку.
Таким образом, функция хеширования брала просто от строки первую букву.
Конечно, функции хеширования могут быть другими, достаточно сложными.
Нам понадобится таблица участков,
которая будет храниться в оперативной памяти, обычно она небольшая.
И, таким образом,
при такой структуре доступ к данным возможен за одно обращение к диску.
На экране вы видите пример создания индекса на основе хеширования.
Мы указываем тип индекса USING HASH.
Проиллюстрируем это на примере нашей таблицы.
Будем строить индекс на основе хеширования для студентов,
и в качестве ключа мы используем идентификатор студента.
Функцию хеширования возьмем как деление числа на 5,
и мы будем брать остаток от этого деления,
То есть мы распределим все данные нашей таблицы по пяти участкам.
На этом слайде вы видите, как распределились строки таблицы.
В четыре блока попало по одной записи, а в одном участке оказалось две.
Кажется, что такой удобный метод,
но почему-то он не получил большого распространения.
Почему?
Потому что у такого метода индексирования есть некоторые недостатки.
Очень трудно подобрать функцию перемешивания,
которая бы абсолютно равномерно размещала данные по участкам, особенно если мы
заранее не знаем всё пространство ключей, которое будет у наших данных.
А если в какой-то участок попадает больше записей, чем в другой,
то у нас возникают переполнения, приходится выделять дополнительные блоки.
Можно вспомнить нашу записную книжку.
Наверное, на какие-то буквы у вас было много знакомых,
а какие-то буквы оставались пустыми совсем.
Таким образом, основная проблема, которую вызывают индексы на основе хеширования,
это неравномерность размещения записей и возникновение коллизий,
которыми мы называем переполнение участков.
На примере вы видите, что в какой-то участок может попасть
небольшое количество записей, а какие-то участки будут состоять из цепочки блоков.
В таком случае преимущества метода теряются,
и доступ за одно обращение к диску мы не получаем.
Следующий индекс, который мы рассмотрим, это индексы на основе битовых карт.
В MySQL они не поддерживаются, но зато встречаются в других СУБД.
Эти индексы подходят для столбцов с низкой избирательностью.
Они очень быстро создаются, занимают мало места и,
может быть, очень удобные для быстрого поиска записи,
поэтому обязательно хотелось рассказать вам об этой структуре.
Как строится индекс на основе битовых карт?
В индекс входит: для каждого значения индексируемого столбца
создается специальная битовая строка,
в которой количество битов соответствует количеству строк таблицы.
Биты, соответственно, могут быть либо нулем, либо единицей, в зависимости от
того, принимает ли столбец в этой строке соответствующее значение или не принимает.
Давайте рассмотрим на примере.
У нас есть таблица девушек.
Первый столбец соответствует их именам,
второй столбец — это цвет глаз, цвет волос и рост.
Мы видим, что значение столбцов цвет волос, рост и цвет
глаз имеет ограниченный спектр значений, то есть ограниченную избирательность.
Для этих столбцов мы можем построить индекс на основе битовых карт.
Рассмотрим индекс на примере роста.
Всего у нас может быть три варианта роста: это высокий, средний и ниже среднего.
И для каждого значения мы составляем строчку из битов,
в которых битик принимает значение единица,
если рост девушки соответствует этому значению параметра.
Можно заметить, что сумма всех строк будет составлять строку из единиц таким образом,
чтобы были покрыты все строки таблицы.
Второй индекс на основе битовых карт построим по цвету волос.
У нас будет четыре строки, соответствующие блондинкам, шатенкам,
брюнеткам и рыжеволосым девушкам.
Индексы на основе битовых карт очень удобны для многокритериального поиска.
Приведем пример запроса.
Ищем блондинку среднего роста.
Мы берем строчку, которая соответствует блондинкам, берем строчку другого индекса,
который соответствует среднему росту, и производим побитовое умножение.
Мы видим, что в результате у нас получаются три единички.
Таким образом, нашему запросу соответствуют три девушки, это Аня,
Даша и Марина.
Что делать, если у нас появляется новое значение столбца?
Например, у нас появилась девушка с голубыми волосами.
Как тогда изменять структуру индекса?
В таком случае в структуру индекса должна будет добавиться новая строчка,
соответствующая новому значению индексного поля.
Она создается из нулей для всех строк, кроме последней.
В последней строке будет единичка.
Другие строки индекса можем дополнить нулями,
а можем просто хранить количество записей и считать,
что если запись индексной строки короче, то она должна быть дополнена нулями.
Индексы на основе битовых карт очень удобны для поиска по нескольким
столбцам с низкой избирательностью.
На этом мы закончили с вами рассмотрение индексных структур.
[БЕЗ_ЗВУКА]
Ознакомьтесь с нашим каталогом
Присоединяйтесь бесплатно и получайте персонализированные рекомендации, обновления и предложения.
Coursera делает лучшее в мире образование доступным каждому, предлагая онлайн-курсы от ведущих университетов и организаций.
© Coursera Inc., 2018 Все права защищены.
