This is the second day of my participation in the August More text Challenge. For details, see: August More Text Challenge

Definition and Introduction

  1. Indexes are data structures that help mysql get efficient data, so indexes are essentially what they are: data structures

  2. The purpose of an index is to improve query efficiency. It can be understood as a dictionary, an article catalog, etc

  3. Because indexes are very large, they cannot be stored in memory. Therefore, indexes are generally stored on disk in the form of index files

Basic grammar

Create indexes

Create index
create [unique] index idxName on table_name(columnName(length))
Alter table structure index
alter table table_name add [unique] index idxName(columnName)
Copy the code

View index

show index from table_name
Copy the code

Remove the index

drop index idxName on table_name
Copy the code

Other common commands for adding indexes

Add primary key index
alter table table_name add primary key(column_list)

-- Add unique index
alter table table_name add unique idxName(column_list)

-- Add a normal index
alter table table_name add index idxName(column_list)

Add full-text index
alter table table_name add fulltext idxName(column_list)
Copy the code

The index classification

Indexes in mysql can be divided into multiple classes according to different categories

Physical storage Angle

  • Clustering index
  • Non-clustered indexes are also called secondary indexes

Data structure Angle

  • B + several indexes
  • A Hash index
  • Full-text index (available before 5.6 only when the storage engine is MyISam)
  • R – tree indexes

The logical point of view

  • Primary key index: a unique index that does not allow null values
  • Single-column index: Each index can contain only one column. A table can have multiple single-column indexes
  • Combined index: Each index contains at least two column fields, and queries are assigned to the left
  • Unique index: The column that adds this index must have a unique value in the table
  • Spatial index: Index added to a spatial column field

B-, B+ tree index

Indexes are implemented at the storage engine level, not the Server level. There are some differences in all support and implementation between multiple storage engines

B-tree (B Tree)

define

The B-tree of order M is a balanced M-path search tree. Every time a node is obtained, an I/O operation is performed on the disk

3 B tree

The nature of the

  • Each node has a maximum of m children
  • Every node except the root node and the leaf node has at least Ceil(m/2) children
  • If the root node is not a child node, then there are at least two children
  • All leaf nodes are at the same layer and contain no other keyword information
  • Each non-terminal node contains n keyword information, m/2 <= n <= m, n= number of children -1
  • The elements of each node are arranged from the smallest to the largest, and k-1 elements of the node are exactly the range of elements contained by k children

instructions

  • Each node occupies the disk space of one disk block. A node has two keywords in ascending order and three Pointers to the sub-root node. The Pointers store the address of the disk block where the sub-node resides
  • The three range domains divided by two keywords correspond to the range domains of the data of the subtree to which the three Pointers point.

B + tree

4 order B+ digitmap

Definition and Description

  • B+ tree is a kind of argument of B tree, the overall performance is better
  • In the B-tree structure diagram, it can be seen that each node contains not only the key value of data, but also the data value. The storage space of each page is limited. If the data is large, the number of keys that can be stored by each node (that is, each page) will be small. If the amount of data stored is large, the depth of B-Tree will also be large, increasing the number of DISK I/O times during the query, and thus affecting the query efficiency.
  • In B+ tree, all data record nodes are stored on leaf nodes of the same layer according to the order of key value, while non-leaf nodes only store key value information. In this way, the number of key values stored in each node can be greatly increased and the height of B+ tree can be reduced

B+Tree B+Tree

The difference between

  • Non-leaf nodes store only key-value information
  • All leaf nodes have a chain pointer between them
  • Data records are placed in leaf nodes

advantage

  • A single node stores more elements, making the query IO times less
  • Nodes do not store data and can store more key values
  • All queries need to find the leaf node, the query performance is stable; B- tree is based on the performance of different data, for example, data appears in the root node, only one IO; If a leaf node appears, it takes m IO times; The performance is not fixed
  • All leaf nodes travel an ordered list, easy to scope query. B-tree performs range search in the in-order traversal mode, which has a lower performance.

A hash index

  • Mainly through the hash algorithm, the database field is converted into the hash value of the order field, and the corresponding position of the hash table is stored together with the pointer of the record. If a Hash collision occurs, it is stored as a linked list under the corresponding Hash key. Common hash algorithms include direct addressing, middle square, folding, mod divisor, and random number
  • Search algorithm: During the search, the system performs the same Hash algorithm for the keyword again to obtain the Hash value and retrieves the data from the corresponding position in the Hash table. If Hash collisions occur, the system filters the value
  • Mysql currently only supports Hash indexes in the Mermory and NDB engines

Full-text Indicates a full-text index

  • Full-text index isa special index type in MyISAM, which is mainly used for full-text retrieval. InnoDB provides support for full-text indexes starting with mysql5.6
  • It is used as an alternative to the less efficient LIKE fuzzy matching operation, and can be fully fuzzy matching multiple fields at one time by full-text index of multi-field combination
  • Deposit using the b-tree index data, but using a particular algorithm, after dividing field data indexing, index file storage is separated before set the index to the string, and the separated index information, the structure of the corresponding BTree node storage is the separated word information and its position before the separation index of the string in the collection.