T-дерево

T-дерево (англ. T-tree) — сбалансированное двоичное дерево, оптимизированное для случаев, когда востребованные («горячие») данные полностью хранятся в оперативной памяти. Используется многими резидентными СУБД, в том числе Datablitz^[англ.], ExtremeDB^[англ.], MySQL Cluster^[англ.], TimesTen^[англ.], MobileLite.

Структура узла 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. Дата обращения: 2 апреля 2010. Архивировано из оригинала 21 апреля 2012 года.