Объекты и указатели облегчают построение дерева в памяти, но они не годятся
для его сохранения на жестком диске. Нельзя создать указатель на часть файла.
Вместо этого можно использовать методы работы с псевдоуказателями и за-
менить указатели номерами записей. Указателем на узлы дерева ссылок служат
не объекты, а номер записи узла в файле. Например, Б+дерево 12-го порядка опе-
рирует с 80-байтовыми ключами. Структуру данных узла можно определить в сле-
дующем коде:
const
ORDER = 12;
KEYS_PER_NODE = 2*ORDER;
type
String80 = String[80];
TBtreeNode = record
Key : array [1..KEYS_PER_NODE] of StringSO; //Ключи
Child : array [0..KEYS_PER_NODE] of Longint; // Указатели на узлы.
end;
Элементы массива Chi Id указывают номер записи из дочерних узлов в файле.
Случайный доступ к файлу данных Б+дерева возможен при помощи записей,
которые соответствуют структуре BtreeNode.
AssignFile(IdxFile,file_name);
Reset(IdxFile);
Когда файл открыт, вы можете выбрать конкретную запись с помощью команд
Seek и Read.
Seek(IdxFile,node_number);
Read(IdxFile,node_record);
Чтобы упростить управление Б+деревом, можно сохранять узлы и записи дан-
ных в отдельных файлах и использовать для управления каждым из них псевдо-
указатели.
Когда программе больше не нужна запись в файле, она не может просто очис-
тить все ссылки на индекс этого элемента. Если сделать так, то программа больше
не сможет использовать эту запись, хотя та все еще занимает место в файле.
Программа должна отслеживать пустые ячейки, чтобы потом можно было по-
вторно использовать их. Один из простых способов сделать это - вести связан-
ный список неиспользуемых записей. Когда запись больше не нужна, ее добавля-
ют к списку. Когда программе нужна новая запись, она удаляет одну запись из
этого списка. Если программе нужен новый элемент, а список пуст, программа рас-
ширяет файл.
|
Главная
Каталог файлов
