Глубокое погружение в дисковые структуры данных, B-деревья, LSM-деревья и фрактальные деревья

Leif Walsh (Tokutek)

После долгого доминирования дисковой структуры данных для СУБД и файловых систем, B-деревья стали медленно вытесняться структурами данных, оптимизированными для операций записи, что позволяет ускорить обработку постоянно растущих объёмов данных. Для достижения этой цели некоторые методы оптимизации для операций записи (например, LSM-деревья) частично жертвуют производительностью запросов B-дерева.
Фрактальное дерево представляет собой структуру данных, оптимизированную для операций записи, которая сочетает в себе производительность операций вставки при сохранении оптимальной производительности запросов B-дерева. Фрактальное дерево было создано под влиянием многих структур данных (таких, как буферные деревья репозиториев, B^ε деревья и т.д.), но по-настоящему соответствует определению такого дерева наша реализация в Tokutek.
Я дам вводную информацию о B-деревьях и LSM-деревьях, в общих чертах объясню, как работают фрактальные деревья, чем они отличаются от B-деревьев и LSM-деревьев, и как мы используем их преимущества в плане производительности – как в достаточно очевидных ситуациях, так и в довольно нетривиальных, для поддержки новых возможностей MySQL и MongoDB в TokuDB и TokuMX.