Структура данных / алгоритм для хранения записей переменной длины и поиска на диске withsearch только на первичных ключах

Простой способ: использовать что-то вроде Berkeley DB. Он предоставляет хранилище ключей и значений для произвольных байтовых строк и выполняет всю тяжелую работу за вас. Он даже предоставляет «вторичные базы данных» для индексации, если вы этого хотите.

Самостоятельный способ: используйте буферы протокола (или двоичный формат по вашему выбору) для определения структур узлов B-дерева и элементов данных. Используйте для своей базы данных файл только с добавлением. Чтобы записать новую запись или изменить существующую запись, вы просто записываете саму запись в конец файла, а затем записываете любые измененные узлы B-дерева (например, родительский узел записи, его родительский узел, и так далее до корня). Затем запишите местоположение нового корня дерева в блок заголовка в начале файла. Чтобы прочитать файл, вы просто находите самый последний корневой узел и читаете B-Tree, как и в любом другом файле. Этот подход имеет несколько преимуществ:

• Поскольку записанные данные никогда не изменяются, читателям не нужно снимать блокировки и получать «моментальный снимок» БД на основе корневого узла в момент начала чтения.
• Добавляя поля «предыдущая версия» к вашим узлам и записям, вы получаете возможность получить доступ к предыдущим версиям БД практически бесплатно.
• Это действительно легко реализовать и отладить по сравнению с большинством форматов файлов на диске, которые поддерживают модификацию.
• Сжатие базы данных состоит из простого чтения последней версии данных и B-дерева и записи ее в новый файл.

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

Вы можете избавиться от любого поиска O (log m) в B-дереве, сохранив индекс, то есть {"логический ID «сопоставляется с« физическим местоположением »} пар значений в хеш-карте (хеширование логического идентификатора) ... или даже при сохранении индекса в непрерывном векторе (с логическим идентификатором, используемым в качестве индекса в векторе значения смещения), как предложил bdonlan, если значения идентификаторов не являются редкими.

Важной деталью реализации может быть то, какой API вы используете для доступа к индексу: храните ли вы его в ОЗУ (что O / S поддерживает системный файл подкачки) и получить к нему доступ в процессе с помощью указателей и / или сохранить его на диске (который O / S кэширует в кэше файловой системы) и получить к нему доступ с помощью API файлового ввода-вывода.

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

If a database is to heavy weight for you, consider a key-value store.

If you really what to implement it yourself, use a disk-based hash table or a B-tree. To avoid the problems with the variable-length values, store the values in an separate file and use the B-tree as index for the data file. Space-reclaimation after deletion of values will be tricky, but it is possible (e.g. by a bitset for freed space in the data file).