Войти
Пример Т-дерева. В информатике Т-дерево - это тип двоичного дерева структуры данных, который используется базами данных в основной памяти, например Datablitz, EXtremeDB, MySQL Cluster, Oracle TimesTen и MobileLite.
T-дерево - это сбалансированная структура данных дерева индексов, оптимизированная для случаев, когда и индекс, и фактические данные полностью хранятся в памяти, точно так же, как B-дерево - это структура индекса, оптимизированная для хранения на вторичных устройствах хранения, ориентированных на блоки, таких как жесткие диски. T-деревья стремятся получить преимущества в производительности древовидных структур в памяти, таких как деревья AVL, избегая при этом больших накладных расходов на дисковое пространство, которые являются общими для них.
T-деревья не хранят копии индексированных полей данных внутри самих узлов индексного дерева. Вместо этого они используют тот факт, что фактические данные всегда находятся в основной памяти вместе с индексом, поэтому они просто содержат указатели на фактические поля данных.
'T' в T-дереве относится к форме структур данных узла в исходной статье, которая впервые описывала этот тип индекса.
Узел T-дерева обычно состоит из указателей на родительский узел, левого и правого дочерних узлов, упорядоченного массива указателей данных и некоторых дополнительных управляющих данных. Узлы с двумя поддеревьями называются внутренними узлами, узлы без поддеревьев называются листовыми узлами, а узлы только с одним поддеревом называются полулистовыми узлами. Узел называется ограничивающим узлом для значения, если значение находится между текущим минимальным и максимальным значением узла включительно.
Связанные значения. Для каждого внутреннего узла существуют листовые или полулистовые узлы, которые содержат предшественник его наименьшего значения данных (называемый наибольшей нижней границей) и один, который содержит преемника его наибольшего значения данных (называемый наименьшая верхняя граница). Листовые и полулистовые узлы могут содержать любое количество элементов данных от одного до максимального размера массива данных. Внутренние узлы сохраняют свою занятость между предопределенными минимальным и максимальным количеством элементов
Если был добавлен новый узел, возможно, потребуется перебалансировать дерево, как описано ниже.
Теперь мы должны различать по тип узла:
Если в массиве данных узла теперь меньше минимального количества элементов, переместите наибольшее значение нижней границы этого узла в его значение данных. Выполните один из следующих двух шагов для половины листа или листового узла, из которого было удалено значение.
Если это был единственный элемент в массиве данных, удалите узел. При необходимости измените баланс дерева.
Если массив данных узла может быть объединен с массивом данных его листа без переполнения, тогда сделайте это и удалите листовой узел. При необходимости измените баланс дерева.
T-дерево реализовано поверх базового самобалансирующегося двоичного дерева поиска. В частности, статья Лемана и Кэри описывает T-дерево, сбалансированное как AVL-дерево : оно выходит из равновесия, когда дочерние деревья узла различаются по высоте как минимум на два уровня. Это может произойти после вставки или удаления узла. После вставки или удаления дерево просматривается от листа до корня. При обнаружении дисбаланса выполняется одно вращение дерева или пара вращений, что гарантированно уравновешивает все дерево.
Когда вращение приводит к тому, что внутренний узел имеет меньше минимального количества элементов, элементы из нового дочернего (ren) узла перемещаются во внутренний узел.
Хотя T-деревья когда-то широко использовались для баз данных в основной памяти из-за повышения производительности, последние тенденции для очень больших баз данных в основной памяти делают больший акцент на стоимости выделения ресурсов. В современных системах баз данных NOSQL, часто хранящих триллионы записей, стоимость памяти для хранения даже одного индекса, включающего фактические значения, может превышать десятки или даже сотни терабайт.
