Дисковые структуры данных, B-деревья, LSM-деревья и фрактальные деревья / Leif Walsh (Tokutek)

Приглашаем на конференцию HighLoad 2024, которая пройдет 2 и 3 декабря в Москве! Программа, подробности и билеты по ссылке: -------- HighLoad 2014 Презентация и тезисы: После долгого доминирования дисковой структуры данных для СУБД и файловых систем, B-деревья стали медленно вытесняться структурами данных, оптимизированными для операций записи, что позволяет ускорить обработку постоянно растущих объёмов данных. Для достижения этой цели некоторые методы оптимизации для операций записи (например, LSM-деревья) частично жертвуют производительностью запросов B-дерева. Фрактальное дерево представляет собой структуру данных, оптимизированную для операций записи, которая сочетает в себе производительность операций вставки при сохранении оптимальной производительности запросов B-дерева. Фрактальное дерево было создано под влиянием многих структур данных (таких, как буферные деревья репозиториев, B^ε деревья и т.д.), но по-настоящему соответствует определению такого дерева наша реализация в Tokutek. ...