История изменений

Вариант для лога/чата: Храним на диске кучу файлов в любом формате, позволяющем отделять записи друг от друга. Имена файлов выбираем так, чтобы их порядок соответствовал порядку индексов строк в них. В памяти храним структуру, содержащую количество строк в каждом файле и всех предыдущих. Способ разделения строк по файлам выбираем исходя из баланса размера файлов и их количества (чтоб структура влезла в память). Например, в одном файле все записи за день. Требование не перемещать все данные при вставке в середину и требование строкам с соседними индексами лежать рядом явно противоречат друг другу, оставляем только первое (ну или дефрагментировать ФС перед запуском машин лернинга). Далее под размером файла подразумевается количество строк в нем.

1. Поиск по индексу: идем по структуре бинарным поиском пока не найдем нужный файл. Идем по файлу, пока не найдем нужный индекс. Сложность - логарифм от количества файлов + линейная от размера файла.
2. Вставка по индексу - идем по структуре, пока не найдем нужный файл, идем по файлу, пока не найдем нужную позицию, сдвигаем хвост, вставляем строку. Обновляем структуру в памяти. Сложность линейная от количества файлов плюс линейная от размера файла.
3. Удаление аналогично вставке.

Поиск по файлу можно ускорить, если дополнительно генерировать индекс, но это замедлит вставку.

Вариант для лога/чата: Храним на диске кучу файлов в любом формате, позволяющем отделять записи друг от друга. Имена файлов выбираем так, чтобы их порядок соответствовал порядку индексов строк в них. В памяти храним структуру, содержащую количество строк в каждом файле и всех предыдущих. Способ разделения строк по файлам выбираем исходя из баланса размера файлов и их количества (чтоб структура влезла в память). Например, в одном файле все записи за день. Требование не перемещать все данные при вставке в середину и требование строкам с соседними индексами лежать рядом явно противоречат друг другу, оставляем только первое (ну или дефрагментировать ФС перед запуском машин лернинга).

1. Поиск по индексу: идем по структуре бинарным поиском пока не найдем нужный файл. Идем по файлу, пока не найдем нужный индекс. Сложность - логарифм от количества файлов + линейная от размера файла.
2. Вставка по индексу - идем по структуре, пока не найдем нужный файл, идем по файлу, пока не найдем нужную позицию, сдвигаем хвост, вставляем строку. Обновляем структуру в памяти. Сложность линейная от количества файлов плюс линейная от размера файла.
3. Удаление аналогично вставке.

Поиск по файлу можно ускорить, если дополнительно генерировать индекс, но это замедлит вставку.