Индекс фрактального дерева
-
Фрактальный древовидный индекс
- Древовидная структура данных для сортировки и поиска данных
- Обеспечивает асимптотически более быстрые вставки и удаления по сравнению с B-деревом
- Имеет буферы в каждом узле для оптимизации производительности
-
Сравнение с B-деревом
- Время поиска асимптотически такое же
- Вставки в фрактальное дерево быстрее, чем в B-дерево
- Вставки в последовательном порядке достигают O(1/B) ввода-вывода
-
Логарифмически структурированные деревья слияния
- Состоят из нескольких индексных структур с экспоненциально растущей емкостью
- Время слияния зависит от порядка сортировки и структуры данных
- Время запроса больше, чем у B-деревьев и фрактальных деревьев
-
Быть деревьями
- Усовершенствование дерева Be
- Включает оптимизацию производительности и расширенную функциональность
- Примеры улучшенной функциональности включают семантику ACID
-
Реализация семантики ACID в B-дереве
- Блокировка строк, участвующих в активных транзакциях
- Вставки и запросы предполагают выборку одного и того же листа в память
- Блокировка не приводит к штрафу за ввод-вывод
-
Индексы фрактального дерева
- Вставки являются сообщениями, строка может находиться в нескольких узлах одновременно
- Требуется отдельная структура блокировки для ввода-вывода или памяти
- Буферы индексируются для ускорения поиска
- Листья крупнее, что позволяет добиться большего сжатия
- Большие листья разбиты на базовые узлы для быстрого доступа
-
Индексы обмена сообщениями и фрактального дерева
- Вставки, удаления и обновления вставляются в буферы
- Инфраструктура обмена сообщениями может использоваться для других операций
-
Upsert в индексах фрактального дерева
- Upsert реализуется путем вставки специального сообщения
- Поддерживаются четыре операции обновления
- Отказ от первоначального поиска увеличивает скорость повторной отправки
-
Изменения в схеме
- Широковещательные сообщения изменяют все строки в базе данных
- Изменение схемы происходит немедленно, работа откладывается до переполнения буферов
-
Реализации
- Индекс фрактального дерева внедрен и коммерциализирован компанией Tokutek
- Доступен как TokuDB для MySQL и MariaDB, TokuMX для MongoDB
- Использовался в прототипах файловых систем TokuFS и BetrFS