kaipa | Фрактальные индексы

На предстоящем этой осенью Хайлоаде анонсирован доклад Leif Walsh из Tokutek, где он будет рассказывать о том, как фрактальные деревья помогают масштабировать индексы на примере TokuMX (это MongoDB с индексакцией на фрактальных индексах от Tokutek). Это преподносится как супер-прорыв. С одной стороны, это так и есть, обычные бинарные индексы масштабируются хреново, а хэш индексы не везде можно использовать. С другой -- я два года назад рассказывал на том же Хайлоаде, как работают фрактальные индексы в TokuDB (это расширение MySQL от Tokutek), и упоминал об этом в статье на Хабре, но никакого интереса это не вызвало. Разве что CEO Tokutek мне написал письмо с благодарностью за популяризацию (мы знакомы). Обидно, понимаешь. Вообще, доклад Лейфа Уолша, судя по аннотации, близок к моему прошлогоднему, где я рассказывал о распределенных базах данных для аналитики, только у него упор на горизонтальное масштабирование OLTP.

Для интересующихся, вкратце, проблемы с бинарными индексами следующие.
1) Скорость вставки (без балансировки) растет как log2N
2) Но без балансировки плохо, поэтому надо балансировать, что в худшем случае дорого (оценку не помню)
3) Удаление с балансировкой дорого
4) Поиск по дереву, если оно большое, плохо ложится на диск с последовательным чтением, то есть сегменты индекса могут быть раскиданы случайно. Из-за этого такие индексы приходится кэшировать целиком, иначе резко падает скорость. Для больших индексов плохо.

В целом, бинарные индексы нормально работают на не слишком большом объеме деревьев, но с ростом количества данных и размера индекса, производительность существенно падает. То есть индекс служит серьезным препятствием для масштабирования.

В компании Tokutek придумали и сделали так называемые индексы на фрактальных деревьев (фрактальные -- не от фракталов, а от fraction -- частей), которые свободны от перечисленных выше недостатков. Это несколько напоминает Log Structured Merge-Trees, но лучше. Как работает, можно понять из этой презентации.