Что такое триллион?

10^6 - это миллион
10^9 - это миллард
10^12 - это триллион

Если грубо - то это приставка тера-*. Тоесть если-бы структура была байтом - то мы-бы грубо выделили 1 терабайт.

Мне кажется вопрос упирается в действия ОС во время операции malloc(). Что она будет делать?
Тут наверное Windows/Linux будут идти по разной стратегии. И какие будут ограничения на фактическую
оперативку.

Возможно при таком объеме стоит посмотреть в memory-mapped API. Consern такой. Даже если
ты аллоцируешь 1 теребайт оперативы то вряд-ли ты в единый миг сможешь ее использовать.

Технически - я думаю это возможно.

По поводу того что у нас не malloc а vector.

Здесь есть нюансы. Я думаю имеет смысл делать
предварительное резервирование структур в штуках в конструкторе

https://en.cppreference.com/w/cpp/container/vector/vector

Потому-что динамический resize может быть расточительным в нашем кейсе.
Возможно в какой-то момент мы затребуем даже больше чем 1 Тера-количество
элементов. Сколько там он? В 1.5 или 1.2 или 2 раза? Я не помню.

Расскажи что у тебя лежит внутри этих структур. И может тебе надо не vector
а какую-то другую структуру данных для поиска.

Давайте эксперимент. Возьмем бесплатную DBMS (PG/MySQL).
Создатим табличку. С 1 полем типа Int.
Проиндексируем ее по этому полю. Загрузим миллиард чисел.
Последовательность. Имеем предварительно знание что любой индекс
баз данных класса B+Tree имее 3-4 уровня блоков. Тоесть максимум
за 4 дисковых операции он находит нужный ключ. Для старого магнитного
диска типа HDD время поиска любого сектора занимает в среднем 6 милисекунд.
(я промерял аж 5 своих SATA дисков и эти цифры правда такие. Я гарантирую.).

Тоесть любой ключ в этой таблице мы найдем за 6 * 4 = 24 милисекунды.
Это на старом жлобском магнином диске. Ну для твердотельных там будут
цифры получше.

И этот весь эксперимент не требует тера-штучного вектора. Обычная
база типа Postgres/MySQL.

Я так всегда делаю. В спорных технических вопросах даю готовое коробочное решение с цифрами.
Пускай даже прямое и деревянное. И дальше уже автор пускай обосновывает почему ему это
решение не подходит. И уже с цифрами.

На самом деле кеши поверх БД тоже строят. Вот сбербанк не просто построил а разработал
целый программный продукт в виде грида кешей и уже продает его отдельно. Но там - тоже
свои сложности. С invalidation.

Нет. Бд не работает так как ты рассказываешь.

2 All

Стоп гнать бочку на Алексея. Здесь мы обсуждаем вопрос а не персону.

(Перчатка Таноса жжот мне руку).


Ты затронул интересный и сложный вопрос. Я по нему могу говорить часами.

Но для начала. Давай просто сделаем такой confirm, что алгоритмы поиска на диске
в принципе ничем особо не отличаются по complexity от алгоритмов по оперативке.
Формула - таже самая. С логарифмом в основе. Тоже самое B+Tree дерево - это
сжатое в блоки бинарное дерево поиска.

Только надо сделать скидку на физическую организацию данных. И на то что seek time
это бич всех механических дисковых систем.

а причём тут сектор? откуда БД знает, в каком секторе лежит нужная строка??
она сначала будет ВСЕ строки с диска в память тащить, а потом в них будет искать нужную.
это и называется "кеширование".
Современные диски оперируют блоками (LBA), поэтому разумно действительно перейти на блоки.
Для большинства жестких дисков блок == 4 килобайта или 8 секторов по 512 байт.

Каким образом приложение может работать с блоками. Есть такой договорняк что все
файловые системы (NTFS/ext4/...etc) начинают свой файл на границе блока. Тоесть если ты открыл
файл в режиме RandomAccess и будешь делать seek по смещению кратному 4к
то диск при этом будет делать минимальное число операций (access path) для того
чтобы тебе предоставить данные. Разумеется режим открытия файла должен быть
соотвествующий (без буферизации). Здесь уже надо читать доки на API который ты используешь.
Далее - простая арифметика. Если твой индекс состоит из страниц равных 4к или 8к (Oracle by default)
тогда будет работать та формула которую я предложил выше.

Да милисекунды это долго. Дольше чем просто память. Но обычно все DBMS прогревают в кешах
корневые вершины индексов и если с индексом долго работать то в учет времени можно
брать уже листовые узлы.

Кстати ты до сих пор не рассказал свою задачу. Если мы ее будем знать то сумеем придумать
access path такой короткой длины чтобы оперативная память и диск работали в тандеме и находили
данные так быстро как только возможно.

Есть также альтернативные разработки (dbms Tarantool) которые улучшают даже B+Tree индекс.

Можем даже заниматься системной оптимизацией полнотекстового. Надо просто поставить задачу.

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

Там хранится ключ и указатель на физическое местоположение строки (RowId) в datafile.
Это для листовых узлов индекса. Для не-листовых - там линки на соседние блоки индекса.

Его формат немного отличается от указателя. Например Oracle хранит группу целых
чисел (номер файла, номер блока в файле (это тот самый 8к блок файловой системы),
и номер строки внутри блока). И дополнительно objectId. Это кажется надо для поддержки
кластеризованных таблиц.

Например. Фрагмент блока индекса.

(Я пишу в формате JSON чтоб было понятно. На самом деле там - RAW.)
keyrow_id (in JSON)mayton{ file=1, block=25, row=3, objId=... }Petro{ file=1, block=25, row=4, objId=... }........

В таблице есть блок номер 25 где лежат 2 строки проиндексированные по ключам mayton, Petro.

Понятно что file=1 это уже не файл где лежит индекс а файл где лежит индексируемая таблица.

Тоже работает. С точки зрения Oracle (например) - все индексы являются Unique по своей структуре данных.

Неуникальные там достигаются изменением алгоритма в плане оптимизатора. Как точно - я щас не помню
надо почитать. Дядка Том писал об этом.