|
||||
Меню:
Главная
Форум
Литература: Программирование и ремонт Импульсные блоки питания Неисправности и замена Радиоэлектронная аппаратура Микросхема в ТА Рубрикатор ТА Кабельные линии Обмотки и изоляция Радиоаппаратура Гибкие диски часть 2 часть 3 часть 4 часть 5 Ремонт компьютера часть 2 Аналитика: Монтаж Справочник Электроника Мощные высокочастотные транзисторы 200 микросхем Полупроводники ч.1 Часть 2 Алгоритмические проблемы 500 микросхем 500 микросхем Сортировка и поиск Монады Передача сигнала Электроника Прием сигнала Телевидиние Проектирование Эвм Оптимизация Автомобильная электроника Поляковтрансиверы Форт Тензодатчик Силовые полевые транзисторы Распределение частот Резисторные и термопарные Оберон Открытые системы шифрования Удк |
[124] tent data structures) позволяют получать информацию о предыдущих состояниях (версиях содержимого) структуры, а иногда и менять предыдущие версии. Общую методику сохранения предыдущих версий списочной структуры данных (с небольшими потерями по времени и памяти) предложили Дрисколл, Сарнак, Слеатор и Тарьян [59]. Напомним, что в задаче 14-1 подобная структура строилась для динамического множества. Б-деревья В этой главе мы рассмотрим один из видов сбалансированных деревьев, при котором обеспечивается эффективное хранение информации на магнитных дисках и других устройствах с прямым доступом - Б-деревья. Б-деревья похожи на красно-черные деревья; разница в том, что в Б-дереве вершина может иметь много детей, на практике до тысячи (в зависимости от характеристик используемого диска). Благодаря этому константа в оценке О (log га) для высоты дерева существенно меньше, чем для черно-красных деревьев. Как и черно-красные деревья, Б-деревья позволяют реализовать многие операции с множествами размера га за время О (log га). Пример Б-дерева показан на рис. 19.1. Вершина ж, хранящая га[ж] элементов, имеет га[ж] + 1 детей. Хранящиеся в ж ключи служат границами, разделяющими всех её потомков на га[ж] + 1 групп; за каждую группу отвечает один из детей ж. При поиске в Б-дереве мы сравниваем искомый ключ с га[ж] ключами, хранящимися в ж, и по результатам сравнения выбираем один из га[ж] + 1 путей. Точное определение Б-дерева и логарифмическая (от числа вершин) оценка его высоты приводятся в разделе 19.1. В разделе 19.2 описаны операции поиска и добавления элемента в дерево; удаление обсуждается в 19.3. Но прежде надо объяснить, в чем отличие магнитных дисков от оперативной памяти, делающее выгодным использование Б-деревьев. Рис. 19.1 Б-дерево с английскими согласными в качестве ключей. Внутренняя вершина х с п[х] ключами имеет п[х] + 1 детей. Все листья имеют одну и ту же глубину. Светлые вершины просмотрены в процессе поиска буквы R. Рис. 19.2 Дисковод Структуры данных на диске Компьютер использует разные виды памяти. Оперативная память (main memory) представляет собой микросхемы, каждая из которых вмещает миллионы битов. Цена такой памяти (в расчёте на бит) выше, чем для вторичной памяти (secondary storage). Типичный компьютер использует в качестве вторичной памяти жёсткий диск, объём которого может на несколько порядков превосходить объём оперативной памяти. Магнитная головка (см. рис. 19.2) записывает и читает данные на магнитном слое вращающегося диска. Рычаг может переместить её вдоль радиуса диска. После этого головка читает/пишет данные на одной из дорожек (tracks) диска. Обычно каждая дорожка делится на определённое число равных по размеру секторов (каждый может занимать несколько килобайтов). Обычно записывают или считывают сектор целиком. Время доступа (access time), которое требуется чтобы подвести головку к нужному месту диска, может быть достаточно большим (до 20 миллисекунд); в оперативной памяти такой задержки нет, потому что нет механического перемещения. Как только головка диска уже установлена, запись или чтение диска происходит довольно быстро. Часто получается, что обработка прочитанного занимает меньше времени, чем поиск нужного сектора. Поэтому, оценивая качество алгоритма мы будем учитывать два параметра: •число обращений к диску, и •время вычислений (время работы процессора). Строго говоря, время доступа зависит от положения головки относительно нужного сектора. Но мы не обращаем на это внимания и учитываем лишь число обращений к диску (т.е. число секторов, которые нужно считать или записать). Алгоритмы, работающие с Б-деревьями, хранят в оперативной |
Среды: 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 | ||