Прикладная эзотерика Бэкенд, теория программирования

Доклад принят в программу конференции
Андрей Аксенов
Авито, Sphinx

Пишет код на всём подряд, показывает другим, как. В удачные дни код удается сносить, это обязательно показывает другим и заставляет "точно так же" втройне сильнее. Всю сознательную жизнь из этого выходят разные движки, прямо проклятие какое-то.

Тезисы

Из фундаментальных структур данных ежедневно любой разработчик вообще чего угодно — от нехитрого микросервиса до хитрого ядра ОС — использует максимум две: вектор и хэш. Что, в принципе, нормально. Слышал еще про полторы-три (списки, множества, деревья и т.п.). И на этом методичка обычно заканчивается полностью.

А рассказать хочется про совершенно другие структуры данных.

Существует несколько СД, которые немного сложнее и интереснее вектора; вполне себе практически применимы; но при этом в среднем (среднем!) скорее неизвестны. Heaps, tries, B-trees/LSMs, Bloom filters, CountMin + HyperLogLog, KLL + T-digest. А ещё для как бы стандартных СД существуют всякие интересные реализации или техники. И тоже вполне практически применимые. Judy arrays, parallel_hashmap, google/btree, facebook/rocksdb.

Вот про эти прикладные эзотерические СД и/или реализации и хочется хотя бы обзорно рассказать, что в природе ещё есть. Какие (нечастые, зато интересные) задачи может помочь решать и с какими ходовыми характеристиками. И если времени (уже в коридоре) хватит, как хотя бы в очень общих чертах чего устроено внутри.

Другие доклады секции Бэкенд, теория программирования