Индекс фрактального дерева

Индекс фрактального дерева
Тип	дерево
Изобретенный	2007
Изобретён	Майкл А. Бендер , Мартин Фарах-Колтон , Брэдли К. Кушмаул
Временная сложность в большой записи O Операция Средний Худший случай Поиск О (логарифм B N ) О (логарифм B N ) Вставлять O(log B N / B е ) O(log B N / B е ) Удалить O(log B N / B е ) O(log B N / B е ) Пространственная сложность Космос О( Н / Б ) О( Н / Б )

В информатике индекс фрактального дерева — это древовидная структура данных , которая обеспечивает сортировку данных и обеспечивает поиск и последовательный доступ за то же время, что и B-дерево , но с вставками и удалениями, которые асимптотически быстрее, чем B-дерево. Как и B-дерево, индекс фрактального дерева является обобщением бинарного дерева поиска , в котором узел может иметь более двух дочерних элементов. Кроме того, в отличие от B-дерева, индекс фрактального дерева имеет буферы в каждом узле, которые позволяют хранить вставки, удаления и другие изменения в промежуточных местах. Целью буферов является планирование записи на диск так, чтобы каждая запись выполняла большой объем полезной работы, тем самым избегая наихудшей производительности B-деревьев, в которых каждая запись на диск может изменить небольшой объем данных на диске. Как и B-дерево, индексы фрактального дерева оптимизированы для систем, которые читают и записывают большие блоки данных. Индекс фрактального дерева был коммерциализирован в базах данных компанией Tokutek . Первоначально он был реализован как массив опережающего просмотра без учета кэша. но текущая реализация является расширением B ^е дерево. Б ^е связано с деревом буферизованного репозитория. Дерево буферизованного репозитория имеет степень 2, тогда как B ^е дерево имеет степень B ^е . Индекс фрактального дерева также использовался в прототипе файловой системы . . с открытым исходным кодом Доступна реализация индекса фрактального дерева который демонстрирует детали реализации, изложенные ниже.

Обзор

В индексах фрактального дерева внутренние ( нелистовые ) узлы могут иметь переменное количество дочерних узлов в пределах некоторого заранее определенного диапазона. Когда данные вставляются или удаляются из узла, количество дочерних узлов изменяется. Чтобы поддерживать заранее заданный диапазон, внутренние узлы можно объединять или разделять. Каждый внутренний узел B-дерева будет содержать количество ключей, на один меньше, чем его коэффициент ветвления . Ключи действуют как значения разделения, которые делят его поддеревья . Ключи в поддеревьях хранятся в порядке дерева поиска , то есть все ключи в поддереве находятся между двумя значениями брекетинга. В этом отношении они похожи на B-деревья.

Индексы фрактального дерева и B-деревья используют тот факт, что при извлечении узла из хранилища блок памяти, размер которого обозначается $B$, извлекается. Таким образом, узлы настраиваются примерно на размер $B$. Поскольку доступ к хранилищу может доминировать над временем работы структуры данных, временная сложность алгоритмов внешней памяти во многом определяется количеством операций чтения/записи, вызываемых структурой данных. (См., например, для следующих анализов.)

В B-дереве это означает, что количество ключей в узле должно быть достаточным для заполнения узла с некоторой вариативностью при разделении и слиянии узлов. Для целей теоретического анализа, если $O(B)$ ключи помещаются в узел, тогда дерево имеет глубину $O(\log _{B}N)$, и это сложность ввода-вывода как для поиска, так и для вставки.

Узлы фрактальных деревьев используют меньший коэффициент ветвления, скажем, ${\sqrt {B}}$. Тогда глубина дерева $O(\log _{\sqrt {B}}N)=O(\log _{B}N)$, тем самым асимптотически сопоставляя B-дерево. Оставшееся пространство в каждом узле используется для буферизации вставок, удалений и обновлений, которые мы в совокупности называем сообщениями. Когда буфер заполнен, он массово сбрасывается дочерним элементам. Существует несколько вариантов очистки буферов, и все они приводят к одинаковой сложности ввода-вывода. Каждое сообщение в буфере узла будет передано конкретному дочернему элементу, как определено его ключом. Предположим, для конкретности, что сбрасываются сообщения, направляющиеся одному и тому же дочернему элементу, и что среди ${\sqrt {B}}+1$дети, мы выбираем того, у которого больше всего сообщений. Тогда есть как минимум ${\frac {B}{{\sqrt {B}}+1}}\approx {\sqrt {B}}$сообщения, которые могут быть отправлены дочернему элементу. Для каждой промывки требуется $O(1)$ сбросов, и, следовательно, стоимость сброса за одно сообщение равна $O\left({\frac {1}{\sqrt {B}}}\right)$.

Учитывайте стоимость внедрения. Каждое сообщение сбрасывается $O(\log _{B}N)$ раз, а стоимость промывки составляет $O\left({\frac {1}{\sqrt {B}}}\right)$. Таким образом, стоимость внедрения составляет $O\left({\frac {\log _{B}N}{\sqrt {B}}}\right)$. Наконец, заметим, что коэффициент ветвления может меняться, но для любого фактора ветвления $B^{\varepsilon }$, стоимость промывки равна $O\left({\frac {1}{B^{1-\varepsilon }}}\right)$, тем самым обеспечивая плавный компромисс между стоимостью поиска, которая зависит от глубины дерева поиска и, следовательно, коэффициента ветвления, и временем вставки, которое зависит от глубины дерева, но более чувствительно от размера очистки буфера.

Сравнение с другими индексами внешней памяти

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

B-деревья

Время поиска B-дерева асимптотически такое же, как и у индекса фрактального дерева. Однако индекс фрактального дерева имеет более глубокие деревья, чем B-дерево, и если бы каждый узел требовал ввода-вывода, скажем, если кеш холодный, то индекс фрактального дерева вызвал бы больше операций ввода-вывода. Однако для многих рабочих нагрузок большинство или все внутренние узлы как B-деревьев, так и индексов фрактального дерева уже кэшируются в оперативной памяти. В этом случае в стоимости поиска преобладает стоимость извлечения листа, которая в обоих случаях одинакова. Таким образом, для многих рабочих нагрузок индексы фрактальных деревьев могут соответствовать B-деревьям по времени поиска.

В чем они различаются, так это вставках, удалениях и обновлениях. Вставка в индекс фрактального дерева занимает $O\left({\frac {\log _{B}N}{\sqrt {B}}}\right)$ тогда как B-деревья требуют $O(\log _{B}N)$. Таким образом, индексы фрактальных деревьев быстрее, чем B-деревья, в два раза быстрее. $O({\sqrt {B}})$. С $B$может быть довольно большим, это дает потенциальное улучшение времени вставки в худшем случае на два порядка, что и наблюдается на практике. И B-деревья, и индексы фрактальных деревьев в лучшем случае могут выполнять вставку быстрее. Например, если ключи вставляются в последовательном порядке, обе структуры данных достигают $O\left({\frac {1}{B}}\right)$Операции ввода-вывода на каждую вставку. Таким образом, поскольку лучшие и худшие случаи B-деревьев сильно различаются, тогда как индексы фрактальных деревьев всегда близки к лучшему случаю, фактическое ускорение, которого достигают индексы фрактальных деревьев по сравнению с B-деревьями, зависит от деталей рабочей нагрузки.

Деревья слияния с лог-структурой

Деревья слияний с лог-структурой (LSM) относятся к классу структур данных, который состоит из двух или более индексных структур с экспоненциально растущей емкостью. Когда дерево на каком-то уровне достигает своей мощности, оно переходит на следующий, больший уровень. Сложность ввода-вывода LSM зависит от таких параметров, как коэффициент роста между уровнями и структура данных, выбранная на каждом уровне, поэтому для анализа сложности LSM нам нужно выбрать конкретную версию. В целях сравнения мы выбираем версию LSM, которая соответствует индексам фрактального дерева по производительности вставки.

Предположим, что LSM реализован через $O(\log _{B}N)$ B-деревья, каждое из которых имеет емкость, ${\sqrt {B}}$больше, чем его предшественник. Время слияния зависит от трех фактов: Отсортированного порядка ключей в $N$-B-дерево элементов может быть создано в $O\left({\frac {N}{B}}\right)$ИО; Два отсортированных списка $N$ и $M$ элементы можно объединить в отсортированный список в $O\left({\frac {N+M}{B}}\right)$ИО; и B-дерево отсортированного списка $N$ элементы могут быть встроены $O\left({\frac {N}{B}}\right)$ИО. Когда дерево переполняется, оно объединяется с деревом, размер которого равен $O({\sqrt {B}})$ больше, поэтому уровень, который держится $k$ предметы требуют $O\left({\frac {k}{\sqrt {B}}}\right)$IO для объединения. Предмет может быть объединен один раз за уровень, что дает общее время $O\left({\frac {\log _{B}N}{\sqrt {B}}}\right)$, что соответствует индексу фрактального дерева.

Время запроса — это просто время запроса B-дерева на каждом уровне. Время запроса в $i$^й уровень $O(\log _{B}B^{\frac {i}{2}})=O(i)$, поскольку $i$^й уровень имеет емкость $B^{\frac {i}{2}}$. Таким образом, общее время $O(\log _{B}^{2}N)$. Это в логарифмическом коэффициенте больше, чем индексы B-дерева и фрактального дерева. Фактически, хотя B-деревья и индексы фрактальных деревьев находятся на оптимальной кривой компромисса между вставками и запросами, LSM - нет. Они несравнимы с B-деревьями и в них преобладают индексы фрактальных деревьев.

Несколько замечаний о LSM: есть способы ускорить запросы. Например, если требуются только запросы на членство и нет запросов на преемника/предшественника/диапазона, то фильтры Блума для ускорения запросов можно использовать . Кроме того, коэффициент роста между уровнями может быть установлен на какое-то другое значение, что дает диапазон компромиссов вставки/запроса. Однако при каждом выборе скорости вставки соответствующий индекс фрактального дерева имеет более быстрые запросы.

Б ^е деревья

Индекс фрактального дерева — это уточнение B ^е дерево. Как Б ^е дерево, оно состоит из узлов с ключами и буферами и реализует оптимальный компромисс между вставкой и запросом. Индекс фрактального дерева отличается включением оптимизации производительности и расширением функциональности. Примеры улучшенной функциональности включают семантику ACID . Реализации семантики ACID в виде B-дерева обычно включают блокировку строк, участвующих в активных транзакциях. Такая схема хорошо работает в B-дереве, поскольку и вставки, и запросы требуют извлечения одного и того же листа в память. Таким образом, блокировка вставленной строки не влечет за собой штраф за ввод-вывод. Однако в индексах фрактального дерева вставки являются сообщениями, и строка может находиться более чем в одном узле одновременно. Поэтому индексам фрактального дерева требуется отдельная структура блокировки, которая эффективно использует ввод-вывод или находится в памяти, чтобы реализовать блокировку, необходимую для реализации семантики ACID.

Индексы фрактального дерева также имеют несколько оптимизаций производительности. Во-первых, буферы сами индексируются для ускорения поиска. Во-вторых, листья намного крупнее, чем у B-деревьев, что позволяет добиться большего сжатия. Фактически, листья выбираются достаточно большими, чтобы время их доступа определялось временем полосы пропускания и, следовательно, амортизировало задержку поиска и вращения. Большие листья являются преимуществом при запросах с большим диапазоном, но замедляют точечные запросы, которые требуют доступа к небольшой части листа. Решение, реализованное в индексах фрактального дерева, состоит в том, чтобы иметь большие листья, которые можно выбирать целиком для запросов быстрого диапазона, но разбивать на более мелкие части, называемые базовыми узлами, которые можно выбирать индивидуально. Доступ к подвальному узлу происходит быстрее, чем доступ к листу, из-за сокращения времени полосы пропускания. Таким образом, подструктура листьев в индексах фрактального дерева по сравнению с B ^е Деревья позволяют выполнять быстрые запросы как по диапазонам, так и по точкам.

Индексы сообщений и фрактального дерева

Вставки, удаления и обновления вставляются как сообщения в буферы, которые направляются к листьям. Инфраструктуру обмена сообщениями можно использовать для реализации множества других операций, некоторые из которых обсуждаются ниже.

Упсы

Upsert . — это оператор, который вставляет строку, если она не существует, и обновляет ее, если она существует В B-дереве upsert реализуется путем сначала поиска строки, а затем реализации вставки или обновления, в зависимости от результата поиска. Для этого необходимо загрузить строку в память, если она еще не кэширована. Индекс фрактального дерева может реализовать обновление, вставив специальное сообщение об обновлении. Такое сообщение теоретически может реализовать произвольные фрагменты кода во время обновления. На практике поддерживаются четыре операции обновления:

1. $x:={\text{constant}}$
2. $x:=x+{\text{constant}}$ (обобщенное приращение)
3. $x:=x-{\text{constant}}$ (обобщенный декремент)
4. $x:={\begin{cases}0&{\text{if }}x=0\\x-1&{\text{if }}x\neq 0\end{cases}}$ (декремент с нижней границей 0)

Они соответствуют операциям обновления, используемым в LinkBench. эталон, предложенный Facebook. Избегая первоначального поиска, сообщения upsert могут повысить скорость upsert на порядки.

Изменения в схеме

До сих пор все типы сообщений изменяли отдельные строки. Однако широковещательные сообщения, копируемые во все исходящие буферы, могут изменить все строки в базе данных. Например, широковещательные сообщения можно использовать для изменения формата всех строк в базе данных. Хотя общая работа, необходимая для изменения всех строк, не меняется по сравнению с методом грубой силы обхода таблицы, задержка улучшается, поскольку, как только сообщение будет введено в корневой буфер, все последующие запросы смогут применить модификацию схемы. ко всем строкам, с которыми они сталкиваются. Изменение схемы происходит немедленно, и работа откладывается до того момента, пока буферы не переполнятся и листья все равно обновятся.

Реализации

Индекс фрактального дерева был реализован и коммерциализирован компанией Tokutek . Он доступен как TokuDB в качестве механизма хранения для MySQL и MariaDB , а также как TokuMX — более полная интеграция с MongoDB . Индексы фрактального дерева также использовались в прототипах файловых систем TokuFS. и БетрФС.