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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

19 Принципы построения БД Тема 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

20 Принципы построения БД Тема 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 может иметь цеп.переполнения ! вставка

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

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

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

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

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

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

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

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

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

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

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

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

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

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

35 Принципы построения БД Тема 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

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

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

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

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

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

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

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

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

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

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

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

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

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

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