Навигация
Главная
Поиск
Форум
FAQ's
Ссылки
Карта сайта
Чат программистов

Статьи
-Delphi
-C/C++
-Turbo Pascal
-Assembler
-Java/JS
-PHP
-Perl
-DHTML
-Prolog
-GPSS
-Сайтостроительство
-CMS: PHP Fusion
-Инвестирование

Файлы
-Для программистов
-Компонеты для Delphi
-Исходники на Delphi
-Исходники на C/C++
-Книги по Delphi
-Книги по С/С++
-Книги по JAVA/JS
-Книги по Basic/VB/.NET
-Книги по PHP/MySQL
-Книги по Assembler
-PHP Fusion MOD'ы
-by Kest
Professional Download System
Реклама
Услуги

Автоматическое добавление статей на сайты на Wordpress, Joomla, DLE
Заказать продвижение сайта
Программа для рисования блок-схем
Инженерный калькулятор онлайн
Таблица сложения онлайн
Популярные статьи
OpenGL и Delphi... 65535
Форум на вашем ... 65535
HACK F.A.Q 65535
Бип из системно... 65535
Гостевая книга ... 65535
Invision Power ... 65535
Содержание сайт... 65535
Организация зап... 65535
Вызов хранимых ... 65535
Программируемая... 65535
Эмулятор микроп... 65535
Подключение Mic... 65535
Создание потоко... 65535
Приложение «Про... 65535
Оператор выбора... 65535
Создание отчето... 65062
Модуль Forms 64838
Пример работы с... 63248
ТЕХНОЛОГИИ ДОСТ... 61552
Имитационное мо... 57399
Реклама
Сейчас на сайте
Гостей: 6
На сайте нет зарегистрированных пользователей

Пользователей: 13,081
новичок: Abdukarimov A
Новости
Реклама
Выполняем курсовые и лабораторные по разным языкам программирования
Подробнее - курсовые и лабораторные на заказ
Delphi, Turbo Pascal, Assembler, C, C++, C#, Visual Basic, Java, GPSS, Prolog, 3D MAX, Компас 3D
Заказать программу для Windows Mobile, Symbian

Моделирование процесса обеспечивающего надежность функционирования АСУ Т...
Расчет мер близости на отношениях на Delphi + Пояснительная записка
База данных студентов на Delphi (файл записей) + Блок схемы

Реклама



Подписывайся на YouTube канал о программировании, что бы не пропустить новые видео!

ПОДПИСЫВАЙСЯ на канал о программировании
База данных на основе Б+дерева
Программа Bplus управляет базой данных на основе Б+дерева с помощью двух
файлов данных - Gusts. dat, содержащего записи данных клиентов, и Gusts. idx,
где находятся узлы Б+дерева.
Введите данные в поле Customer Record (Запись о клиенте) и нажмите кнопку
Add, чтобы добавить в базу данных новый элемент. Введите имя и фамилию в верх-
ней части формы, и нажмите Find (Найти), чтобы отыскать соответствующую запись.
На рис. 7.23 показано окно программы после нахождения записи Rod Stephens.
Метка Accesses (Обращения) в поле Search (Поиск) определяет, что про-
грамме понадобилось всего три обращения к диску, чтобы отыскать запись. Ста-
тистика внизу указывает, что данные были
найдены в записи номер 354. Глубина Б+дерева
равна 3, оно содержит 731 запись данных
и 67 сегмента.
Когда вы вносите запись или проводите
поиск, программа Bplus выбирает эту запись
из файла. После нажатия кнопки Remove про-
грамма удаляет запись из базы данных.
Если выбрать команду Internal Nodes
(Внутренние узлы) в меню Display (Показать),
программа выведет список внутренних узлов
дерева. Она отображает также ключи для каж-
дого узла, чтобы показать внутреннюю струк-
туру дерева.
При помощи команды Complete Tree (Все
дерево) меню Display можно вывести полную
структуру дерева. Данные о клиенте отобра-
жаются в скобках.

Рис. 7.23. Окно программы Bplus
Записи индексного файла содержат 41-байтовые ключи. Каждый ключ - это
фамилия клиента, дополненная до 20 символов, после чего следует запятая, а пос-
ле запятой - имя клиента, дополненное до 20 символов.
Программа Bplus считывает данные блоками по 1024 байта. Если предполо-
жить, что блок содержит К ключей, то в каждом сегменте будет К ключей длиной
41 байт, К + 1 указателей на дочерние узлы по 4 байта и двухбайтовое целое число
NumKeys. При этом полный размер блоков должен быть максимальным, но не пре-
вышать 1024 байт.
Решая уравнение 41*К + 4*(К+1) + 2<= 1024 относительно К, вы получаете
К < 22,62, поэтому К должно быть равно 22. В этом случае Б+дерево имеет поря-
док 11, поэтому оно содержит по 22 ключа в каждом блоке. Каждый сегмент зани-
мает 41 * 22 + 4 * (22 + 1) + 2 = 996 байт. Следующий код демонстрирует опреде-
ление блоков в программе Bplus:

const
KEY_SIZE = 41;
ORDER = 11;
KEYS_PER_NODE = 2*ORDER;



Чтобы упростить управление этими двумя файлами данных, программа Bplus
использует два различных типа записей для представления записи в каждом файле.
Тип данных TBucket представляет запись в индексном файле Б+дерева -
Gusts . idx. Первая запись в Custs. idx содержит заголовок, который описывает
текущее состояние Б+дерева. В заголовок входит число сегментов, содержащихся
в Custs . dat, количество записей данных Gusts . dat, указатели на первый пус-
той блок в каждом файле и т.д.
Остальные записи в файле Custs . idx содержат ключи и индексы. Перемен-
ная NumKeys возвращает число реально используемых в записи ключей.
TBucket = record
case IsHeader : Boolean of
True :
( // Информация заголовка.
NumBuckets : Longint; // Число сегментов в Custs.idx.
NumRecords : Longint; // Число записей в Custs..
Root : Longint; // Индекс корня в Custs.idx.
NextTreeRecord : Longint; // Следующий неиспользуемый в Custs.idx.
NextCustRecord : Longint; // Следующий неиспользуемый в Custs.dat.
FirstTreeGarbage : Longint; // Первый неиспользуемый в Custs. idx.
FirstCustGarbage : Longint; // Первый неиспользуемый в Custs.dat.
Height : Integer; // Глубина дерева.
) ;
False :
( // Сегмент, содержащий ключи.
// Число используемых ключей в данном сегменте.
NumKeys : Integer;
// Key = Last Name, First Name.
Key : array [1..KEYS_PER_NODE] of String[KEY_SIZE];
// Индексы дочерних сегментов.
Child : array [0..KEYS_PER_NODE] of Longint;
end;
end; // Конец объявления записи TBucket.



Тип данных TCustomer представляет запись в файле данных В+дерева —
Gusts. dat. Эта запись немного проще, чем тип данных TBucket. Каждая запись
находится либо в связанном списке свободных ячеек файла, либо содержит дан-
ные о клиентах. Свободные ячейки содержат только индекс следующей записи
связанного списка.
TCustomer = record
case IsGarbage : Boolean of
True :
( // В списке неиспользуемых элементов.
NextGarbage : Longint; // Индекс следующей
// неиспользуемой записи.
);
False :
(
// Запись о клиенте.
LastName : String[20];
FirstName : String[20];
Address : String[40];
City : String[20];
State : String[2];
Zip : String[10];
Phone : String [12] ;
);
end;
end; // Конец определения записи TCustomer.




При запуске программа Bplus запрашивает путь к базе данных, затем открыва-
ет файлы данных Б+дерева Gusts. dat и Gusts . idx в указанном каталоге. Если
файлы не существуют, программа создает их. Если они уже есть, программа счи-
тывает заголовок с информацией о дереве из файла Gusts . idx. Затем она считы-
вает корневой узел Б+дерева и кэширует его в памяти.
Когда программа начинает исследовать дерево, чтобы вставить или удалить
элемент, она кэширует все узлы, к которым обращается. При рекурсивном возвра-
те эти узлы могут понадобиться снова, если произошло разбиение сегмента, слия-
ние или другое переупорядочивание узлов. Поскольку программа кэширует узлы
на пути вниз, они доступны и на пути вверх.
Увеличение размера сегментов делает Б+дерево более эффективным, но при
этом его сложнее проверить «вручную». Чтобы увеличить Б+дерево 11-го порядка
на 2 уровня, вам необходимо добавить в базу данных 23 элемента. Чтобы высота
дерева стала равной 3, необходимо добавить более 250 дополнительных элементов.
Тестировать программу Bplus будет намного легче, если изменить порядок
Б+дерева и сделать его равным 2. В файле BplusC. pas закомментируйте строку,
которая определяет 11-й порядок, и снимите атрибут комментария со строки, за-
дающей 2-й порядок.
// ORDER = 11;
ORDER = 2;



Меню Data (Данные) программы Bplus содержит команду Create Data (Со-
здать данные), которая позволяет быстро создать большое количество записей дан-
ных. Введите число записей, которые вы хотите создать и порядковый номер пер-
вого элемента.
Программа организует записи и вставляет их в Б+дерево. Например, если вы
задаете в программе создание 100 записей, начиная с номера 200, программа обра-
зует записи с порядковыми номерами 200, 201,... ,299, которые будут выглядеть
следующим образом:
FirstName : FirSt_200
LastName : Last_200
Address : Addr_200
City : City_200



Вы можете использовать эти записи для экспериментов с достаточно больши-
ми Б+деревьями.














Опубликовал Kest November 02 2009 23:58:07 · 0 Комментариев · 7160 Прочтений · Для печати

• Не нашли ответ на свой вопрос? Тогда задайте вопрос в комментариях или на форуме! •


Комментарии
Нет комментариев.
Добавить комментарий
Имя:



smiley smiley smiley smiley smiley smiley smiley smiley smiley
Запретить смайлики в комментариях

Введите проверочный код:* =
Рейтинги
Рейтинг доступен только для пользователей.

Пожалуйста, залогиньтесь или зарегистрируйтесь для голосования.

Нет данных для оценки.
Гость
Имя

Пароль



Вы не зарегистрированны?
Нажмите здесь для регистрации.

Забыли пароль?
Запросите новый здесь.
Поделиться ссылкой
Фолловь меня в Твиттере! • Смотрите канал о путешествияхКак приготовить мидии в тайланде?
Загрузки
Новые загрузки
iChat v.7.0 Final...
iComm v.6.1 - выв...
Visual Studio 200...
CodeGear RAD Stud...
Шаблон для новост...

Случайные загрузки
AJAX и PHP. разра...
CS:Source - монит...
Работа с картотеками
Калькулятор [Исхо...
ATComponents
Crystal Button
THttpScan v4.1
Программирование ...
Медиа комбайн
Drag&Drop
Delphi 2005 для .NET
Панель Наша Кнопка
Delphi. Разработк...
Delphi7 Для профе...
VksButton
Borland C++Builde...
PHP 5. Полное рук...
C++ Builder в за...
Учебник по создан...
Приемы программир...

Топ загрузок
Приложение Клие... 100466
Delphi 7 Enterp... 86622
Converter AMR<-... 20077
GPSS World Stud... 12647
Borland C++Buil... 11755
Borland Delphi ... 8555
Turbo Pascal fo... 7037
Visual Studio 2... 4998
Калькулятор [Ис... 4760
FreeSMS v1.3.1 3541
Случайные статьи
Удаление, усечение...
Производительность...
Область применения...
Социативный массив...
Поиск с помощью яз...
Описание сети масс...
Как купить мед спр...
Настройка управлен...
• Кэширование.
Задание ограничени...
Константы в классе
Тур в Львов
Блок try–finally
11.1. Сортировка в...
3. Какие службы ну...
Конечная область п...
Работа асинхронног...
Корпоративное такси
Хакинг приставок X...
Конфигурация серве...
В программе предпо...
Терминальные устро...
Что делают маршрут...
consult(X)
Интерфейс на естес...
Статистика



Друзья сайта
Программы, игры


Полезно
В какую объединенную сеть входит классовая сеть? Суммирование маршрутов Занимают ли таблицы память маршрутизатора?