Студопедия

КАТЕГОРИИ:


Архитектура-(3434)Астрономия-(809)Биология-(7483)Биотехнологии-(1457)Военное дело-(14632)Высокие технологии-(1363)География-(913)Геология-(1438)Государство-(451)Демография-(1065)Дом-(47672)Журналистика и СМИ-(912)Изобретательство-(14524)Иностранные языки-(4268)Информатика-(17799)Искусство-(1338)История-(13644)Компьютеры-(11121)Косметика-(55)Кулинария-(373)Культура-(8427)Лингвистика-(374)Литература-(1642)Маркетинг-(23702)Математика-(16968)Машиностроение-(1700)Медицина-(12668)Менеджмент-(24684)Механика-(15423)Науковедение-(506)Образование-(11852)Охрана труда-(3308)Педагогика-(5571)Полиграфия-(1312)Политика-(7869)Право-(5454)Приборостроение-(1369)Программирование-(2801)Производство-(97182)Промышленность-(8706)Психология-(18388)Религия-(3217)Связь-(10668)Сельское хозяйство-(299)Социология-(6455)Спорт-(42831)Строительство-(4793)Торговля-(5050)Транспорт-(2929)Туризм-(1568)Физика-(3942)Философия-(17015)Финансы-(26596)Химия-(22929)Экология-(12095)Экономика-(9961)Электроника-(8441)Электротехника-(4623)Энергетика-(12629)Юриспруденция-(1492)Ядерная техника-(1748)

Организация индексов в виде Б-деревьев

Структура типа Б-дерева является частным случаем бинарного индекса древовидного типа, которая используется для построения наиболее важных и распространенных индексов. Бинарные индексы обладают в большинстве случаев сравнительно высокой производительностью и поэтому в настоящее время их использование предусмотрено почти во всех СУБД, а некоторые СУБД работают только на основе такого индекса.

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

Построение Б-деревьев связано с простой идеей построения индекса над уже построенным индексом. Действительно, если уже построен плотный (но может быть и неплотный, если в индексированном файле проведена кластеризация на основе индекса) индекс для реальных данных, то сама индексная область может рассматриваться как основной файл, над которым надо снова построить неплотный индекс.

Записи внутри индекса сгруппированы по страницам, а страницы связаны в цепочку таким образом, чтобы логическое упорядочение на основе индекса осуществлялось внутри первой страницы, затем с помощью физической последовательности записей внутри второй страницы этой последовательной цепочки и т. д. Таким образом, с помощью набора последовательностей можно организовать быстрый последовательный доступ к индексированным данным.

Потом снова над новым индексом строится следующий неплотный индекс и так до того момента, пока не останется всего один индексный блок. Эта операция обычно применяется трижды, поскольку создание большого количества иерархических уровней индексирования требуется для очень больших файлов. При этом индекс на каждом из уровней будет неплотным по отношению к нижнему индексируемому уровню. Таким образом, на самом верхнем уровне такого индекса находится только один элемент структуры (страница, содержащая множество записей), который называется корневым.

Набор индексов обеспечивает быстрый непосредственный доступ к набору последовательностей (а значит, и к данным).

В результате такого построения получится некоторое дерево (рис. 7.8), каждый родительский блок которого связан с одинаковым количеством подчиненных блоков, число которых равно числу индексных записей, размещаемых в одном блоке. Количество обращений к диску при этом для поиска любой записи одинаково и равно количеству уровней в построенном дереве. Такие деревья называются сбалансированными потому, что путь от корня до любого листа в этом древе одинаков.

Рис. 7.8. Б-дерево

 

Структуры типа Б-дерева позволяют, используя специальные, алгоритмы, осуществлять сбалансированную вставку или удаление значений. К. Дж. Дейт приводит такой краткий алгоритм вставки нового значения V в структуру типа Б-дерева порядка. Он рассчитан на вставку значения только лишь в набор индексов, но может быть достаточно просто расширен для вставки записи с данными в набор последовательностей.

· На самом низком уровне набора индексов следует найти элемент (допустим, что это элемент N), с которым логически связано вставляемое значение V. Если элемент N содержит свободное пространство, то значение V вставляется в него, и на этом процесс завершается.

· В противном случае (если свободного пространства нет, т. е. придется создать еще один уровень) элемент N (допустим, что он содержит 2n индексных записей) разделяется на два элемента —N1 и N2. Обозначим символом S множество из 2n + 1 значений, в котором 2n исходных значений и одно новое значение V. Тогда n первых значений этой логической (уже упорядоченной) последовательности необходимо поместить в элемент N1, n последних — в элемент N2, а среднее между ними значение W— в родительский элемент Р на более высоком структурном уровне. Впоследствии, при осуществлении поиска значения U и достижении элемента Р, поиск будет перенаправлен в сторону элемента N1, если U £ W, либо в сторону элемента N2, если U > W.

· Далее этот процесс следует повторить для вставки среднего значения W в родительский элемент Р на более высоком структурном уровне.

В худшем случае процесс разделения элементов структуры может продлиться вплоть до корневого элемента всей структуры с образованием нового иерархического уровня.

Для удаления некоторого значения следует применить аналогичный алгоритм, но только в обратном порядке. А для изменения значения его можно удалить, а затем вставить новое.

<== предыдущая лекция | следующая лекция ==>
Индексно-последовательные файлы | Инвертированные списки
Поделиться с друзьями:


Дата добавления: 2014-01-20; Просмотров: 2024; Нарушение авторских прав?; Мы поможем в написании вашей работы!


Нам важно ваше мнение! Был ли полезен опубликованный материал? Да | Нет



studopedia.su - Студопедия (2013 - 2024) год. Все материалы представленные на сайте исключительно с целью ознакомления читателями и не преследуют коммерческих целей или нарушение авторских прав! Последнее добавление




Генерация страницы за: 0.01 сек.