Экзотические функциональные структуры данных: деревья автостопщика — Дэвид Гринберг

Функциональные структуры данных — это потрясающе: они лежат в основе многих функциональных языков программирования, позволяя нам выражать сложную логику неизменяемо и эффективно. Однако есть одно досадное ограничение: эти структуры данных должны помещаться в кучу, ограничивая время их жизни временем работы процесса. Несколько лет назад появилась Datomic — первая функциональная база данных, которая решает эту проблему. Тем не менее, в области масштабируемых (от гигабайтов до терабайтов) функциональных структур данных не наблюдается особой активности. В этом докладе мы сначала рассмотрим некоторые фундаментальные принципы функциональных структур данных, в частности, деревьев. Затем мы рассмотрим, что такое B-дерево и почему оно лучше других деревьев для хранения данных. После этого мы узнаем об интересном варианте B-дерева, называемом фрактальным деревом, как его можно сделать функциональным и почему оно обладает феноменальной производительностью. Наконец, мы объединим эти концепции, чтобы понять дерево Hitchhiker — функционально персистентное фрактальное дерево с открытым исходным кодом. Мы также кратко рассмотрим пример API для использования деревьев Hitchhiker, который позволяет хранить состояние вашего приложения вне кучи, в духе статьи 2014 года "Быстрый перезапуск баз данных в Facebook".