schimaytonDBMS умеет по другому. Он бъет сложным и универсальным ударом который
называется B+Tree. Это дерево. Но особое. Оптимизированное для дисковых
блочных операций. И разумеется оно нелетает без прослойки LRU-подобного
кеша блоков.

Первый раз такую трактовку слышу, про оптимизацию с дисками. Не поделитесь источником ?
1) Ваша постановка вопроса меня удивляет. Если вы из сегмента It - то вы должны были проходить
курс алгоритмы и структуры данных. Там - дают вводную по деревьям (красные-чорные, бинарные,
тернарные, АВЛ) и в том числе B+Tree, N-того порядка. Последние просто являются
частным случаем предыдущих деревьев при условии что группа узлов (Nodes)
объединяются в дисковый блок (2/4/8/16K) массив и все операции с узлами
делаются в рамках блока. Это дает оптимальное использование I/O.

Один из производителей DBMS их описывает так.
B-tree indexes are the standard index type. They are excellent for highly selective indexes (few rows correspond to each index entry) and primary key indexes. Used as concatenated indexes, a B-tree index can retrieve data sorted by the indexed columns.
Далее по ссылке отрисовывается вся внутренняя структура.

https://docs.oracle.com/database/122/CNCPT/indexes-and-index-organized-tables.htm#CNCPT88834

Детально об этом пишут разные писатели. Джонатан Льюис. Том Кайт.

Решение нашей задачи в рамках DBMS я вижу так:




Далее - наполняем этот справочник insert-ами и игнорируем ошибку ORA-00001. Отбрасываем дубли.

Profit.

2) По кешам.

Механизм кеша - это я сказал ниочом и обо всем. Практически все современные
DBMS используют разные варианты кешей. IBM DB2, Postgres e.t.c. А кто не использует
тот дурак и у того нет перформанса.

Поэтому моя фраза о кешах - это попадание пальцем в небо. Так-же как и
"Волга Впадает в Каспийское море".

schiНичего не понял. Кайта и Льюиса читал, с деревьями знаком несколько раньше, чем вышли книги Кайта и Льюиса же, и ни разу не слышал про оптимизацию использования деревьев с точки зрения ввода-вывода, поэтому и заитересовался.
Вся дисковая оптимизация для дисков старого поколения (магнитных) базируется
на уменьшении количества чтений и записей блоков (db_blocks). Сам по себе блок может
варьироваться от 512 байт до 64к. Это зависит от ОС и архитектуры. Поэтому
все структуры данных такие как таблицы и индексы бьются на блоки и читаются
и сериализуются кусками кратными блоку. Это считается ТруЪ для всех DBMS.

Я своё мнение кажется сказал в первом посте. Грузить в базу.

А все остальное в топика - это игры разума. И я поддерживаю их ради дискурса.

В продолжение топика. Для 150Гб файла в качестве метрики эффективности
алгоритма КМК мы должны брать за основу т.н. Full-Table-Scan (это в терминологии БД).

Или грубо говоря 1 проход чтением по нашему файлу. Full-File-Scan (если мы работаем
со своими самописными алгоритмами). Для краткости - FFS.

Я не имею ничего против оценки асимтотической сложности алгоритма но в нашем
случае инженерная интуиция мне подсказывает что, учитывая технические
характеристики диска нам будет очень важно сколько штук FFS мы отработаем
в течение исполнения алгоритма.

Как я уже говорил - ленточная сортировка - это сразу более чем несколько FFS.
Ванговать не буду. Это количество зависит от оперативы у вас на борту.

Aleksandr Sharahov, +1

Я тоже об этом думал. Но у меня была идея такая. Мы (к примеру) имеем не 1 а аж минимум 3 разных
алгоритма унификации большого толстого грёбаного файла (big-fat-ugly-file (BFUF)).

И во всех трех алгоритмах всегда присутствует первая фаза FFS. Что мы будем делать в эту фазу?
Сразу много всего.
- анализировать сведенья (число строк. средняя длина. количество уникальных на тек.момент,
гистограммы и прочие характеристики текста. Языки кодировки.)
- параллельно строить hash-table или другую структуру данных полезную для distinct of BFUF.
- если при параллельной постройке hash-table мы вышли за какие-то разумные границы
расходов памяти - то процесс анализа продолжаем до конца.

Alibek B.А удалять из середины 150ГБ файла несколько строк-дубликатов может быть накладно.

Всем заинтересованным.

Тема имеет логическое продолжение здесь Тяпничная унификация