Я просматривал B-Tree topi c в Введение в алгоритмы от Cormen et. al. И у меня возникли трудности с реализацией дисковых операций псевдокода в реальной программе. Это может быть ситуация, потому что некоторые описания объектов здесь не понятны. Так мог бы кто-нибудь подсказать мне, как действовать дальше.
Ниже приведены выдержки из текста, представляющие ситуацию разработки:
Мы моделируем дисковые операции в нашем псевдокоде как следует. Пусть x будет указателем на объект. Если объект в настоящее время находится в основной памяти компьютера , то мы можем ссылаться на поля объекта как обычно: key[x], например. Однако, если объект, на который указывает x, находится на диске, мы должны выполнить операцию Disk-Read (x), чтобы прочитать объект x в основную память, прежде чем мы сможем ссылаться на его поля. (Мы предполагаем, что если x уже находится в основной памяти, то Disk-Read (x) не требует доступа к диску; это «не работает».) Аналогично, операция Disk-Write(x) используется для сохранения любых изменений, которые были сделаны. в поля объекта x. Типичный шаблон для работы с объектом выглядит следующим образом:
x <- a pointer to some object
Disk-Read (x)
operations that access and/or modify the fields of x
Disk-Write(x) // Omitted if no fields of x were changed.
other operations that access but do not modify fields of x
Итак, вполне очевидно, что если x должен хранить объект, который на диске, мы не можем ссылаться на него. если мы не перенесем его в основную память, но как мы можем иметь x, указывающее на объект на диске в первую очередь, это что-то, у меня проблема с реализацией.
Я не мог понять как реализовать эти дисковые операции в реальной программе.
Создание пустого B-дерева
Чтобы построить B-дерево T, мы сначала используйте B-Tree-Create, чтобы создать пустой узел root. В этой процедуре используется вспомогательная процедура Allocate-Node, , которая выделяет одну дисковую страницу для использования в качестве нового узла через O(1) время. (Я знаю, что нужно выделить в куче, но здесь они говорят о выделении непосредственно на диске? Более того, если x содержит ссылку на объект, размещенный на диске, то, не помещая его в основную память, мы не можем работать с его атрибутами в соответствии с предыдущим выдержка). Мы можем предположить, что узел, созданный Allocate-Node, не требует Disk-Read, поскольку на диске еще нет полезной информации для этого узла. (Если мы не читаем его, как мы можем установить атрибуты x?)
В-Tree-Create (T):
1 x <- Allocate-Node()
2 leaf[x] <- true
3 n[x] <- 0
4 Disk-Write (x)
5 root[T] <- x
Я знаю, как выделить в куче, и скажу, что используйте fwrite() в C programming language, чтобы записать его на диск, но как включить линковка на диске? Следует ли использовать ftell(), чтобы получить начало объекта в файле и, соответственно, выполнить связывание?
Я не совсем понимаю, как элегантно записывать объекты на диск, сохраняя связанную структуру. (Текст Структуры данных с использованием C и C ++ Автор Аарон М. Тененбаум и др. имеет дело только с topi c наглядно без хардкорной реализации. И я еще не пройдите формальный курс СУБД)
Пожалуйста, помогите мне, если возможно. Спасибо ..
[Обратите внимание, что я рассмотрел этот вопрос , а также этот , но предложенные ответы содержат огромные коды без какой-либо документации или ярких комментариев, поискав в Google stuff дает B-дерево, поддерживаемое в основной памяти (это не то, для чего они предназначены). Может ли кто-нибудь просто указать мне на эту вещь на более простом языке программирования, таком как C, чтобы я мог понять набросок процесса, не вдаваясь в детали сотен строк кода, с гораздо более сложными задачами, такими как получение блокировки, а затем снятие блокировки, дефрагментация и т.д. c.] [Тем более на топи c есть видео-лекция , но без подробностей реализации]