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

Эта статья поднимает множество проблем. Пожалуйста, помогите улучшить его или обсудите эти проблемы на странице обсуждения . ( Узнайте, как и когда удалить эти сообщения-шаблоны ) Тема этой статьи может не соответствовать общему руководству Википедии о известности . Пожалуйста, помогите продемонстрировать значимость темы, цитируя надежные вторичные источники , не зависящие от темы и обеспечивающие значительное ее освещение, помимо банального упоминания. Если не удается показать известность, вероятно, статья будет объединена , перенаправлена или удалена . Найти источники:  «Индекс фрактального дерева»  -  новости  · газеты  · книги  · ученый  · JSTOR ( апрель 2014 г. ) (Узнайте, как и когда удалить этот шаблон сообщения ) Один из основных авторов этой статьи, кажется, имеет тесную связь с ее предметом. Может потребоваться очистка для соответствия политике содержания Википедии, особенно нейтральной точки зрения . Пожалуйста, обсудите дальше на странице обсуждения . ( Апрель 2014 г. ) ( Узнайте, как и когда удалить этот шаблон сообщения ) ( Узнайте, как и когда удалить этот шаблон сообщения )

В информатике , фрактал индексное дерево представляет собой структуру данных дерева , которая хранит данные сортируются и позволяет осуществлять поиск и последовательный доступ в то же время как B-дерева , но с вставками и удалений, которые асимптотически быстрее , чем B-дерева. Как и B-дерево, индекс фрактального дерева является обобщением бинарного дерева поиска.в этом узле может быть более двух дочерних элементов. Кроме того, в отличие от B-дерева, индекс фрактального дерева имеет буферы в каждом узле, что позволяет сохранять вставки, удаления и другие изменения в промежуточных местах. Буферы предназначены для планирования записи на диск, чтобы каждая запись выполняла большой объем полезной работы, тем самым избегая наихудшей производительности B-деревьев, когда каждая запись на диск может изменять небольшой объем данных на диске. Как и B-дерево, индексы фрактального дерева оптимизированы для систем, которые читают и записывают большие блоки данных. Фрактал дерево индекса было коммерчески в базах данных по Tokutek . Первоначально он был реализован как опережающий массив без учета кеша ^[1], но текущая реализация является расширением B^ε дерево. ^[2] B ^ε связано с деревом буферизованного репозитория. ^[3] Буферизованное дерево репозитория имеет степень 2, тогда какдеревоB ^ε имеет степень B ^ε . Индекс фрактального дерева также использовался в прототипе файловой системы . ^{[4] [5]} с открытым исходным кодом реализация фрактального индекса дерева доступна, ^[6] , который показывает деталь реализацииописанную ниже.

Обзор [ править ]

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

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

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

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

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

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

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

B-деревья [ править ]

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

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

Лог-структурированные деревья слияния [ править ]

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

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

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

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

B ^ε деревья [ править ]

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

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

Обмен сообщениями и индексы фрактального дерева [ править ]

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

Upserts [ править ]

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

1. х = константа
2. x = x + константа (обобщенное приращение)
3. x = x - константа (обобщенный декремент)
4. x = if (x = 0, 0, x-1) (декремент с полом в 0)

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

Изменения схемы [ править ]

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

Реализации [ править ]

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

Ссылки [ править ]