Навигация
Главная
Поиск
Форум
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
Создание отчето... 63877
Модуль Forms 63618
ТЕХНОЛОГИИ ДОСТ... 60461
Пример работы с... 59795
Имитационное мо... 55924
Реклама
Сейчас на сайте
Гостей: 11
На сайте нет зарегистрированных пользователей

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

Компьютерный магазин на Turbo Pascal (База данных) + Пояснительная записка
Принадлежит ли точка пересечению двух окружностей на Turbo Pascal + Отче...
Моделирование работы перекрёстка по регулированию движения на GPSS + Поя...

Реклама



Подписывайся на 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 Комментариев · 7115 Прочтений · Для печати

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


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



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

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

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

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

Пароль



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

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

Случайные загрузки
PHP глазами хакера
Программирование ...
ИНТЕРНЕТ ПРОГРАММ...
Gold Submitter II...
Preview
Изучаем Ассемблер
Проигрыватель Mp3
Report
Delphix Sample [И...
Java 2 - Эффектив...
Win-Prolog 3.618
Пример работы с р...
Программирование ...
DragMe [Исходник ...
Bitmap [для кнопок]
Allsubmitter 4.7 ...
Самоучитель PHP 5...
CwstatusBar
IpEditAdress
AlnComponents

Топ загрузок
Приложение Клие... 100447
Delphi 7 Enterp... 85789
Converter AMR<-... 20067
GPSS World Stud... 12518
Borland C++Buil... 11572
Borland Delphi ... 8503
Turbo Pascal fo... 7023
Visual Studio 2... 4989
Калькулятор [Ис... 4739
FreeSMS v1.3.1 3535
Случайные статьи
Есть ли польза от ...
Фаза управления
Использование кома...
3.1. Принципы
ASM expected
Основы службы подд...
Полная ленивость
Получи www.anythin...
Создание собственн...
Работа с Cookies н...
4.3.2. Комбинаци...
Игровые автоматы о...
6.3. Классификаци...
Обработка транзакц...
Линия тренда
Предикат поиска ст...
7.12. Отображение...
Процесс закреплени...
Как привлечь 1000 ...
Операция опроса
Несжатые данные
Транзакции
Генерация HTTP зап...
write(X)
Устранение избыто...
Статистика



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


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