В-дерево

СтруктураВ-дерева(сбалансированное дерево) является следствием дальнейшего расширения концепции использования индексов (строится индекс над индексом) и представляет собой многоуровневые индексы. Записи упорядочиваются внутри блока. Каждый блок получает свой ключ, ключи объединяются в блоки и т.д.

Рис. 15. В-дерево

При поиске число обращений к ВП равно числу уровней дерева.

Процедура добавления записи также достаточно эффекитивна.

Размещение записей с использованием хэширования

Определенным образом выбирается так называемаяхэш-функция f. Аргументом этой функции является значение x первичного ключа логической записи. Тогда f(x) указывает адрес расположения блока, в котором должна находиться логическая запись со значением ключа x. Функция f должна, по возможности, равномерно распределять значения x по физическим блокам. Может оказаться, что выбранная функция отображает в один адрес памяти (один блок) более k записей. Возникает так называемая коллизия. Возможным способом разрешения коллизий является использование дополнительной области переполнения.

При поиске по заданному значению ключа x подсчитывается значение функции f(x), из ВП считывается блок, находящийся по адресу f(x). Если записи в блоке нет, то она ищется в списке переполнения. Аналогично происходит добавление записи.

Структура хранения с использованием хэширования является наиболее эффективной из рассмотренных выше по критерию минимизации числа обращений к ВП при реализации основных операций.

 

В СУБД могут использоваться как каждая из вышерассмотренных структур в отдельности, так и их комбинация.

 

ЛИТЕРАТУРА

Основные источники:

1. Фуфаев Э.В. Базы данных: учеб. пособие для студ. сред. проф образования / Э.В. Фуфаев, Д.Э. Фуфаев. – 3-е изд., стер. – М.: Издательский центр «Академия», 2007. – 320 с.

2. Фуфаев Э.В. Разработка и эксплуатация удаленных баз данных: учебник для студ.сред.проф.образования/ Э.В. Фуфаев, Д.Э. Фуфаев. –М.: Издательский центр «Академия», 2008. – 256 с.

 

Дополнительные источники:

1. Агальцов В.П. Базы данных. В 2-х кн. Книга 1. Локальные базы данных: учебник. – М.: ИД «ФОРУМ»: ИНФРА-М, 2009.- 349 с.

2. Агальцов В.П. Базы данных. В 2-х кн. Книга 2. Распределенные и удаленные базы данных: учебник. – М.: ИД «ФОРУМ»: ИНФРА-М, 2009.- 272 с.

3. Пушников А.Ю. Введение в системы управления базами данных. Часть 1. Реляционная модель данных: Учебное пособие / Изд-е Башкирского ун-та. - Уфа, 1999. - 108 с.

 

Интернет-ресурсы:

1. Грошев А.С. Основы работы с базами данных. [Электронный ресурс]. – Режим доступа: http://www.intuit.ru/department/database/basedbw/ , свободный

2. Швецов В.И. Базы данных. [Электронный ресурс] – Режим доступа: http://www.intuit.ru/department/database/databases/ , свободный