Как организовать работу структуры b-дерева, файла данных и файла индексов?

Question

[ccc35]

Есть готовое b-дерево на C++. Имеются функции вставки, удаления и поиска.
Необходимо сделать следующее:
1. Элементом данных, хранящихся в файле, является запись, имеющая уникальное ключевое значение.
2. Запись в файле представлена индексом, т.е. парой (k,p), где k – ключевое значение, p – файловый указатель на начало записи в файле.
3. Для файла данных поддерживается файловая структура индексов, указанная в варианте задания.
4. Файл индексов имеет страничную структуру. Страницы содержат индексы записей и имеют фиксированный размер.
5. Чтение и запись в файл индексов ведется постранично.
6. Тестирование файловой структуры ведется для различных значений параметров:
N – число записей в файле данных, N = 103, 104, 105, 106,
M – число индексов на странице файла индексов, M = 10,100, 1000.
7. Число обращений к блокам файла индексов в процессе выполнения операций должно соответствовать: для B- дерева файла – 2 + logt (N/M), где t – степень В – дерева.

Вопрос. Как организовать работу структуры b-дерева, файла данных и файла индексов ?

Comments

[Станислав Макаров]

> Есть готовое b-дерево на C++. Имеются функции вставки, удаления и поиска.
> Вопрос. Как организовать работу структуры b-дерева, файла данных и файла индексов ?
Готовое b-дерево есть работающая структура b-дерева, не обязательно с отображением в файл, но по кр. мере в памяти. Таки непонятно, что у вас есть, а что нужно реализовать.

[ccc35]

Станислав Макаров: Да, скорее всего я не правильно выразился. Есть код отсюда www.geeksforgeeks.org/b-tree-set-1-introduction-2
Там есть поиск, вставка и удаление.
Теперь нужно организовать работу с файлами. Файлом индексов и файлом данных.

Answer 1

[Станислав Макаров]

Там есть поиск, вставка и удаление.
Теперь нужно организовать работу с файлами. Файлом индексов и файлом данных.

1) заменяете указатели на потомков в узлах дерева на абстрактные указатели или номера. Это нужно потому, что узлы дерева теперь могут быть как в основной памяти, так и на диске, поэтому при обращении к любому из узлов нужно сначала смотреть, загружен он или нет, и при необходимость загружать с диска (т.е. огранизовать простейший кэш);
2) в листовых узлах вы будете хранить такие же абстрактные указатели, только не на узлы дерева (которые в индексном файле), а на реальные записи (которые в файле данных). С записями можно поступать точно также - проверять, загружены они в кэш или нет, при необходимость загружать и отдавать пользователю.
3) операции изменения теперь должны научиться помечать узлы как "грязные", т.е. требующие сохранения на диск. В процессе модификации B-дерева вы помечаете как грязные все изменившиеся узлы, и потом сохраняете их диск (по окончании операции или через равные промежутки времени), после сохранения каждого узла сбрасываете флаг.

Собственно основные изменения: организация кэша для записей данных и индекса и переделка дерева на работу с узлами через кэш, а не напрямую по указателю на BTreeNode.