deletion, the tree is scanned from the leaf to the root. If an imbalance is found, one tree rotation or pair of rotations is performed, which is guaranteed to balance the whole tree. When the rotation results in an internal node having fewer than the minimum number of items, items from the node's new child(ren) are moved into the internal node. Performance and Storage Although T-trees were once widely used for main-memory databases because of performance benefits, recent trends for very large main-memory databases put more emphasis on provisioning cost. With modern NOSQL database systems often storing trillions of records, the memory cost to store even a single index that includes actual values can exceed tens or even hundreds of terabytes. See also Tree (graph theory) Tree (set theory) Tree structure Exponential tree Other trees B-tree (2-3 tree, 2-3-4 tree, B+ tree, B*-tree, UB-tree) Dancing tree Fusion tree k-d tree Octree Quadtree R-tree Radix tree Top tree References External links Oracle TimesTen FAQ entry on index mentioning T-Trees Oracle Whitepaper: Oracle TimesTen Products and Technologies DataBlitz presentation mentioning T-Trees An Open-source T*-tree Library Binary trees Search trees