Т-образное дерево
 | Эта статья в значительной степени или полностью опирается на один источник . ( июнь 2013 г. ) |
В информатике T -дерево — это тип двоичного дерева структуры данных , который используется базами данных в основной памяти , такими как Datablitz , eXtremeDB , MySQL Cluster , Oracle TimesTen и MobileLite.
T-дерево — это сбалансированная структура данных дерева индексов, оптимизированная для случаевгде и индекс, и фактические данные полностью хранятся в памяти, точно так же, как B-дерево представляет собой индексную структуру, оптимизированную для хранения на блочно-ориентированных вторичных устройствах хранения, таких как жесткие диски. Т-деревья стремятся получить преимущества в производительности от древовидных структур в памяти, таких как деревья AVL, избегая при этом больших накладных расходов на пространство хранения, которые являются общими для них.
Т-деревья не хранят копии индексированных полей данных внутри самих узлов индексного дерева. Вместо этого они используют тот факт, что фактические данные всегда находятся в основной памяти вместе с индексом, поэтому они просто содержат указатели на фактические поля данных.
Буква «Т» в Т-дереве относится к форме структур данных узла в исходной статье, в которой впервые был описан этот тип индекса. [1]
Структуры узлов [ править ]
Узел Т-дерева обычно состоит из указателей на родительский узел, левый и правый дочерние узлы, упорядоченный массив указателей данных и некоторые дополнительные управляющие данные. Узлы с двумя поддеревьями называются внутренними узлами , узлы без поддеревьев называются листовыми узлами , а узлы только с одним поддеревом называются полулистовыми узлами. Узел называется ограничивающим узлом для значения, если это значение находится между текущим минимальным и максимальным значением узла включительно.
Для каждого внутреннего узла существуют листовые или полулистовые узлы, которые содержат предшественника его наименьшего значения данных (называемого наибольшей нижней границей ) и узла, который содержит преемника наибольшего значения данных (называемого наименьшей верхней границей ). Листовые и полулистовые узлы могут содержать любое количество элементов данных от одного до максимального размера массива данных. Внутренние узлы сохраняют свою занятость между заранее определенным минимальным и максимальным количеством элементов.
Алгоритмы [ править ]
Поиск [ править ]
- Поиск начинается с корневого узла
- Если текущий узел является ограничивающим узлом для искомого значения, выполните поиск в его массиве данных. Поиск завершается неудачно, если значение не найдено в массиве данных.
- Если искомое значение меньше минимального значения текущего узла, продолжайте поиск в его левом поддереве. Поиск завершается неудачей, если нет левого поддерева.
- Если значение поиска больше максимального значения текущего узла, продолжайте поиск в его правом поддереве. Поиск завершается неудачей, если нет правильного поддерева.
Вставка [ править ]
- Найдите ограничивающий узел для нового значения. Если такой узел существует, то:
- проверьте, есть ли еще место в его массиве данных, если да, то вставьте новое значение и завершите
- если места нет, удалите минимальное значение из массива данных узла и вставьте новое значение. Теперь перейдите к узлу, содержащему наибольшую нижнюю границу узла, в который было вставлено новое значение. Если удаленное минимальное значение все еще помещается туда, добавьте его как новое максимальное значение узла, иначе создайте новый правый подузел для этого узла.
- Если ограничивающий узел не найден, вставьте значение в последний искомый узел, если оно все еще вписывается в него. В этом случае новое значение станет либо новым минимальным, либо максимальным значением. Если значение больше не подходит, создайте новое левое или правое поддерево.
Если был добавлен новый узел, возможно, потребуется перебалансировка дерева, как описано ниже.
Удаление [ править ]
- Найдите ограничивающий узел значения, которое нужно удалить. Если ограничивающий узел не найден, закончите.
- Если ограничивающий узел не содержит значения, завершите.
- удалить значение из массива данных узла
Теперь нам нужно различать по типу узла:
- Внутренний узел:
Если массив данных узла теперь содержит меньше минимального количества элементов, переместите наибольшее значение нижней границы этого узла в его значение данных. Выполните один из следующих двух шагов для полулиста или листового узла, из которого было удалено значение.
- Листовой узел:
Если это был единственный элемент в массиве данных, удалите узел. При необходимости перебалансируйте дерево.
- Полулистовой узел:
Если массив данных узла можно объединить с массивом данных его листа без переполнения, сделайте это и удалите листовой узел. При необходимости перебалансируйте дерево.
Вращение и балансировка [ править ]
Т-дерево реализуется поверх базового самобалансирующегося двоичного дерева поиска . В частности, в статье Лемана и Кэри описывается Т-дерево, сбалансированное как дерево AVL : оно выходит из равновесия, когда дочерние деревья узла различаются по высоте как минимум на два уровня. Это может произойти после вставки или удаления узла. После вставки или удаления дерево сканируется от листа до корня. При обнаружении дисбаланса один поворот дерева выполняется или пара поворотов, что гарантированно сбалансирует все дерево.
Когда в результате вращения во внутреннем узле количество элементов становится меньше минимального, элементы из нового дочернего узла(детей) узла перемещаются во внутренний узел.
Производительность и память [ править ]
Хотя Т-деревья когда-то широко использовались для баз данных в основной памяти из-за повышения производительности, последние тенденции для очень больших баз данных в основной памяти делают больший акцент на затратах на предоставление ресурсов. Поскольку современные системы баз данных NOSQL часто хранят триллионы записей, стоимость памяти для хранения даже одного индекса, включающего фактические значения, может превышать десятки или даже сотни терабайт.
См. также [ править ]
Другие деревья [ править ]
- B-дерево ( дерево 2–3 , дерево 2–3–4 , дерево B+ , B*-дерево , UB-дерево )
- Танцующее дерево
- Дерево слияния
- k -d дерево
- Октри
- Четырехдерево
- R-дерево
- Радикс-дерево
- Верхнее дерево
Ссылки [ править ]
- ^ Леман, Тобин Дж.; Кэри, Майкл Дж. (25–28 августа 1986 г.). Исследование структур индексов для систем управления базами данных основной памяти . Двенадцатая Международная конференция по очень большим базам данных (VLDB, 1986). Киото. ISBN 0-934613-18-4 .