What is the function of B + tree index in MySQL

This article is to share with you about the role of the B+ tree index in MySQL, the editor thinks it is very practical, so I share it with you to learn. I hope you can get something after reading this article.

A brief introduction to trees

A brief introduction to trees

Trees, like arrays, linked lists, and stacks, are data structures. It consists of a limited number of nodes to form a set with hierarchical relations. It gets its name because it looks like a tree. An ordinary tree is as follows:

A tree is a finite set with n (n is an integer, greater than 0) nodes and 1 edge of n Murray. It has the following characteristics:

Each node has either no child nodes or only a limited number of child nodes

There is a special node that has no parent node, which is called the root node.

Each non-root node has one and only one parent node

There is no loop in the tree.

There are some concepts about trees:

Degree of a node: the number of sub-nodes contained in a node is called the degree of the node.

Degree of a tree: in a tree, the degree of the largest node is called the degree of the tree.

Parent node: if a node contains a child node, the node is called the parent node of its child node

Depth: for any node n, the depth of n is the only path from root to n, and the depth of root node is 0.

Height: for any node n, the height of n is the longest path from n to a leaf, and the height of all leaves is 0.

The types of trees

According to order, it can be divided into ordered tree and unordered tree:

Unordered tree: there is no sequential relationship between the child nodes of any node in the tree

Ordered tree: there is a sequential relationship between the children of any node in the tree.

According to the number of subtrees contained in nodes, they can be divided into B-trees and binary trees, and binary trees can be divided into the following categories:

Binary tree: a tree with at most two subtrees per node is called a binary tree

Binary search tree: first of all, it is a binary tree. If the left subtree is not empty, the value of all nodes on the left subtree is less than that of its root node; if the right subtree is not empty, the value of all nodes on the right subtree is greater than that of its root node; the left and right subtrees are also binary sorting trees.

Full binary tree: a tree in which all nodes except leaf nodes contain two subtrees is called full binary tree

Complete binary tree: if a binary tree except the last layer of nodes is a full binary tree, and the nodes of the last layer are distributed from left to right in turn

Hoffman tree: the binary tree with the shortest weighted path.

Red-black tree: the red-black tree is a special binary search tree. Each node is black or red, and the root node and leaf node are black. If a node is red, its child nodes must be black.

Balanced binary tree (AVL): the absolute value of the height difference between an empty tree or its left and right subtrees is not more than 1, and both left and right subtrees are a balanced binary tree.

Brief introduction of B-Tree and B + Tree

Brief introduction of B-tree

B-tree, also known as B-tree, is a balanced multi-fork tree (you can compare the balanced binary search tree), it is more suitable for external search. Take a look at these concepts:

Degree: the maximum number of child nodes in a node. (usually denoted by the letter m)

Keyword: the numerical value on the node is the keyword

Degree: the number of child nodes that a node has.

A B-tree of order m has the following characteristics:

The root node has at least two children.

The number of keywords contained in each non-root node j satisfies: ⌈ mplink 2 ⌉-1