Т-образное дерево - T-tree

Для T-разветвления см. H дерево и Система повторяющихся функций.
Пример Т-дерева.

В Информатика а Т-образное дерево это тип двоичное деревоструктура данных что используется базы данных в оперативной памяти, Такие какДатаблиц, EXtremeDB, Кластер MySQL, Oracle TimesTen и MobileLite.

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

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

«T» в T-дереве относится к форме структур данных узлов в исходной статье, которая впервые описывала этот тип индекса.[1]

Узловые структуры

Узел T-дерева обычно состоит из указателей на родительский узел, левого и правого дочерних узлов, упорядоченного массива указателей данных и некоторых дополнительных управляющих данных. Узлы с двумя поддеревья называются внутренние узлы, узлы без поддеревья называются листовые узлыи узлы только с одним поддерево названы половина листа узлов. Узел называется ограничивающий узел для значения, если значение находится между текущим минимальным и максимальным значением узла включительно.

Связанные значения.

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

Алгоритмы

Поиск

  • Поиск начинается с корневого узла
  • Если текущий узел является ограничивающим узлом для значения поиска, выполните поиск в его массиве данных. Поиск завершается неудачей, если значение не найдено в массиве данных.
  • Если значение поиска меньше минимального значения текущего узла, продолжить поиск в его левом поддереве. Поиск не выполняется, если нет левого поддерева.
  • Если значение поиска больше максимального значения текущего узла, продолжайте поиск в его правом поддереве. Поиск не выполняется, если нет правильного поддерева.

Вставка

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

Если был добавлен новый узел, возможно, потребуется перебалансировать дерево, как описано ниже.

Удаление

  • Найдите ограничивающий узел значения, которое нужно удалить. Если ограничивающий узел не найден, закончите.
  • Если ограничивающий узел не содержит значения, закончите.
  • удалить значение из массива данных узла

Теперь нужно различать по типу узла:

  • Внутренний узел:

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

  • Листовой узел:

Если это был единственный элемент в массиве данных, удалите узел. При необходимости измените баланс дерева.

  • Половинчатый узел:

Если массив данных узла можно объединить с массивом данных его листа без переполнения, сделайте это и удалите узел листа. При необходимости измените баланс дерева.

Вращение и балансировка

T-дерево реализуется поверх базового самобалансирующееся двоичное дерево поиска В частности, статья Лемана и Кэри описывает Т-дерево, сбалансированное как AVL дерево: он выходит из равновесия, когда дочерние деревья узла различаются по высоте как минимум на два уровня. Это может произойти после вставки или удаления узла. После вставки или удаления дерево сканируется от листа к корню. обнаружен дисбаланс, один вращение деревьев либо выполняется пара вращений, что гарантированно уравновешивает все дерево.

Когда вращение приводит к тому, что внутренний узел имеет меньше минимального количества элементов, элементы из нового дочернего (ren) узла перемещаются во внутренний узел.

Производительность и хранилище

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

Смотрите также

Другие деревья

Рекомендации

  1. ^ Lehman, Tobin J .; Кэри, Майкл Дж. (25–28 августа 1986 г.). Исследование структур индексов для систем управления базами данных с основной памятью. Двенадцатая международная конференция по очень большим базам данных (VLDB 1986). Киото. ISBN  0-934613-18-4.

внешняя ссылка