T-tree

Key takeaways

T-tree belongs to science; place it in that map before memorising details.
Learn the definition first, then one example that makes the definition concrete.
Connect T-tree to a quantity you can measure, compute or draw — that is where exam questions come from.
Reproduce the core statement of T-tree from memory before moving on to harder problems.

Reference excerpt

In computer science a T-tree is a type of binary tree data structure that is used by main-memory databases, such as Datablitz, eXtremeDB, MySQL Cluster, Oracle TimesTen and MobileLite. A T-tree is a balanced index tree data structure optimized for cases where both the index and the actual data are fully kept in memory, just as a B-tree is an index structure optimized for storage on block oriented secondary storage devices like hard disks. T-trees seek to gain the performance benefits of in-memory tree structures such as AVL trees while avoiding the large storage space overhead which is common to them. T-trees do not keep copies of the indexed data fields within the index tree nodes themselves. Instead, they take advantage of the fact that the actual data is always in main memory together with the index so that they just contain pointers to the actual data fields. The 'T' in T-tree refers to the shape of the node data structures in the original paper which first described this type of index.

Node structures A T-tree node usually consists of pointers to the parent node, the left and right child node, an ordered array of data pointers and some extra control data. Nodes with two subtrees are called internal nodes, nodes without subtrees are called leaf nodes and nodes with only one subtree are named half-leaf nodes. A node is called the bounding node for a value if the value is between the node's current minimum and maximum value, inclusively.

For each internal node, leaf or half leaf nodes exist that contain the predecessor of its smallest data value (called the greatest lower bound) and one that contains the successor of its largest data value (called the least upper bound). Leaf and half-leaf nodes can contain any number of data elements from one to the maximum size of the data array. Internal nodes keep their occupancy between predefined minimum and maximum numbers of elements

Algorithms

Search Search starts at the root node If the current node is the bounding node for the search value then search its data array. Search fails if the value is not found in the data array. If the search value is less than the minimum value of the current node then continue search in its left subtree. Search fails if there is no left subtree. If the search value is greater than the maximum value of the current node then continue search in its right subtree. Search fails if there is no right subtree.

Insertion Search for a bounding node for the new value. If such a node exists then: check whether there is still space in its data array, if so then insert the new value and finish if no space is available then remove the minimum value from the node's data array and insert the new value. Now proceed to the node holding the greatest lower bound for the node that the new value was inserted to. If the removed minimum value still fits in there then add it as the new maximum value of the node, else create a new right subnode for this node. If no bounding node was found then insert the value into the last node searched if it still fits into it. In this case the new value will either become the new minimum or maximum value. If the value doesn't fit anymore then create a new left or right subtree. If a new node was added then the tree might need to be rebalanced, as described below.

Deletion Search for bounding node of the value to be deleted. If no bounding node is found then finish. If the bounding node does not contain the value then finish. delete the value from the node's data array Now we have to distinguish by node type:

Internal node: If the node's data array now has less than the minimum number of elements then move the greatest lower bound value of this node to its data value. Proceed with one of the following two steps for the half leaf or leaf node the value was removed from.

Leaf node: If this was the only element in the data array then delete the node. Rebalance the tree if needed.

Half leaf node: If the node's data array can be merged with its leaf's data array without overflow then do so and remove the leaf node. Rebalance the tree if needed.

Rotation and balancing A T-tree is implemented on top of an underlying self-balancing binary search tree. Specifically, Lehman and Carey's article describes a T-tree balanced like an AVL tree: it becomes out of balance when a node's child trees differ in height by at least two levels. This can happen after an insertion or deletion of a node. After an insertion or 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

Illustrations

Worked examples

Example 1 — a first encounter with T-tree

Start with the simplest possible case. Write down what T-tree claims or describes in one sentence, then invent the smallest concrete situation in which that sentence is true. In science, the smallest case is usually a single object, a single equation or a single measurement. Check that every symbol or term in your sentence has a meaning in that case.

Example 2 — changing one variable

Take the situation from Example 1 and change exactly one quantity: double it, halve it, or set it to zero. Predict what should happen to T-tree before you calculate. Comparing your prediction with the result is the fastest way to find out whether you understand the idea or only the words.

Example 3 — an exam-style question

Typical questions about T-tree ask you to (a) state it precisely, (b) apply it to given data, and (c) explain a limitation. Practise writing all three answers in under five minutes; the third part is what separates a full-mark answer from an average one.

Applications of T-tree

In research: T-tree appears in science research whenever the underlying quantities have to be modelled precisely. Papers usually cite it as a starting assumption and then explore where it breaks down.
In technology and industry: Engineering practice reuses T-tree in design rules, simulations and safety margins. Knowing the idea lets you read a specification sheet and understand why the numbers look the way they do.
In the classroom: T-tree is common in secondary-school and first-year university syllabi. It links to neighbouring topics Binary trees, Search trees, so understanding it makes those chapters shorter.
In everyday life: Look for T-tree outside the textbook — in sport, cooking, traffic, electronics or the sky above you. An example you found yourself is remembered far longer than one you were given.

How to study T-tree in 20 minutes

Read the reference excerpt below once, without taking notes.
Close the page and write down what T-tree means in your own words.
Compare your version with the excerpt and mark what you missed.
Work through the three examples above with pen and paper.
Explain T-tree out loud to somebody else — or to Teacher Smith in the lgStudy chat.

Frequently asked questions

What is T-tree in simple terms?

In computer science a T-tree is a type of binary tree data structure that is used by main-memory databases, such as Datablitz, eXtremeDB, MySQL Cluster, Oracle TimesTen and MobileLite. A T-tree is a balanced index tree data structure optimized for cases where both the index and the actual data are…

Why does T-tree matter?

Because it connects several science ideas at once: it gives you a definition you can apply, a quantity you can calculate, and a way to check whether a result is plausible.

How should I study T-tree?

Read the excerpt, restate it from memory, then work through the examples and applications listed on this page. The five-step study plan above takes about twenty minutes.

What does this page cover?

It gives you a compact reference excerpt plus original lgStudy explanations, examples, applications and study material on T-tree.