Надо сохранить массив (список) строк. В массиве может лежать крайне дохрена таких элементов (строк), т.е. например 100 млрд строк. Длина одной строки - рандом, но уже разумный - например 1…2000 символов. Т.е. наш массив имеет такой вид: [‘ab’, ‘zuzuzu’, ‘S’, …, ‘hehebububu’] (и это всё длиной 100 млрд).
Хочется:
- Быстрый доступ по индексу, т.е. по смещению: «дай 5-млрдный элемент». Доступ как к 1 элементу, так и к подмассиву («дай 100 элементов со смещения 52 млрд»).
- Быстрая, но можно уже чуть медленнее, вставка в любое место. В середину, например. Не перезапись, а именно вставка - т.е. если вставил в середину, то значит подвинул всё после места вставки на 1 и вставил в новое место, а длина списка выросла на 1.
- Быстрое удаление из любого места. Почти то же, что (2).
Требования (2) и (3) как-бы подразумевают, что если я воткнул строку по индексу «5 млрд», то все элементы, лежавшие после него должны теперь переехать в следующие по нумерации квартиры на единицу. ВСЕ ПЕРЕЕХАТЬ! Т.е. элемент, лежавший ранее по индексу 10 млрд теперь будет лежать по индексу (10 млрд + 1). За идею «давайте сделаем 95 млрд изменений в памяти или на диске» - сразу расстрел.
В память оно не влезет. Памяти у нас 2 гига, хаха. Т.е. надо как-то хранить всю эту байду на диске. На длинах массива порядка миллиардов цена доступа к любому элементу такого массива должна быть не выше чем 3-4 движения головы диска, т.е. это число обращений к нему. Т.е. всё должно лежать на диске не хуже, чем бы оно лежало в B+-Tree, если бы мы все элементы списка положили в виде key=value пар виде (elem1=string, elem2=string). С вариантом «куча key=value» не взлетит потому, что вас расстреляют при попытке переименовать все 95 млрд ключей, поменяв у них циферку в конце при вставке на позицию «5 млрд». Положить кучу key=value так, чтобы value было блоком строк - уже лучше, но всё равно на порядках сотен миллиардов придётся переименовывать овердофига ключей, трогая явно не 3-4 блока.
Варианты?
P.S.:
Пример применения: хранить очень длинный чатик или лог открытия ворот. Просматривалка с доступом через пагинацию. Нас не интересует время события, нас интересуют все 50 событий на странице номер 500 тыс.
Удаление или вставка в середину иногда нужна, но редко. Например дропнуть пачку флуда или добавить некий служебный евент.
Хранить на диске желательно так, чтобы все события открывания ворот лежали вплотную, чтобы машин лернинг при обработке всего миллиарда событий физически прочитал как можно меньше блоков данных, не перешагивая через другие события.
