Реализация файла индекса базы данных

Question

Я экспериментирую с дизайном индексного файла базы данных, состоящего из страниц фиксированного размера, каждая из которых содержит набор записей (ключ, указатель), указывающих на фактический файл данных.

Дизайн на основе страниц усложняетвсе.Мне показался самый наивный подход, что я должен хранить записи в отсортированном порядке (то есть сортировать физически, как Page0 имеет записи 0 1 3 6, Page1 имеет записи, 7 8 12 15, ... и т. Д.), Но все же я не могу использовать, например, двоичный файлпоиск в отсортированном файле, поскольку записи не являются последовательными, но находятся на страницах (которые имеют заголовки страниц, свободное пространство и т. д.).

Может ли кто-нибудь предложить несколько советов о том, как искать полностью отсортированный индексный файл со страницами, используя двоичный поиск?

edit: реализация btree на основе страницы слишком сложна для меня сейчас.Я хочу попасть туда после достижения более простых подходов, как указано выше.

Answer 1

Мне позже удалось сделать это легко.

Читать страницу посередине. Проверьте его первую и последнюю записи (или записи с наименьшим / наибольшим индексом, если страница не отсортирована внутри). Идите вправо или влево в зависимости от вашего ключа поиска. Loop.

Answer 2

Обычно проще всего создать индекс, который вы хотите использовать, и просто сохранить его в памяти.Таким образом, вы можете оптимизировать свое хранилище данных и доступ к ним, помимо того, как они индексируются.

Когда я реализовал нечто подобное, я сохранил индекс как большой кусок в файле, а затем поместил данные как другой больший кусок.

Answer 3

B-дерево из Википедии