|
||||
Меню:
Главная
Форум
Литература: Программирование и ремонт Импульсные блоки питания Неисправности и замена Радиоэлектронная аппаратура Микросхема в ТА Рубрикатор ТА Кабельные линии Обмотки и изоляция Радиоаппаратура Гибкие диски часть 2 часть 3 часть 4 часть 5 Ремонт компьютера часть 2 Аналитика: Монтаж Справочник Электроника Мощные высокочастотные транзисторы 200 микросхем Полупроводники ч.1 Часть 2 Алгоритмические проблемы 500 микросхем 500 микросхем Сортировка и поиск Монады Передача сигнала Электроника Прием сигнала Телевидиние Проектирование Эвм Оптимизация Автомобильная электроника Поляковтрансиверы Форт Тензодатчик Силовые полевые транзисторы Распределение частот Резисторные и термопарные Оберон Открытые системы шифрования Удк |
[125] Рис. 19.3 Б-дерево высоты 2 содержит более миллиарда ключей. Каждая вершина содержит 1000 ключей. Всего имеется 1001 вершина на глубине 1 и более миллиона листьев на глубине 2. В каждой вершине х записано число п[х] ключей в ней. памяти лишь небольшую часть всей информации (фиксированное число секторов), и поэтому её размер не ограничивается размером доступной памяти. Мы рассматриваем диск как большой участок памяти, работа с которым происходит следующим образом: перед тем как работать с объектом ж, мы должны выполнить специальную операцию Disk-Read (ж) (чтение с диска). После внесения изменений в наш объект ж, мы выполняем операцию Disk-Write) (запись на диск): 1... 2ж <- указатель на какой-то объект 3Disk-Read) 4операции, которые используют и/или изменяют поля объекта, на который указывает ж. 5Disk-Write) > Не нужно, если > поля объекта не изменились. 6операции, которые пользуются полями указателя ж, но не меняют их. 7... Время работы программы в основном определяется количеством операций Disk-Read и Disk-Write, так что имееет смысл читать/записывать возможно больше информации за раз и сделать так, чтобы вершина Б-дерева заполняла полностью один сектор диска. Таким образом, степень ветвления (число детей вершины) определяется размером сектора. Типичная степень ветвления Б-деревьев находится между 50 и 2000 (в зависимости от размера элемента). Увеличение степени ветвления резко сокращает высоту дерева, и тем самым число обращений к диску, при поиске. На рис. 19.3 показано Б-дерево степени 1001 и высоты 2, хранящее более миллиарда ключей. Учитывая, что корень можно постоянно хранить в оперативной памяти, достаточно двух обращений к диску, при поиске нужного ключа! 19.1. Определение Б-дерева Как и раньше, для простоты мы считаем, что дополнительная информация, связанная с ключом, хранится в той же вершине де- вершина может содержать лишь ссылку на сектор, где хранится эта дополнительная информация.) Мы считаем, что при перемещениях ключа дополнительная информация (или ссылка на неё) перемещается вместе с ним. Тем самым элементом Б-дерева будет ключ вместе со связанной с ним информацией. В принципе мы могли бы использовать другую часто встречающуюся организацию Б-деревьев: помещать сопутствующую информацию в листьях (где больше места, так как не надо хранить ключи), а во внутренних вершинах хранить только ключи и указатели на детей, экономя место (и получая возможность увеличить степень ветвления при том же размере сектора). Итак, Б-деревом (B-tree) назовём корневое дерево, устроенное следующим образом: 1.Каждая вершина х содержит поля, в которых хранятся: а), количество п[х] ключей, хранящихся в ней; б), сами ключи keyi[x] кеу2[х] ... кеуп[х] (в неубывающем порядке) в), булевское значение leaj[x], истинное, когда вершина х является листом. 2.Если х - внутренняя вершина, то она также содержит п[х] + 1 указатель с\[х], с2[х],..., сга[г,] 1[ж] на её детей. У листьев детей нет, и эти поля для них не определены. 3.Ключи keyi[x] служат границами, разделяющими значения ключей в поддеревьях: ki кеух[х] к2 кеу2[х] • • • кеуп[х][х\ кп[х]+1, где к{ - любой из ключей, хранящихся в поддереве с корнем сг[х]. 4.Все листья находятся на одной и той же глубине (равной высоте h дерева). 5.Число ключей, хранящихся в одной вершине, ограничено сверху и снизу; границы задаются единым для всего дерева числом t 2, которое называется минимальной степенью (minimum degree) Б-дерева. Именно: а). Каждая вершина, кроме корня, содержит по меньшей мере t-1 ключ. Таким образом, внутренние вершины (кроме корня) имеют не менее t детей. Если дерево непусто, то в корне должен храниться хотя бы один ключ. всегда удобно, и в реальном алгоритме б). В вершине хранится не более 2t - 1 ключей. Следовательно, внутренняя вершина имеет не более 2t детей. Вершину, хранящую ровно 2t - 1 ключей, назовем полной (full). В простейшем случае t = 2, тогда у каждой внутренней вершины 2, 3 или 4 ребенка, и мы получаем так называемое 2-3-4 дерево (2-34 tree). (Как мы уже говорили, для эффективной работы с диском на практике t надо брать гораздо большим.) Высота Б-дерева Число обращений к диску для большинства операций пропорционально высоте Б-дерева. Оценим сверху эту высоту. Теорема 19.1. Для всякого Б-дерева Т высоты h и минимальной степени t 2, хранящего га 1 ключей, выполнено неравенство h s 1 11 + 1 h l°gf --. Доказательство. Пусть высота Б-дерева равна заданному числу h. Наименьшее число вершин в дереве будет, если степень каждой вершины минимальна, то есть у корня 2 ребёнка, а у внутренних вершин по t детей. В этом случае на глубине 1 мы имеем 2 вершины, на глубине 2 имеем 2t вершин, на глубине 3 имеем 2t2 вершин, ... , на глубине h имеем 2th~1 вершин. При этом в корне хранится один ключ, а во всех остальных вершинах по t - 1 ключей. (На рис. 19.4 показано такое дерево при h чаем неравенство: h га 1 + (t - 1) Y 2~1 = 1 + 2(* - 8 = 1 откуда следует утверждение теоремы. Как и для красно-чёрных деревьев, высота Б-дерева с га вершинами есть О (log га), но основание логарифма для Б-деревьев гораздо больше, что примерно в lg 4 раз сокращает количество обращений к диску. Упражнения 19.1-1 Почему в определении Б-дерева требование t 2 существенно? 19.1-2 При каких t дерево на рис. 19.1 можно рассматривать как Б-дерево минимальной степени tl 3.) Таким образом, полу- th - 1 □ |
Среды: Smalltalk80 MicroCap Local bus Bios Pci 12С ML Микроконтроллеры: Atmel Intel Holtek AVR MSP430 Microchip Книги: Емкостный датчик 500 схем для радиолюбителей часть 2 (4) Структура компьютерных программ Автоматическая коммутация Кондиционирование и вентиляция Ошибки при монтаже Схемы звуковоспроизведения Дроссели для питания Блоки питания Детекторы перемещения Теория электропривода Адаптивное управление Измерение параметров Печатная плата pcad pcb Физика цвета Управлении софтверными проектами Математический аппарат Битовые строки Микроконтроллер nios Команды управления выполнением программы Перехода от ahdl к vhdl Холодный спай Усилители hi-fi Электронные часы Сердечники из распылённого железа Анализ алгоритмов 8-разрядные КМОП Классификация МПК История Устройства автоматики Системы и сети Частотность Справочник микросхем Вторичного электропитания Типы видеомониторов Радиобиблиотека Электронные системы Бесконтекстный язык Управление техническими системами Монтаж печатных плат Работа с коммуникациями Создание библиотечного компонента Нейрокомпьютерная техника Parser Пи-регулятор ч.1 ПИ-регулятор ч.2 Обработка списков Интегральные схемы Шина ISAВ Шина PCI Прикладная криптография Нетематическое: Взрывной автогидролиз Нечеткая логика Бытовые установки (укр) Автоматизация проектирования Сбор и защита Дискретная математика Kb радиостанция Энергетика Ретро: Прием в автомобиле Управление шаговым двигателем Магнитная запись Ремонт микроволновки Дискретные системы часть 2 | ||