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

Содержание

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

Слайд 1Внутренние структуры хранения


Слайд 2Организация доступа к данным
Наличие двух уровней системы для организации доступа к

данным
Поддержка отношений-каталогов
Регулярность структуры данных

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

Слайд 4Уровень СУБД

Слайд 5Уровень ОС

Слайд 6Временные характеристики
Наиболее распространенное время доступа к дисковой памяти – от 3

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

Слайд 7Каталоги
Обычные отношения РМД
Содержат информацию, связанную с объектами базы данных
Примеры:


SELECT * FROM T
INSERT INTO T VALUES (e1, e2, … )

Слайд 8Структура файлов базы данных
Основной объект базы данных – таблица; совокупность строк
Дополнительные

управляющие структуры – индексы
Управляющая (служебная) информация – для удовлетворения внутренних потребностей нижнего уровня системы

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

WHERE ключ = значение

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

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

Слайд 11Бинарные деревья поиска
Упорядоченная тройка (TL, R, TR)
R – корень дерева
TL, TR

– левое и правое поддеревья корня R; двоичные деревья
NL, NR – количество узлов в поддеревьях, NL ≥ 0, NR ≥ 0
Общее количество узлов в дереве NR = NL + NR + 1

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

правый указатели на поддеревья
Длина поиска – длина пути от корня до целевой записи

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

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

Слайд 15Многоходовые деревья
Каждый узел дерева содержит N ключей и, соответственно, N +

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

Слайд 16Узел дерева




P0 K1 P1 K2 P2 … PN-1 KN PN
{ K(Pi-1)}

< Ki < {K(Pi)},

. . .

KN

K2

K1

P0

P1

P2

PN–1

PN

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

Слайд 18В-дерево
Сбалансированное многоходовое дерево. Узлы В-дерева могут иметь свободное пространство, что упрощает

операции вставки и удаления
а) от слова Balanced – сбалансированное дерево, в котором все листья имеют один и тот же уровень
б) от Bayer – автора данной структуры

Слайд 19В-дерево степени n (1)
1. Все пути от корня до любых листьев

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

Слайд 20В-дерево степени n (2)
3. В корне В-дерева может располагаться минимум 1,

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

Слайд 21Структура узла В-дерева
P0 R1 P1 R2 P2 … Pk-1 Rk Pk
P0,

P1, P2, …, Pk – указатели на подчиненные узлы
R1, R2, …, Rk – записи (ключ и RowID)

Слайд 22Правила следования
1. Ключи записей в текущем узле упорядочены по возрастанию
2. Записи

в узле P0 имеют ключи, меньшие, чем ключ записи R1
3. Записи в узле Pk имеют ключи, большие, чем ключ записи Rk
4. Записи в узле Pj, 1 ≤ j ≤ k – 1, имеют ключи, большие, чем ключ записи Rj, и меньшие, чем ключ записи Rj + 1

Слайд 23Примеры В-деревьев

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

не заполнен

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

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

48, 3, 5, 70, 101


3) 48

48

1) 20

2) 12

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



5) 5

3

12
5

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




7) 101



70
101
70

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

Слайд 30Удаление ключа
Удаляемый ключ находится в листе дерева
Удаляемый ключ находится в промежуточном

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

Слайд 31Нормальная ситуация
В целевом листе находится более чем n элементов (n –

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

20

42

29

35

21

25

27

. . .

. . .

. . .

. . .

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

количество
При удалении ключа нарушается свойство В-дерева
Перераспределение ключей
Слияние узлов

Слайд 33Перераспределение ключей (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

Слайд 34Перераспределение ключей (2)
Пример: фрагмент В-дерева степени 3; удаляется ключ 276
191, 196,

201, 210, 211, 253, 255, 293

189

253

510

191

195

201

210

211

255

276

293

. . .

. . .

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

– 1) + 1 + n = 2n
Удаляется один из листьев
Удаляется ключ из родительского узла

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

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

Слайд 38Основные свойства В-дерева
Ключи и ассоциированные с ними данные (RowID) хранятся во

всех узлах В-дерева
Произвольная выборка данных выполняется эффективно
Последовательная выборка данных мало эффективна

Слайд 39В+ дерево (1)
Два типа узлов В+ дерева:
внутренние узлы – представляют собой

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

Слайд 40В+ дерево (2)






Внутренние узлы –
индексы
Листья
. . .
.

. .

Слайд 41Вставка в В+ дерево
Аналогично В-дереву, за исключением расщепления листа: медианный ключ

перемещается в родительский узел и остается в листе (правом или левом)


k0


k1


…


kj-1


kj


…


k2n




…




…








kj

Слайд 42Пример: вставка в В+ дерево степени 1 (1)
Вставляется последовательность ключей 20,

12, 48, 3, 5, 70, 101


3) 48

48

1) 20

2) 12

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



5) 5

3

12
5
20

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






70
48
5
20

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





7) 101

5
70
101

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

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

ключ 31

15

31

31

35

17

21

27

. . .

. . .

. . .

73

219

39

. . .

. . .

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

. .

. . .

73

219

39

. . .

. . .

27

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

.

. . .

73

219

39

. . .

. . .

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

индекс в физический адрес хранения соответствующей строки таблицы
Принцип отображения – m : 1

Слайд 51Организация хранения таблицы




0
1
N - 1
. . .
Бакеты (buckets)

Слайд 52Идея хеширования (1)


hash












бакет
бакет
Первичная
область
Область
переполнения
Ключи


Слайд 53Идея хеширования (2)
Для k1 ≠ k2 hash(k1) = hash(k2)
k1, k2 –

синонимы
Разрешение коллизий:
выявление свободного пространства в бакете
обработка переполнения бакета

Слайд 54Метод открытой адресации







бакет
Первичная область + область переполнения


Бакет А


Бакет В

Слайд 55Метод срастающихся цепочек









Указатель на свободное пространство








Бакет А


Бакет В

Слайд 56Метод раздельных цепочек








Первичная область
Область переполнения




Бакет А

Бакет В

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

таблицы
упорядоченное хранение строк таблицы
определены и операции < и > для сравнения ключей

Хеш индексы

не представляются объектами базы данных
влияют на представление таблицы
упорядоченность строк отсутствует
определены только операции = и ≠ для ключей

Слайд 58Сравнение методов индексирования (2)
В+ деревья
пространство для таблицы выделяется по мере вставки

строк
могут создаваться на ключевых и не ключевых атрибутах
используются всеми СУБД

Хеш индексы

пространство для таблицы выделяется при создании таблицы
должны создаваться только на ключевых атрибутах
используются не всеми СУБД

Слайд 59Рекомендации
Если размер таблицы сильно изменяется – не хэш таблица
Если

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

Слайд 60Пример создания хеш таблицы (1)
Создание кластерного хеш-индекса (Oracle)
CREATE CLUSTER HD (


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

Слайд 61Пример создания хеш таблицы (2)
Создание хеш-таблицы (Oracle)
CREATE TABLE Tab (
MDID NUMBER

(5) NOT NULL PRIMARY KEY,
. . . -- другие колонки таблицы
) CLUSTER HD(MDID) -- на каком хеш-индексе строится таблица

Похожие презентации

Потолочная система охлаждения панельного типа Uponor Comfort 208
ЭКОЛОГИЧЕСКАЯ ОТВЕТСТВЕННОСТЬ СЕГОДНЯ - ЖИЗНЬ ЗАВТРА 224
Накануне 50-летия нашего города я решил найти фотографии его строительства. Зачастую местность так меняется, что, сопоставив две фотографии, одну старую, а другую современную, долго не можешь поверить, что это одно и то же место. Например, далеко немногие 187
ФГОС НОО (Выполнила Кибиткина С.В., учитель СОШ № 2 г. Ершова 193
Обнаружитель людейпри катастрофах 174
Синергия в продаже 211

Обратная связь

Если не удалось найти и скачать презентацию, Вы можете заказать его на нашем сайте. Мы постараемся найти нужный Вам материал и отправим по электронной почте. Не стесняйтесь обращаться к нам, если у вас возникли вопросы или пожелания:

Email: Нажмите что бы посмотреть 

Что такое ThePresentation.ru?

Это сайт презентаций, докладов, проектов, шаблонов в формате PowerPoint. Мы помогаем школьникам, студентам, учителям, преподавателям хранить и обмениваться учебными материалами с другими пользователями.

Для правообладателей

Яндекс.Метрика