Я ищу алгоритм / структуру данных, которая хорошо работает для больших блочных устройств (например, механический жесткий диск), который оптимизирован для вставки, получения, обновления и удаления, где поиск всегда выполняется с использованием идентификатора данных и где поля данных для любого идентификатора имеют переменную длину.
Кажется, что B-дерево является часто цитируемой структурой, но в основном для записей фиксированной длины. Я также ожидаю значительно большего количества загрузок и обновлений, чем вставляю и удаляю. Можно ли избавиться от поиска O (log m) B-дерева?
Я очень рад, что это комбинированная система, например, ISAM объединяет B-дерево и линейное хранилище файлов, которое выглядит так, будто его можно использовать для работы с записями переменной длины в качестве подхода. Есть ли что-то лучше?
Некоторые дополнительные ограничения:
1) Идентификаторы потенциально разрежены, но их можно создать в виде блоков линейных чисел, но в большом диапазоне (64 бита)
2) Я не хочу использовать СУБД, производительность для моей конкретной проблемы не очень хорошая. Мне не нужны никакие операции, которые использует полная СУБД, мне не нужен поиск. Мне нужно что-то, что я могу легко настроить и оптимизировать. Назовите это академическим любопытством, если MySQL его не использует, тогда я воспользуюсь им, но мне нужно постараться быстрее.
3) Набор данных больше, чем может поместиться в памяти, однако индекс может вполне уместиться в памяти, если его просто сместить как ключ. Я, конечно, смотрю что-то вроде 1 миллиарда или более объектов в хранилище.
4) В идеале пространство должно быть восстановлено при удалении записи. Это может быть с помощью сжатия, но мне интересно посмотреть, есть ли лучший способ (например, B-дерево легко восстанавливает пространство).