The index

An Index is a data structure that helps MySQL obtain data efficiently.

As we know, database query is one of the most important functions of database. We all want to query data as fast as possible, so the designer of the database system optimizes it from the perspective of the query algorithm. Linear Search is the most basic query algorithm, of course. This algorithm of O(n) complexity is obviously bad when there is a large amount of data. Fortunately, the development of computer science provides many better search algorithms. For example, binary search, binary tree search and so on. If slightly analysis will find that each search algorithm can only be applied to a specific data structure, such as binary search request was to retrieve data in order, and the binary tree can only be applied to the binary search tree, but the organizational structure of the data itself can’t completely satisfy all kinds of data structure (for example, theoretically impossible will both columns at the same time in order to organize), so, In addition to the data, the database system maintains data structures that satisfy specific lookup algorithms, and that reference (point to) the data in a way that makes it possible to implement advanced lookup algorithms on these data structures. This data structure is called an index. Look at an example:

Figure 1 shows one possible way to index. On the left is the data table, with two columns and seven records, and on the far left is the physical address of the data records (note that logically adjacent records are not physically adjacent on disk). To speed up Col2 lookup, a binary lookup tree can be maintained as shown on the right. Each node contains the index key value and a pointer to the physical address of the corresponding data record, so that binary lookup can be used to obtain the corresponding data within O(log2n) complexity.


While this is a genuine index, actual database systems rarely use binary lookup trees or their evolutionary varieties
Red and black tree(Red-black tree), for reasons described below.

B-tree and B + Tree

At present, most database systems and file systems use B-tree or its variant B+Tree as an index structure. In the next section of this paper, we will discuss why B-tree and B+Tree are so widely used in indexes based on the principles of memory and computer access. This section first describes them purely from the perspective of data structure.

B-Tree

Is a kind of multi-path search tree (not binary) : 1. Define any non-leaf node has at most M sons; And M > 2; 2. The number of sons of the root node is [2, M]; 3. The number of sons of non-leaf nodes except root nodes is [M/2, M]; 4. Each node stores at least M/2-1 (rounded) and at most M-1 keywords; 5. Number of keywords of non-leaf nodes = number of Pointers to sons -1; 6. Keywords of non-leaf nodes: K[1], K[2]… [M, K – 1); And K[I] < K[I +1]; 7. Pointers to non-leaf nodes: P[1], P[2]… P [M]; Where P[1] points to the subtree whose keyword is less than K[1], P[M] points to the subtree whose keyword is greater than K[m-1], and other P[I] points to the subtree whose keyword belongs to (K[i-1], K[I]). 8. All leaf nodes are located in the same layer; 9. Each K corresponds to a data. For example :(M=3) is equivalent to a 2-3 tree. A 2-3 tree is a tree where each node has either 2 children and 1 data element, or 3 children and 2 data elements, while a leaf node has no children and 1 or 2 data elements.

B-tree search, starting from the root node, the keyword (ordered) sequence within the node for binary search, if the match is finished, otherwise enter the search keyword range of the son node; Repeat until the corresponding son pointer is null or already a leaf node; The pseudo-code of the search algorithm on b-tree is as follows:

BTree_Search(node, key) { if(node == null) return null; foreach(node.key) { if(node.key[i] == key) return node.data[i]; if(node.key[i] > key) return BTree_Search(point[i]->node); } return BTree_Search(point[i+1]->node); } data = BTree_Search(root, my_key);

• B-tree has the following characteristics: 1. The keyword set is distributed in the whole tree; 2. Any keyword appears in only one node; 3. The search may end at non-leaf nodes; 4. Its search performance is equivalent to a binary search in the whole set of keywords; 5. Automatic hierarchical control;

• Self-control of the B-tree: Each internal node in the B-tree contains a certain number of keys. Typically, the number of key values is selected between D and 2D. In practice, key values take up most of the space in a node. Factor 2 guarantees that nodes can be split or combined. If an internal node has 2d keys, the process of adding a key to the node will split the 2d key with 2 D keys and add the key to the parent node. Each split node requires a minimum number of keys. Similarly, if an internal node and its neighbor both have D keys, a key will be deleted by merging it with the neighbor. Deleting this key results in the node having D-1 keys; The merge with the neighbor adds d keys, plus one from the parent of the neighbor node. The result is a fully populated 2D key value.

• Insert 6 10 4 14 5 11 15 32 12 1 7 8 8 6 3 6 21 5 15 15 6 32 23 45 65 7 8 65 4

  
  

  

  btreebuild.gif

B+Tree

There are many varieties of B-tree, among which B+Tree is the most common. For example, MySQL widely uses B+Tree to achieve its index structure.

• Compared with B-tree, B+Tree has the following differences: 1. The number of subtree Pointers and keywords of non-leaf nodes is the same. P[I], which points to the subtree whose keyword value belongs to [K[I], K[I +1]) (b-tree is the open interval); 3. Add a chain pointer to all leaf nodes; 4.

  
  

  

  Paste_Image.png

The search of B+ is basically the same as that of B-tree. The difference is that B+ tree hits only leaf nodes (B-tree can hit non-leaf nodes), and its performance is equivalent to binary search in the whole set of keywords.

• Characteristics of B+ : 1. All keywords appear in the linked list of leaf nodes (dense index), and the keywords in the linked list happen to be ordered; 2. 2. Impossible to hit on non-leaf nodes; 3. Non-leaf nodes are equivalent to the index of leaf nodes (sparse index), and leaf nodes are equivalent to the data layer storing (keyword) data; 4. More suitable for file indexing system;

• Insert 6 10 4 14 5 11 15 32 12 1 7 8 8 6 3 6 21 5 15 15 6 32 23 45 65 7 8 65 4

  
  

  

  Bplustreebuild.gif

Physical storage of indexes

Generally, indexes themselves are too large to be stored in memory, so indexes are often stored on disk as index files. Therefore, the disk I/O consumption of index lookups is several orders of magnitude higher than memory access, so the most important indicator of a data structure as an index is the progressive complexity of disk I/O operations during lookups. In other words, indexes should be structured to minimize the amount of disk I/O needed to access a lookup.

B-tree

Suppose each disk block can store exactly one node of the B-tree (exactly two file names). A BTNODE node represents one disk block, and a subtree pointer is the address of another disk block.

• Let’s simulate the process of finding file 29:1. Find the root disk block 1 of the file directory according to the root pointer, and import the information in it into memory. [Disk I/O operation once] 2. The memory has two file names 17, 35, and three to store the data of other disk page addresses. According to the algorithm, we find: 17<29<35, so we find the pointer P2. 3. According to the P2 pointer, we locate disk block 3 and import the information into memory. [disk I/o operation twice] 4. The memory contains two file names 26,30, and three pages of other disks. According to the algorithm, we find: 26<29<30, so we find the pointer P2. 5. According to the P2 pointer, we locate the disk block 8 and import the information into the memory. [Disk I/O operation three times] 6. The memory contains two file names 28 and 29. According to the algorithm, we find the file name 29 and locate the disk address of the file memory. Three disk I/O operations and three memory lookup operations are required. As for the file name search in memory, because it is an ordered table structure, we can use split search to improve efficiency. IO operations are the decisive factor affecting the efficiency of the whole B-tree search.

Of course, if we use the balanced binary tree disk storage structure for lookup, disk 4 times, maximum 5 times, and more files, B tree than balanced binary tree disk I/O operations will be fewer and more efficient.

B+tree

• Advantages of B+ Tree:

1. The disk read and write cost of B+-tree is lower ****B+-tree**** internal nodes do not point to the specific information of the keyword. So the internal nodes are smaller than the b-tree. If all the keywords of the same internal node are stored in the same disk block, then the disk block can contain more keywords. Read into memory at a time to find more keywords. The number of IO reads and writes is relatively low. For example, suppose that a block on a disk contains 16bytes, a keyword is 2bytes, and a pointer to a keyword is 2bytes. An internal node of order 9 b-tree (a node with up to 8 keywords) requires 2 disks. The internal node of ****B+ **** tree only needs 1 disk fast. When internal nodes need to be read into memory, the B-tree has one more block lookup time (in disk, the rotation time) than the ****B+ **** tree.
2. The query efficiency of B+-tree is more stable because the non-endpoints are not the nodes that ultimately point to the content of the file, but only the index of the keyword in the leaf node. So any keyword lookup must take a path from root to leaf. The length of all keyword query paths is the same, resulting in the same query efficiency of each data.

Index storage mechanism of the two storage engines of mysql

MyISAM index implementation

MyISAM engine uses B+Tree as the index structure, and the data field of the leaf node stores the address of the data record. Here is the MyISAM index schematic:

Select Col1 as Primary key from MyISAM; select Col1 as Primary key from MyISAM; You can see that MyISAM’s index file only holds the address of the data record. In MyISAM, there is no difference in structure between primary and Secondary keys, except that the primary index requires a unique key, while Secondary keys can be repeated. If we create a secondary index on Col2, the structure of this index is as follows:

Also a B+Tree, data field holds the address of the data record. Therefore, the index retrieval algorithm in MyISAM is to search the index according to THE B+Tree search algorithm. If the specified Key exists, the value of its data field is extracted, and then the corresponding data record is read with the value of the data field as the address.


MyISAM’s indexing approach is also called “non-clustered”.

InnoDB index implementation

InnoDB also uses B+Tree as an index structure, but the implementation is quite different from MyISAM.

The first big difference is that InnoDB’s data files are themselves index files. MyISAM index files and data files are separate, and the index file only holds the address of the data record. In InnoDB, the table data file itself is an index structure organized by B+Tree, and the data field of the leaf node of this Tree holds complete data records. The key of this index is the primary key of the table, so the InnoDB table data file itself is the primary index.

Above is a diagram of the main index (which is also a data file) of InnoDB. You can see that the leaf node contains the complete data record. This kind of index is called a clustered index. InnoDB requires tables to have primary keys (MyISAM does not have primary keys) because InnoDB data files themselves are aggregated by primary keys. If this is not explicitly specified, the MySQL system automatically selects a column that uniquely identifies the data record as the primary key. MySQL automatically generates an implied field for the InnoDB table as the primary key. This field is 6 bytes long and of type long integer.

The second difference from MyISAM index is that InnoDB’s secondary index data field stores the value of the primary key of the corresponding record rather than the address. In other words, all InnoDB secondary indexes refer to the primary key as the data field. For example, a secondary index defined on Col3:

The ASCII code of English characters is used as the comparison criterion. Clustered index implementations make searching by primary key very efficient, but secondary index searches require retrieving the index twice: first, retrieving the secondary index for the primary key, and then using the primary key to retrieve records from the primary index.

Understand the different storage engines index is implemented for the proper use of and optimize the index are very helpful, know the InnoDB index after implementation, for example, it is easy to understand why not suggest using long field as the primary key, because all the auxiliary index reference primary index, long primary index will make auxiliary index becomes too large. For example, using non-monotonic fields as primary keys is not a good idea in InnoDB, because InnoDB data files themselves are a B+Tree. Non-monotonic primary keys cause data files to be constantly split and adjusted to maintain B+Tree features when new records are inserted, which is inefficient. Using an increment field as a primary key is a good choice.