T-tree

T-tree ( English T-tree ) - balanced binary tree , optimized for cases when the requested (hot) data is completely stored in RAM. Used by in -memory databases : Datablitz , EXtremeDB , MySQL Cluster , Oracle TimesTen and MobileLite.

The structure of the T-tree node can be represented as follows:

  struct t_tree_node
 {
     void * parent ;
     // sorted array of data pointers
     void ** data ;
     // additional control data
     void * control ;
     void * left_child ;
     void * right_child ;
 }