Binary Search Tree (BST), also known as Binary sorting Tree, on the basis of Binary Tree, all nodes in the left subtree of any node must have values not greater than the root node, and all nodes in the right subtree of any node must have values not less than the root node.

Storing data in a binary tree is a common choice when quick lookups are needed, since the query time depends on the tree height and the average time complexity is O(LGN). However, in extreme cases, tree skew occurs, as shown in the figure below, where the binary tree degenerates into a linked list,



The time complexity is reduced to O(n).

To solve this problem, a balanced binary tree is introduced.

In contrast to AVL trees, red-black trees are not strictly balanced, but roughly balanced: just ensuring that the longest possible path from root to leaf is no more than twice as long as the shortest possible path. From the perspective of implementation, the biggest characteristic of red-black tree is that each node belongs to one of two colors (red or black), and the division of node color needs to meet specific rules (detailed rules are omitted). The following is an example of a red-black tree:

Compared with AVL tree, the query efficiency of red-black tree will be reduced, because the balance of the tree becomes worse and the height is higher (its longest path is twice that of the shortest path, but the height of the balanced tree is not more than 1, so the natural height will be higher and the query time will be longer). However, the removal efficiency of red-black trees is greatly improved because red-black trees also introduce color. When inserting or deleting data, only O(1) rotations and color changes are required to ensure basic balance, rather than O(LGN) rotations (at the time of deletion) as AVL trees do. In general, red-black trees have better statistical performance than AVL.

Therefore, in practical applications, AVL trees are used relatively little, while red-black trees are widely used. For example, TreeMap in Java uses red-black trees to store sorting key-value pairs; HashMap in Java8 uses linked lists + red-black trees to resolve hash collisions (linked lists when there are few conflicting nodes, red-black trees when there are many).

Red-black trees perform very well when the data is in memory (such as TreeMap and HashMap above). But in the case of data on secondary storage devices such as disks (such as databases such as MySQL), red-black trees are not good because they are still too tall. When data is on disk, disk I/O becomes the biggest performance bottleneck. The design goal should be to minimize the number of I/OS. The higher the tree height is, the more I/OS required for add, delete, modify, and query, which seriously affects the performance.

B+ tree is also a multi-path balanced search tree, which differs from B tree mainly in: Every node in the tree B (including the leaf node and the non-leaf nodes) real data are stored, only leaves of B + tree node storing the real data, the leaf nodes only store the key (so B + tree index of the leaf node can store more, final data on the leaf node, tree height is not high, the query efficiency is stable, Whatever data is queried is ultimately determined by the tree height, because the data is at the page byte point). In MySQL, the actual data may be the entire row (as in Innodb’s clustered index), the primary key of the row (as in Innodb’s secondary index), or the address of the row (as in MyIsam’s non-clustered index. MyIsam’s data and index are separate files. Not like InnoDB clustering index data all in one piece). Whereas a record in a B tree appears only once and does not repeat itself, a key in a B+ tree may repeat itself — either at a leaf or at a non-leaf node. The leaves of a B+ tree are linked by a bidirectional linked list. (Range lookup, while B-tree can only iterate) Non-leaf nodes in B-tree, the number of records is 1 less than the number of child nodes; The number of records in a B+ tree is the same as the number of child nodes. Therefore, compared with B tree, B+ tree has the following advantages: Fewer IO times: The non-leaf nodes of B+ tree only contain keys, not real data, so the number of records stored by each node is much more than that of B number (that is, order M is larger), so the height of B+ tree is lower, and fewer IO times are required for accessing. In addition, because there are more records stored per node, the principle of access locality is better utilized and the cache hit ratio is higher. More suitable for range query: when range query is carried out in B tree, the lower limit to be searched is found first, and then the middle order traversal of the B tree is carried out until the upper limit of the search is found; The range query of B+ tree only needs to traverse the linked list. More stable query efficiency: The query time complexity of A B tree is between 1 and tree height (recorded at the root and leaf nodes respectively), whereas the query complexity of a B+ tree is stable at tree height because all data is located at the leaf node. B+ trees also have a disadvantage: they take up more space because the keys are repeated. However, the spatial disadvantage is often acceptable compared to the performance advantage, so B+ trees are more widely used in databases than B trees.

Finally, we summarize the problems solved by all kinds of trees and the new problems: binary search tree (BST) : solve the basic problem of sorting, but because of the balance can not guarantee, may degenerate into a linked list; Balanced binary tree (AVL) : the problem of balance is solved by rotation, but the efficiency of rotation operation is too low. Red-black tree: By abandoning strict balance and introducing red-black nodes, the problem of low AVL rotation efficiency is solved. However, in disk and other scenarios, the tree is still too high and IO times are too many. B tree: the problem of too high tree is solved by changing binary tree to multi-path balanced search tree. B+ tree: On the basis of B tree, non-leaf nodes are transformed into pure index nodes that do not store data, further reducing the height of the tree; In addition, leaf nodes are linked into linked lists using Pointers, which makes range query more efficient.