- T-дерево
-
T-tree — сбалансированное дерево во внешней памяти, оптимизированное для случаев, когда востребованные (горячие) данные полностью хранятся в оперативной памяти. Данные хранятся в самих узлах дерева. Указатели переводят на следующий узел дерева.
T-деревья сами не хранят копии индексированных полей данных в своих вершинах. Вместо этого, они пользуются тем, что горячие данные всегда содержатся в памяти вместе со своим индексом. Таким образом, они просто содержат ссылки на эти горячие данные.
Структура узла T-дерева можно представить в следующем виде:
struct t_tree_node{ void* parent; void** data; /* сортированный массив указателей на данные */ void* control; /* дополнительные управляющие данные */ void* left_child; void* right_child; }
Литература
- Tobin J. Lehman and Michael J. Carey, A Study of Index Structures for Main Memory Database Management Systems. (англ.) (pdf). VLDB. Архивировано из первоисточника 22 апреля 2012. Проверено 2 апреля 2010.
Дерево (структура данных) Двоичное дерево поиска · Дерево (теория графов) · Древовидная структура Двоичные деревья Двоичное дерево · T-дерево Самобалансирующиеся двоичные деревья АА-дерево · АВЛ-дерево · Красно-чёрное дерево · Расширяющееся дерево · Дерево со штрафами · Декартово дерево · Дерево Фибоначчи B-деревья B-дерево · 2-3-дерево · B+ дерево · B*-дерево · UB-дерево · 2-3-4 дерево · (a,b)-дерево · Танцующее дерево Префиксные деревья Суффиксное дерево · Radix tree · Ternary search tree Двоичное разбиение пространства k-мерное дерево · VP-дерево Недвоичные деревья Дерево квадрантов · Октодерево · Sparse Voxel Octree · Экспоненциальное дерево · PQ-дерево Разбиение пространства R-дерево · R+-дерево · R*-дерево · X-дерево · M-дерево · Дерево Фенвика · Дерево отрезков Другие деревья Куча · TTH · Finger tree · Metric tree · Cover tree · BK-tree · Doubly-chained tree · iDistance · Link-cut tree Алгоритмы Поиск в ширину · Поиск в глубину · DSW-алгоритм · Алгоритм связующего дерева Категория:- Деревья (структуры данных)
Wikimedia Foundation. 2010.