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