Shady Minds

Oleksiy Dyagilev on computer science and related ..

Fractal Tree Indexes

Парни из 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 считают что в будущем все перейдут на фрактальные деревья как замена Б-деревьям. Детали алгоритма запатентованы.

Ссылки

Comments