База данных на основе Б+дерева

Kest

рограмма 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

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

База данных на основе Б+дерева

Ссылки по теме

О нас

Помощь

Способы оплаты

Проекты Interface Ltd.