Парни из Tokutek реализовали engine TokuDB для MySQL как замену InnoDB, улучшив производительность операций вставки, запросов и компрессии. В основе индекса лежит так называемое Fractal Tree.
Посмотрим за счет чего достигается скорость вставки и поиска по сравнению с классическим B-tree.
Асимптотическая оценка
Необходимо оговориться, что мы рассматриваем случай когда индекс хранится на диске, а не в памяти. Поэтому нас интересует оценка количества операций IO, а не операций CPU. Операции CPU занимают ничтожно малое время по сравнению с IO.
Вставка:
B-tree O((log N)/(log B))
Fractal-tree O((log N)/(B^(1-k)))
Поиск:
B-tree O((log N)/(log B))
Fractal-tree O((log N)/(log (k*B^(1-k)))
где B - размер IO блока
Итак, упрощенный вариант Fractal Tree:
log Nмассивов размером2^i- каждый массив или полностью пустой или полностью заполнен
- каждый массив отсортирован
Вставка
Начинаем сверху. Смотрим на верхний массив размером 1. Если он пустой - кладем туда элемент. Иначе вынимаем элемент и сортируем с данным во временом массиве. Спускаемся вниз к массиву размером 2. Если он пустой - кладем туда нашу пару. Если нет - мержим их с временным массивом. Так как оба массива отсортированы, то делаем ето за O(X), где X ето длина массива. По сути ето операция merge из merge-сортировки.
Амортизированное время вставки занимает O((log N)/B), хотя в худшем случае вставка одного элемента может повлечь за собой перезапись огромного количества данных по цепочке. Чтобы избежать пиков с длительным ответом TokuDB порождает отдельный поток для вставки, ответ для клиента возвращается немедленно.
Поиск
проходимся по массивам, в кажом массиве используем бинарный поиск. Итого - O((log N)^2). Это медленнее чем B-tree. Как это можно ускорить?
Идея состоит в том, чтобы во время поиска в очередном массиве использовать некоторую информацию из поиска предыдущего массива. И так по цепочке. А информация следующая - каждый элемент массива хранит ссылку на его ‘виртуальное’ место в следующем массиве. Называется ето fractional cascading.
Итого, log N массивов, константное время на каждом массиве дает O(log N).
В целом товарищи из Tokutek считают что в будущем все перейдут на фрактальные деревья как замена Б-деревьям. Детали алгоритма запатентованы.