Принципы построения БД Тема 51 Принципы построения и работы баз данных Тема 05: Хэширование и другие вопросы.

Принципы построения БД Тема 52 key h(key) Хэширование Ячейки (обычно 1 диск.блок )

Принципы построения БД Тема Две возможности записи (1) key h(key)

Принципы построения БД Тема 54 (2) key h(key) Индекс запись ключ Две возможности (2) – для вторичного ключа поиска

Принципы построения БД Тема 55 Пример функции хэширования Ключ = x1 x2 … xn строка символов длиной n байт Пусть имеется m ячеек h: сложить x1 + x2 + ….. хn как целые числа – вычислить сумму по модулю b Это может быть не лучшей хэш-функцией Д.Кнут. Искусство программирования для ЭВМ. Т.3. (Если хотите Узнать как выбрать хорошую хэш-функцию.) Хорошая функция обладает свойством: среднее ожидаемое количество ключей в ячейке одинаково для всех ячеек

Принципы построения БД Тема 56 Внутри ячейки: Нужно ли держать ключи отсортированными? Да, если время обработки процессором критично & Вставки.удаления не слишком часты Далее: Пример для иллюстрации вставок, переполнения, удалений h(key)

Принципы построения БД Тема 57 Пример 2 записи на ячейку Вставка: h(a) = 1 h(b) = 2 h(c) = 1 h(d) = d a c b h(e) = 1 e

Принципы построения БД Тема a b c e d Пример: удаление Удалить: e f f g М.б. перенести g в предыдущий блок c d

Принципы построения БД Тема 59 Главное правило: Использование пространства ячейки от 50% до 80% Использование = число использованных мест общее число мест в ячейке Если < 50%, теряем дисковое пространство Если > 80%, переполнение может быть значительным, зависит от качества хэш-функции и количества ключей в ячейке

Принципы построения БД Тема 510 Как бороться с ростом хэш-таблицы (файла)? Переполнение и реорганизация Динамическое хэширование Расширяемая схема Линейная схема

Принципы построения БД Тема 511 Расширяемая схема: две идеи (a) Использовать j из b битов значения хэш-функции b h(K) исп. j может расти со временем (б) Использование оглавления h(K)[j ] к ячейке

Принципы построения БД Тема 512 Пример: h(k) дает 4 бита; 2 ключа/ячейку j = Вставить Новое оглавление j = 2 2

Принципы построения БД Тема Вставить: j = Продолжение примера

Принципы построения БД Тема i = Вставить: 1001 Продолжение примера j = 3 3

Принципы построения БД Тема 515 Расширяемая схема: удаление Без слияния блоков Слияние блоков и сокращение оглавления если возможно (процедура – обратная вставке) Пример удаления Рассмотрите вставку в обратном порядке

Принципы построения БД Тема 516 Расширяемая схема Справляется с растущими файлами - с меньшей потерей пространства - без полной реорганизации Итог + Косвенная адресация (хорошо если оглавление в памяти) Оглавление увеличивается в 2 раза (То умещается, то нет) - -

Принципы построения БД Тема 517 Линейная схема Другая динамическая схема Две идеи: (a) Использование младших j битов значения хэш-функции растет b j (б) Файл растет линейно (в) Пороговое значение U = число записей

Принципы построения БД Тема 518 Пример b=4 bits, j =1, 2 ключа/ячейку m = 01 (max номер блока) Если h(k)[j ] m, то проверять ячейку h(k)[ j ], иначе проверять ячейку h(k)[j ] - 2 j -1 Правило вставка

Принципы построения БД Тема 519 Пример b=4 bits, j =2, 2 ключа/ячейку m = 01 (max номер блока) 10 Ячейки для будущего роста Если h(k)[j ] m, то проверять ячейку h(k)[ j ] иначе проверять ячейку h(k)[j ] - 2 j -1 Правило 1010

Принципы построения БД Тема 520 Пример b=4 bits, j =2, 2 ключа/ячейку m = 01 (max номер блока) 10 Ячейки для будущего роста Если h(k)[j ] m, то проверять ячейку h(k)[ j ], иначе проверять ячейку h(k)[j ] - 2 j -1 Правило 0101 может иметь цеп.переполнения ! вставка

Принципы построения БД Тема 521 Пример b=4 bits, j =2, 2 ключа/ячейку m = 01 (max номер блока) Ячейки для будущего роста вставка

Принципы построения БД Тема 522 Продолжение примера: Как расти дальше ? m = 11 (max номер блока) j =

Принципы построения БД Тема 523 Если U > порогового значения, то увеличить m (и может быть j ) Когда расширяется файл? Следите за: кол-во записей общее кол-во ячеек = U

Принципы построения БД Тема 524 Линейная схема Справляется с растущими файлами - с меньшей потерей пространства - без полной реорганизации Нет необходимости в косвенной адресации Итог + + Может иметь цепочки переполнения -

Принципы построения БД Тема 525 Пример: «Плохой» частный случай Очень полная ячейка Очень пустыеНужно увел. m … Приведет к потере пространства...

Принципы построения БД Тема 526 Далее: Сравнение индексирования и хэширования Определение индекса в SQL Доступ с использованием нескольких ключей

Принципы построения БД Тема 527 Хеширование хорошо для выбора записей с заданным значением ключа, например SELECT … FROM R WHERE R.A = 5 Индексирование (включая B-Trees) хорошо для поиска записей со значениями из (полу-) интервала SELECT... FROM R WHERE R.A > 5 Сравнение индексирования и хэширования

Принципы построения БД Тема 528 Определение индекса в SQL CREATE INDEX имя_индекса ON rel (attr) CREATE UNIQUE INDEX имя_индекса ON rel(attr) Определяет возможный ключ отношения DROP INDEX имя_индекса

Принципы построения БД Тема 529 Нельзя задать тип индекса ( например, B-tree, хэширование, …) или параметры (заполненность, размер хэш-таблицы,...) По крайней мере стандарт SQL этого не позволяет... Замечания Можно задавать список атрибутов в качестве ключа многомерный индекс CREATE INDEX имя_индекса ON R(A,B,C)

Принципы построения БД Тема 530 Мотивация: Найти все записи, у которых DEPT = Toy AND SAL > 50k Стратегия 1: Использовать один индекс, например Dept. Получить все записи с Dept = Toy и проверить зарплату Многомерный индекс I1I1

Принципы построения БД Тема 531 ToySal > 50k Стратегия 2: Использовать 2 индекса; манипулировать указателями Стратегия 3: Многомерный индекс I1I1 I2I2 I2I2

Принципы построения БД Тема 532 Пример записи Dept индекс Salary индекс Name=Joe DEPT=Sales SAL=15k Art Sales Toy 10k 15k 17k 21k 12k 15k 19k

Принципы построения БД Тема 533 Для каких запросов хорош этот индекс? Найти записи с Dept = Sales & SAL=20k Найти записи с Dept = Sales & SAL > 20k Найти записи с Dept = Sales Найти записи с SAL = 20k

Принципы построения БД Тема 534 Интересное приложение: Географические(пространственные) данные Данные : x y... Запросы: Какой город находится в ? Что находится в 5 милях от ? Что ближе всех к ?

Принципы построения БД Тема 535 h n b i a c o d Пример e g f m l k j h i a b c d e f g n o m l j k Поиск точек близких к f Поиск точек близких к b 5 15

Принципы построения БД Тема 536 Запросы Найти точки с Yi > 20 Найти точки с Xi < 5 Найти точкиблизкие к i = Найти точкиблизкие к b = Используется несколько типов географических индексов Q деревья R деревья

Принципы построения БД Тема 537 Еще два типа многомерных индексов Сеточный файл(индекс) Хэш-разбиение Сеточный индекс Key 2 X1 X2 …… Xn V1 V2 Key 1 Vn К записи с ключом key1=V3, key2=X2

Принципы построения БД Тема 538 Утверждение Может быстро находить записи с –ключ 1 = V i & ключ 2 = X j –ключ 1 = V i –ключ 2 = X j А также записи с ключами из диапазона. –ключ 1 V i & ключ 2 < X j

Принципы построения БД Тема 539 Имеется загвоздка в сеточном индексе! Как сеточный индекс хранится на диске? Как массив X1X2X3X4X1X2X3X4X1X2X3X4 V1V2V3 Проблема: Необходима регулярность данных для вычисления позиции элемента

Принципы построения БД Тема 540 Решение: Использовать косвенную адресацию Ячейки V1 V2 V3 *сетка V4 содержит указатели на ячейки Ячейки -- X1 X2 X3

Принципы построения БД Тема 541 При косвенной адресации: Сетка может быть регулярной без потери пространства Однако необходима дополнительные затраты на обработку косвенной адресации

Принципы построения БД Тема 542 Можно индексировать сетку по интервалам ЗарплатаСетка Линейная шкала 123 ToySalesPersonnel 0-20K1 20K-50K2 50K-3 8

Принципы построения БД Тема 543 Сеточные файлы Удобны для поиска по многомерному ключу Дополнительные затраты памяти и обработки (нет ничего бесплатного) Нуждается в равномерном разбиении значений ключей + - -

Принципы построения БД Тема 544 Идея: ключ1 ключ2 Хэш-разбиение h1h

Принципы построения БД Тема 545 h1(toy)=0000 h1(sales)=1001 h1(art)= h2(10k)=01100 h2(20k)=11101 h2(30k)=01110 h2(40k)=00111., Пример: Вставка

Принципы построения БД Тема 546 h1(toy)=0000 h1(sales)=1001 h1(art)= h2(10k)=01100 h2(20k)=11101 h2(30k)=01110 h2(40k)= Найти служащих с Dept. = Sales & Sal=40k

Принципы построения БД Тема 547 h1(toy)=0000 h1(sales)=1001 h1(art)= h2(10k)=01100 h2(20k)=11101 h2(30k)=01110 h2(40k)= Найти служащих с Sal=30k Искать здесь

Принципы построения БД Тема 548 h1(toy)=0000 h1(sales)=1001 h1(art)= h2(10k)=01100 h2(20k)=11101 h2(30k)=01110 h2(40k)= Найти служ. с Dept. = Sales Искать здесь

Принципы построения БД Тема Индексирование против хэширокания - Определение индексов в SQL - Доступ при многомерном ключе - многомерный индекс Вариации: Сетка, Географические данные - Хэш-разбиение Итоги