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


The Presentation inside:

Slide 0

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


Slide 1

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


Slide 2

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


Slide 3

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


Slide 4

Уровень ОС 5


Slide 5

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


Slide 6

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


Slide 7

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


Slide 8

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


Slide 9

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


Slide 10

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


Slide 11

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


Slide 12

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


Slide 13

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


Slide 14

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


Slide 15

Узел дерева P0 K1 P1 K2 P2 … PN-1 KN PN { K(Pi-1)} < Ki < {K(Pi)}, . . . KN K2 K1 P0 P1 P2 PN–1 PN 16


Slide 16

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


Slide 17

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


Slide 18

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


Slide 19

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


Slide 20

Структура узла В-дерева P0 R1 P1 R2 P2 … Pk-1 Rk Pk P0, P1, P2, …, Pk – указатели на подчиненные узлы R1, R2, …, Rk – записи (ключ и RowID) 21


Slide 21

Правила следования 1. Ключи записей в текущем узле упорядочены по возрастанию 2. Записи в узле P0 имеют ключи, меньшие, чем ключ записи R1 3. Записи в узле Pk имеют ключи, большие, чем ключ записи Rk 4. Записи в узле Pj, 1 ? j ? k – 1, имеют ключи, большие, чем ключ записи Rj, и меньшие, чем ключ записи Rj + 1 22


Slide 22

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


Slide 23

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


Slide 24

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


Slide 25

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


Slide 26

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


Slide 27

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


Slide 28

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


Slide 29

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


Slide 30

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


Slide 31

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


Slide 32

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


Slide 33

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


Slide 34

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


Slide 35

Слияние листьев (2) Пример: фрагмент В-дерева степени 2; удаляется ключ 15 32 75 8 15 42 52 92 36


Slide 36

Пример: В-дерево степени 1 Удаляется ключ 77 64 10 25 77 93 19 81 37


Slide 37

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


Slide 38

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


Slide 39

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


Slide 40

Вставка в В+ дерево Аналогично В-дереву, за исключением расщепления листа: медианный ключ перемещается в родительский узел и остается в листе (правом или левом) k0 k1 … kj-1 kj … k2n … … kj 41


Slide 41

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


Slide 42

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


Slide 43

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


Slide 44

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


Slide 45

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


Slide 46

Удаление из В+ дерева Только из листьев Пример: В+ дерево степени 2; удаляется ключ 31 15 31 31 35 17 21 27 . . . . . . . . . 73 219 39 . . . . . . 47


Slide 47

Антипереполнение: перераспределение Удаляется 39; перераспределение ключей (ключ 31 удаляется) 15 31 35 17 21 27 . . . . . . . . . 73 219 39 . . . . . . 27 48


Slide 48

Антипереполнение: слияние Удаляется 39; слияние листьев (ключ 31 удаляется) 15 31 35 17 21 . . . . . . . . . 73 219 39 . . . . . . 49


Slide 49

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


Slide 50

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


Slide 51

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


Slide 52

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


Slide 53

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


Slide 54

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


Slide 55

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


Slide 56

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


Slide 57

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


Slide 58

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


Slide 59

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


Slide 60

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


×

HTML:





Ссылка: