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.