Indexing is the process of associating a key with the location of the corresponding data record in the database. There are many data indexing structures used in NoSQL databases. B-Tree is one of the most common index structures in a DBMS. In it, internal nodes can have a variable number of children within a certain range.
One of the main differences from other tree structures, such as AVL, is that B-Tree allows for a variable number of children, which means less tree balancing but more space wastage. B+Tree is one of the most popular variants of B-trees. This improvement (unlike B-Tree) requires all keys to be in a leaf.
The T-Trees data structure was developed by combining the features of AVL Trees and B-Trees. AVL trees are a type of self-balancing binary search trees, while B-Trees are unbalanced, and each node can have a different number of children.
The structure of a T-tree is very similar to an AVL-tree and a B-tree. Each node stores a tuple {key-value, pointer}. In addition, binary search is used in combination with multiple nodes and tuples to provide better memory and performance.
A T-tree has three types of nodes: a node with right and left children, a terminal node with no children, and a half-leaf node with only one child. T-Trees are considered to have better overall performance.