Внутренние структуры хранения

Организация доступа к данным Наличие двух уровней системы для организации доступа к данным Поддержка отношений-каталогов Регулярность структуры данных 2

Схема обработки запроса 3

Уровень СУБД 4

Уровень ОС 5

Временные характеристики Наиболее распространенное время доступа к дисковой памяти – от 3 до 9 миллисекунд Время обращения к оперативной памяти – 100 нанасекунд (Данные из книги: Т. Кормен и др. Алгоритмы. Построение и анализ, 2-е издание. : Пер. с англ. – М.: Издательский дом «Вильямс», 2005) 6

Каталоги Обычные отношения РМД Содержат информацию, связанную с объектами базы данных Примеры: SELECT * FROM T INSERT INTO T VALUES (e 1, e 2, … ) 7

Структура файлов базы данных Основной объект базы данных – таблица; совокупность строк Дополнительные управляющие структуры – индексы Управляющая (служебная) информация – для удовлетворения внутренних потребностей нижнего уровня системы 8

Способы извлечения данных Последовательная выборка SELECT * FROM таблица Произвольная выборка SELECT * FROM таблица WHERE ключ = значение 9

Методы доступа к данным Последовательный метод доступа: для получения целевой записи – обращение ко всем предшествующим цели записям Произвольный метод доступа: для получения целевой записи – непосредственное обращение к ней Специальные объекты – индексы 10

Бинарные деревья поиска Упорядоченная тройка (T L, R, T R ) R – корень дерева T L, T R – левое и правое поддеревья корня R; двоичные деревья N L, N R – количество узлов в поддеревьях, N L 0, N R 0 Общее количество узлов в дереве NR = N L + N R

Структура узла дерева Значение узла – ключ и некоторая запись RowId Левый и правый указатели на поддеревья Длина поиска – длина пути от корня до целевой записи 12

Примеры бинарных деревьев 13

Удаление из бинарного дерева 14

Многоходовые деревья Каждый узел дерева содержит N ключей и, соответственно, N + 1 указатель на подчиненные узлы Ключи в узле упорядочены по возрастанию: K 1 < K 2 < … < K N Ключи в поддеревьях упорядочены по такому же принципу, как и в бинарном дереве 15

Узел дерева P 0 K 1 P 1 K 2 P 2 … P N-1 K N P N { K(P i -1)} < K i < {K(P i )},... KNKN K2K2 K1K1 P0P0 P1P1 P2P2 P N–1 PNPN 16

Пример многоходового дерева 17

В-дерево Сбалансированное многоходовое дерево. Узлы В-дерева могут иметь свободное пространство, что упрощает операции вставки и удаления а) от слова Balanced – сбалансированное дерево, в котором все листья имеют один и тот же уровень б) от Bayer – автора данной структуры 18

В-дерево степени n (1) 1. Все пути от корня до любых листьев имеют одинаковую длину h, называемую также высотой В-дерева. 2. В каждом узле дерева, за исключением корня, должно располагаться минимум n, максимум 2n ключей. 19

В-дерево степени n (2) 3. В корне В-дерева может располагаться минимум 1, максимум 2n ключей. 4. Любой узел дерева, за исключением листьев, имеющий j ключей (n j 2n, для корня 1 j 2n), должен иметь j+1 подчиненный узел 20

Структура узла В-дерева P 0 R 1 P 1 R 2 P 2 … P k-1 R k P k P 0, P 1, P 2, …, P k – указатели на подчиненные узлы R 1, R 2, …, R k – записи (ключ и RowID) 21

Правила следования 1. Ключи записей в текущем узле упорядочены по возрастанию 2. Записи в узле P 0 имеют ключи, меньшие, чем ключ записи R 1 3. Записи в узле P k имеют ключи, большие, чем ключ записи R k 4. Записи в узле P j, 1 j k – 1, имеют ключи, большие, чем ключ записи R j, и меньшие, чем ключ записи R j

Примеры В-деревьев 23

Вставка в В-дерево (1) Вставка – только в лист В-дерева Ситуации: 1. Целевой лист не заполнен 24

Вставка в В-дерево (2) 2. Целевой лист заполнен полностью – расщепление листа 25

Пример: вставка в В-дерево степени 1 (1) Вставляется последовательность ключей 20, 12, 48, 3, 5, 70, 101 3) ) 202) 12 26

Пример: вставка в В-дерево степени 1 (2) 4) 3 5)

Пример: вставка в В-дерево степени 1 (3) 6) 70 7)

Пример: вставка в В-дерево степени 1 (4) 7)

Удаление ключа Удаляемый ключ находится в листе дерева Удаляемый ключ находится в промежуточном узле дерева –замещается следующим за ним элементом (минимальный ключ из правого поддерева) –замещается предшествующим ему элементом (максимальный ключ из левого поддерева) 30

Нормальная ситуация В целевом листе находится более чем n элементов (n – степень В-дерева) Пример: фрагмент В-дерева степени 2; удаляется ключ

Антипереполнение листа В целевом листе находится только n ключей – минимально допустимое количество При удалении ключа нарушается свойство В-дерева 1.Перераспределение ключей 2.Слияние узлов 32

Перераспределение ключей (1) Соседний лист, подчиненный тому же ключу, что и целевой, содержит n + m + 1 ключ, m 0 Общее количество ключей: (n – 1) (n + m + 1) = 2n m, m 0 Перераспределение: (n + d) (n + m – d), d 0 33

Перераспределение ключей (2) Пример: фрагмент В-дерева степени 3; удаляется ключ , 196, 201, 210, 211, 253, 255,

Слияние листьев (1) Соседние листья содержат только по n ключей Общее количество ключей: (n – 1) n = 2n Удаляется один из листьев Удаляется ключ из родительского узла 35

Слияние листьев (2) Пример: фрагмент В-дерева степени 2; удаляется ключ

Пример: В-дерево степени 1 Удаляется ключ

Основные свойства В-дерева 1.Ключи и ассоциированные с ними данные (RowID) хранятся во всех узлах В-дерева 2.Произвольная выборка данных выполняется эффективно 3.Последовательная выборка данных мало эффективна 38

В+ дерево (1) Два типа узлов В+ дерева: внутренние узлы – представляют собой В-дерево индексов; содержат только ключи листья – объединены в двухсвязный список; содержат все ключи и ассоциированные с ними данные (RowID) 39

В+ дерево (2) Внутренние узлы – индексы Листья... 40

Вставка в В+ дерево Аналогично В-дереву, за исключением расщепления листа: медианный ключ перемещается в родительский узел и остается в листе (правом или левом) k0k0 k1k1 …k j-1 kjkj …k 2n …… kjkj 41

Пример: вставка в В+ дерево степени 1 (1) Вставляется последовательность ключей 20, 12, 48, 3, 5, 70, 101 3) ) 202)

Пример: вставка в В+ дерево степени 1 (2) 4) 3 5)

Пример: вставка в В+ дерево степени 1 (3) 6)

Пример: вставка в В+ дерево степени 1 (4) 6) 70 7)

Пример: вставка в В+ дерево степени 1 (5) 7)

Удаление из В+ дерева Только из листьев Пример: В+ дерево степени 2; удаляется ключ

Антипереполнение: перераспределение Удаляется 39; перераспределение ключей (ключ 31 удаляется)

Антипереполнение: слияние Удаляется 39; слияние листьев (ключ 31 удаляется)

Хэш индексы Для произвольного доступа к данным Строится на уникальных атрибутах Хэш функция отображает индекс в физический адрес хранения соответствующей строки таблицы Принцип отображения – m : 1 50

Организация хранения таблицы 01N Бакеты (buckets) 51

Идея хеширования (1) hash бакет Первичная область Область переполнения Ключи 52

Идея хеширования (2) Для k 1 k 2 hash(k 1 ) = hash(k 2 ) k 1, k 2 – синонимы Разрешение коллизий: выявление свободного пространства в бакете обработка переполнения бакета 53

Метод открытой адресации бакет Первичная область + область переполнения Бакет А Бакет В 54

Метод срастающихся цепочек Указатель на свободное пространство Бакет А Бакет В 55

Метод раздельных цепочек Первичная область Область переполнения Бакет А Бакет В 56

Сравнение методов индексирования (1) В+ деревья представляются объектами базы данных не влияют на представление таблицы упорядоченное хранение строк таблицы определены и операции для сравнения ключей Хеш индексы не представляются объектами базы данных влияют на представление таблицы упорядоченность строк отсутствует определены только операции = и для ключей 57

Сравнение методов индексирования (2) В+ деревья пространство для таблицы выделяется по мере вставки строк могут создаваться на ключевых и не ключевых атрибутах используются всеми СУБД Хеш индексы пространство для таблицы выделяется при создании таблицы должны создаваться только на ключевых атрибутах используются не всеми СУБД 58

Рекомендации Если размер таблицы сильно изменяется – не хэш таблица Если часто организуется поиск по критериям – не хэш таблица Если используются справочники (мало изменяемые таблицы, поиск в них по =) – хэш таблицы 59

Пример создания хеш таблицы (1) Создание кластерного хеш-индекса (Oracle) CREATE CLUSTER HD ( DID NUMBER (5,0) SIZE 1K -- размер строк с одним и тем же значением индекса HASH IS DID -- на каком атрибуте создается хеш-индекс HASHKEYS число различных значений хеш индекса ) 60

Пример создания хеш таблицы (2) Создание хеш-таблицы (Oracle) CREATE TABLE Tab ( MDID NUMBER (5) NOT NULL PRIMARY KEY, другие колонки таблицы ) CLUSTER HD(MDID) -- на каком хеш-индексе строится таблица 61