Оптимизация B-дерева для численных in-memory индексов

Доклад описывает путь развития B-дерева, которое хранит численные типы для in-memory поисковых индексов рекламного движка ВКонтакте. Будет полезно как начинающим разработчикам, так и опытным программистам, потому что список оптимизаций состоит из базовых улучшений (SOO, key-stealing) и интересного алгоритма поиска в дереве, который основан на векторных инструкциях.

Расскажу, как реализовать поисковое дерево для численных типов, которое обладает производительностью хеш-таблицы и требует менее 5 байтов для хранения int32. Основной фокус работы — метод локализации внутри вершины B-дерева на основе декомпозиции ключей и использования SIMD, а также сокращение количества накладных расходов B-дерева.