MySQL index data structure

1. Index Overview

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

The nature of an index:

An index is a data structure. You can think of it simply as a “sorted fast lookup data structure” that satisfies a particular lookup algorithm. These data structures point to the data in a way that allows you to implement advanced lookup algorithms on top of these data structures. Indexes are implemented in storage engines, so each storage engine may not have identical indexes, and each storage engine may not support all index types. At the same time, the storage engine can define the maximum number of indexes and the maximum index length for each table. All storage engines support at least 16 indexes per table, and the total index length is at least 256 bytes. Some storage engines support a larger number of indexes and a larger index length.

Key points:

SQL > alter table ORDER BY; SQL > alter table ORDER BY; SQL > alter table ORDER BY;

The following figure shows an example of a possible indexing approach

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 record. In order to speed up the Col2 data records in the search, can maintain a as shown on the right side of the binary search trees, each node contains the index key value and a pointer to the corresponding data record physical address, so that you can use binary search within a certain complexity to get to the appropriate data, to rapidly retrieve the eligible records.

The purpose of an index is to improve query efficiency. It can be compared to a dictionary. If you want to look up the word mysql, you must locate the letter M first, then search down for the letter Y, and then find the rest of SQL. If you don’t have an index, then you might need a– z for a full dictionary scan. What if I want to find words that start with Java? What if I want to find words that start with Oracle??

Generally, indexes themselves are too large to be stored in memory, so they are often stored on disk as index files

Run the df command to query disk space in Linux-h 
[root@Ringo ~]# df -h
Filesystem      Size  Used Avail Use% Mounted on
/dev/vda1        40G   16G   23G  41% /
devtmpfs        911M     0  911M   0% /dev
tmpfs           920M     0  920M   0% /dev/shm
tmpfs           920M  480K  920M   1% /run
tmpfs           920M     0  920M   0% /sys/fs/cgroup
overlay          40G   16G   23G  41% 
Copy the code

The index we normally refer to, if not specified, is in the InnoDB engine, all refers to the B+ tree (multi-way search tree, not necessarily binary) structure of the index. Among them clustered index, secondary index, overwrite index, composite index, prefix index, unique index is the default use of B+ tree index, collectively called index. Of course, in addition to B+ tree data structure indexes, there are Hash indexes, etc.

MyISAM, InnoDB, Memory three storage engines for various index types support

The index INNODB engine MYISAM engine The MEMORY engine
BTREE index support support support
A HASH index Does not support Does not support support
R – tree indexes Does not support support Does not support
Full-text Supported after version 5.6 support Does not support

advantages

  1. Search: similar to the university library to build bibliographic index, improve the efficiency of data retrieval, reduce the disk IO cost of database, which is the main reason to create index.
  2. By creating unique indexes, each row of data in a database table is guaranteed to be unique.
  3. In terms of achieving referential integrity of data, you can speed up joins between tables. In other words, you can speed up queries when children and parents of dependent tables are jointly queried.
  4. Sorting: When grouping and sorting clauses are used for data queries, the time of grouping and sorting in queries can be significantly reduced and CPU consumption reduced.

disadvantages

Increasing indexes also has many disadvantages, mainly in the following aspects:

  • Creating and maintaining indexes takes time and increases as the volume of data increases.
  • Indexes take up disk space. In addition to data table space, each index also takes up a certain amount of physical space and is stored on disk. If there are a large number of indexes, index files may reach the maximum file size faster than data files.
  • While indexes greatly speed up queries, they slow down table updates. Indexes are maintained dynamically as data is added, deleted, or modified to a table, which slows down data maintenance.
  • Therefore, the advantages and disadvantages of an index should be considered when selecting an index.
  • Indexes are only one factor in improving efficiency. If MySQL has a large number of tables, it takes time to research and build the best indexes.

2. Why index

Index is the storage engine used to quickly find a data structure of data records, like through the directory to find the specific one page of the book to locate to an article, Mysql, too, for data search, to see whether the query conditions hit one of the first index, conform to the relevant data by an index lookup, does not conform to the requires global scanning, That is, search the records one by one until you find the records that match the criteria

If the data is stored using a data structure such as binary search tree, as shown in the figure below

3. Deduction of indexes in InnoDB

3.1. Lookup before index

Let’s start with an example of an exact match:

SELECT[List of column names]FROMThe name of the tableWHEREThe column name= xxx;
Copy the code

1. Find within a page

Assuming that there are few records in the table at present, all records can be stored in one page, and records can be searched in two cases according to different search conditions:

  • Search by primary key: you can quickly locate the corresponding slot in the page directory using dichotomy (because primary keys are generally incremental and orderly), and then traverse the records in the corresponding group of the slot to quickly find the specified record
  • With other columns as the search terms: because in the data page is not for the primary key column set up so-called page directory, so we can’t through the dichotomy quickly locate the corresponding slot, this situation can only start from minimum record traverse singly linked lists of each record in turn, and then compared each record is in accordance with the search criteria. Obviously, this kind of search is very inefficient

2. Search through many pages

Most of the time the records in our tables are very large and require many data pages to store them. Looking for records across many pages can be divided into two steps:

  1. Navigate to the page where the record resides
  2. Find the corresponding record from the page you are on

In the case of no index, no matter according to the value of the primary key column or other column, because we can not quickly locate the record on the page, so we can only from the first page down the bidirectional linked list, in each page according to the way we find the specified record. This is obviously super time consuming because you have to traverse all the data pages. What if a table had 100 million records? This is where indexes come in.

3.2 design index

Create a table:

mysql> CREATE TABLE index_demo(
    -> c1 INT.-> c2 INT.-> c3 CHAR(1),
    -> PRIMARY KEY(c1)
    -> ) ROW_FORMAT =Compact; Line # formatCopy the code

The newly created Index_demo table has 2 INT columns, 1 CHAR(1) column, and c1 primary key. The table uses Compact row format to actually store records. Here we simplify the row format schematic of the Index_demo table:

We only show these parts of the record in the diagram:

  • Record_type: an attribute of the record header. It indicates the type of the record. 0 indicates normal record, 2 indicates minimum record, 3 indicates maximum record, and 1 has not been used yet.
  • Next_record: an attribute of the record header that represents the offset of the next address relative to this record. We use an arrow to indicate who the next record is.
  • Values for individual columns: Only three columns in the Index_Demo table are recorded here, c1, C2, and C3.
  • Other information: All information except the above three, including the values of other hidden columns and additional information recorded.

This is what happens when you temporarily remove other information items from the record format diagram and make it stand up:

Here’s a diagram of putting some records on a page:

1. A simple index design

Why should we traverse all the data pages when we are looking up some records based on some search criteria? Because the records in each page are irregular, we do not know which records in our search criteria match, so we have to traverse all the data pages in turn. So what if we want to quickly locate the records we need to find in which data pages? We can create a directory to quickly locate the data page where the record resides. This directory must do the following:

  • The primary key value recorded by the user on the next data page must be greater than the primary key value recorded by the user on the previous page.
  • Create a directory entry for all pages.

So our table of contents for the previous pages looked something like this:

For example, page 28 corresponds to directory entry 2, which contains the page number 28 and the minimum primary key value 5 for user records on the page. We only need to store several items in physical storage (such as: array), can realize the function of finding a certain record according to the primary key value. For example, to search for records whose primary key value is 20, the specific search process is divided into two steps:

  1. The primary key value of 20 is quickly determined from the directory entry according to the dichotomy method and recorded in the directory entry 3 (because 12 < 20 < 209), and its corresponding page is page 9.
  2. Locate the specific record on page 9 in the same way we found the record on the page above (primary key lookup – dichotomy).

At this point, a simple table of contents for data pages is done. This directory has an alias called index.

2. Index scheme in InnoDB

① Iteration 1: pages of catalogue entries

This is what we would look like if we put the previous entry into the data page:

As you can see from the figure, a new page numbered 30 has been allocated to store catalog entry records. Again, there are differences between directory entry records and normal user records:

  • The record_type value of a directory entry record is 1, whereas the record_type value of a common user record is 0.
  • The directory entry record has only two columns: primary key and page number, whereas the normal user record column is user-defined and may contain many columns, as well as hidden columns added by InnoDB itself.
  • Note: There is also a min_rec_mask attribute in the record header. The min_rec_mask value is 1 for the directory record with the smallest primary key value on the page where the directory record is stored. The min_rec_mask value is 0 for all other records.

Similarities: Both use the same data Page and both generate Page Directory by primary key value, thus dichotomy can be used to speed up the query when searching by primary key value.

Now take the search for the record whose primary key is 20 as an example, the search for the record according to a primary key value can be roughly divided into the following two steps:

  1. First go to the page where the directory record is stored, that is, through the dichotomy method on page 30, quickly locate the corresponding directory entry. Because 12 <20 <209, the page where the corresponding record is located is page 9.
  2. Then go to page 9 where user records are stored and quickly locate the user record whose primary key value is 20 according to dichotomy.

② Iterate 2 times: pages of multiple catalogue entries

As you can see from the figure, we need two new data pages after we insert a user record with a primary key of 320:

  • Page 31 is created to store the user record.
  • Because page 30, where the directory entry records were stored, was full (we assumed that only four directory entry records could be stored), a new page 32 had to be used to hold the directory entries corresponding to page 31.

Now, since there is more than one page for storing catalog entry records, it takes roughly 3 steps if we want to find a user record based on the primary key value. Take finding a record with a primary key value of 20 as an example:

  1. Determine the directory entry record page: we now have two pages storing directory entry records, namely page 30 and page 32. Because the primary key value range of the directory entry represented by page 30 is [1, 320), and the primary key value of the directory entry represented by page 32 is not less than 320, the directory entry corresponding to the record with the primary key value of 20 is recorded in page 30.
  2. Determine the page where the user record is actually located by the directory entry record page: the way to locate a directory entry record by primary key value in a page where the directory entry record is stored is described.
  3. Locate the specific record in the page where the actual user record is stored.

③ Iterate 3 times: The directory page of the directory entry record page

As shown in figure, we generated a higher entry page 33 of storage, the two records of representing pages 30 and 32 pages, if the user record’s primary key value in [1, 320), then to page 30 to find more detailed catalogue records, if the primary key value should not less than 320 words, just look in to page 32 for more detailed catalogue records. So that’s our initial model of a B+ tree

We can describe it as follows:

This data structure, its name is B+ tree.

(4) B + Tree

The nodes of a B+ tree can actually be divided into several layers, so the bottom layer (the leaf node), where our user records are stored, is layer 0, and then we add them up. Earlier, we made a very extreme assumption that a page for user records could hold up to three records and a page for directory entry records could hold up to four records. In fact, the number of records stored in a page in the real environment is very large. Suppose that the data page represented by all leaf nodes storing user records can store 100 user records, and the data page represented by all internal nodes storing directory records can store 1000 directory records, then:

  • If the B+ tree has only one level, that is, only one node for storing user records, it can hold up to 100 records.
  • If the B+ tree has two layers, it can store up to 1000×100=10,0000 records.
  • If B+ tree has 3 layers, it can store 1000×1000×100=1,0000,0000 records at most.
  • If the B+ tree has four layers, it can store a maximum of 1000×1000×1000×100=1000,0000,0000 records. Quite a lot of records!!

Can you store 100000000000 records in your table? Therefore, in general, the B+ tree we use is not more than 4 layers (the lower the tree level is, the less disk I/O times are), so we only need to do a maximum of 4 pages to find a record through the primary key value (find 3 directory entry pages and 1 user record page). And because there is a so-called Page Directory within each Page, it is also possible to quickly locate records within the Page using dichotomy.

3.3. Common index concepts

Index According to the physical implementation, indexes can be divided into two types: clustered (clustered) and non-clustered (non-clustered) indexes. We also refer to non-clustered indexes as secondary or secondary indexes.

1. Cluster index

Clustered indexes are not a single type of index, but rather a way of storing data (all user records are stored in leaf nodes). The term ‘clustering’ refers to the storage of rows of data together with clusters of adjacent keys and values. The index is the data, the data is the index

Features:

  • Using the recordThe primary keyThe size of records and pages are sorted, which has three implications:
    • The records in the page are arranged in a one-way linked list in order of the size of the primary key.
    • Each page storing user records is also arranged in a bidirectional linked list according to the primary key size of user records in the page.
    • The pages that store directory entry records are divided into different levels. The pages in the same level are also arranged in a bidirectional linked list according to the primary key size of directory entry records in the page.
  • The leaves of the B+ tree store the complete user record. A complete user record is one in which the values of all columns (including hidden columns) are stored.

A B+ tree with these two characteristics is called a clustered index, and all the complete user records are stored at the leaf node of the clustered index. The InnoDB storage engine automatically creates the clustered INDEX for us instead of using the INDEX statement displayed in Mysql

Advantages:

  • Data access is faster because clustered indexes keep indexes and data in the same B+ tree, so getting data from clustered indexes is faster than non-clustered indexes
  • Clustering indexes are very fast in sorting and range lookups for primary keys
  • When a certain range of data is displayed in a clustered index sequence, the database does not need to extract data from multiple data blocks. Therefore, a large number of I/O operations are saved.

Disadvantages:

  • The insert speed depends heavily on the insert order. The primary key order is the fastest way to insert. Otherwise, pages will split and performance will be severely affected. Therefore, for InnoDB tables, we generally define an incremented ID column primary key
  • Updating the primary key is expensive because it causes the updated row to move. Therefore, for InnoDB tables, we generally define primary keys as not updatable
  • Secondary index access requires two index lookups, the first to find the primary key value and the second to find the row data based on the primary key value

Limitations:

  • For Mysql currently only InnoDB supports clustered indexes, while MyISAM does not support clustered indexes
  • Because data can be stored in only one physical sort, each Mysql table can have only one clustered index. In general, this is the primary key of the table
  • If there is no primary key defined, InnoD selects a non-empty unique index instead. If there is no such index, InnoDB implicitly defines a primary key as the cluster index
  • In order to take full advantage of the clustering feature of the index, some sequential ids are selected for the primary key column of innoDB tables. It is not recommended to use unordered ids, such as UUID, MD5, HASH, and string columns as the primary key to ensure the sequential growth of data.

2. Secondary index (secondary index, non-clustered index)

The clustered indexes described above only work if the search criteria are primary keys, because the data in a B+ tree is sorted by primary keys, so what if we want to search by specific columns? You can’t go all the way down the list

Answer: We can build several more B+ trees, and different B+ numbers adopt different sorting rules. For example, we use the size of C2 column as the sorting rules (search criteria) for data pages and records in the page, and then build a B+ tree, as shown in the figure below:

This B+ tree differs from the cluster index above in several ways:

  • Ordering records and pages using the size of the record C2 column has three implications:
    • The records in the page are arranged in a one-way linked list in order of C2 values.
    • Each page storing user records is also arranged in a bidirectional linked list according to the size of C2 columns of user records in the page.
    • The pages storing directory entry records are divided into different levels, and the pages in the same level are also arranged in a bidirectional linked list according to the size of C2 columns of directory entry records in the page.
  • Instead of storing the complete user record, the leaves of the B+ tree store the values of the C2 + primary key columns.

Take the example of finding a record with a value of 4 in column C2:

  1. Determine the directory entry record page: Based on the root page, which is page 44, you can quickly locate the directory entry record on page 42(because 2<4<9).
  2. Determine the actual user record page from the catalog entry record page: On page 42 can quickly locate to the actual storage user record in the page, but because of C2 column and no uniqueness constraints (also is not the primary key, can’t like clustering index), so the value of C2 is 4 records may be distributed in multiple data pages, and because 2 < 4 < = 4, so make sure the actual record store user page in the page on page 34 and 35
  3. Locate the specific record on pages 34 and 35 where the user record is actually stored.
  4. However, the records in the leaf node of the B+ tree only store C2 and C1(primary key) columns, so we must search the complete user records in the B+ tree of the clustered index again according to the primary key value, this process is called back table

Concept: back table

The B+ tree sorted by the c2 column size can only determine the primary key value of the record we are looking for, so if we want to find the full user record based on the C2 column value, we still need to look again in the clustered index, a process called table back. It takes 2 B+ trees to query a complete user record based on the values of c2 column!

If no field value is found in the result of a query based on a non-primary key index, the user needs to start the search again from the root node of the cluster index based on the primary key. In this way, the records searched again are complete.

Question: Why do we need a back table operation? Isn’t it OK to put the full user record directly into the leaf node?

Answer: if the user complete records on the leaf node is can need not back to the table, but it’s too take a place, such as insert data in the table, then copy it again all the data to establish a B + tree, the equivalent of every build a B + tree need to copy all the user record again, if the amount of data a lot, it’s a bit too waste of storage space

Because this kind of established according to the primary key column B + tree needs a back table operation can locate the complete user record, so this kind of B + tree is also known as secondary indexes, or secondary index, the size of the column because we are using the C2 as collation of B + tree, so we also call the B + tree is established for C2 column index

The presence of non-clustered indexes does not affect the organization of data in clustered indexes, so a table can have multiple non-clustered indexes.

Summary: Clustered index and non-clustered index principle is different, there are some differences in use:

  • The leaf node of the clustered index stores our complete data record, while the leaf node of the non-clustered index stores the data location (index value + primary key). The non-clustered index does not affect the physical storage order of the data table
  • A table can have only one clustered index, because there can only be one sort storage, but it can have multiple non-clustered indexes, that is, multiple index directories providing data retrieval
  • When clustered indexes are used, the data query efficiency is high. However, when data is inserted, deleted, or updated, the efficiency is lower than that of non-clustered indexes

3. Syndication index

If we want to sort the B+ tree by the size of the C2 and C3 columns, this has two implications:

  • Start by sorting individual records and pages into c2 columns.
  • In the case that the C2 columns of the records are the same, the C3 column is used for sorting

Note that a B+ tree sorted by the size of the C2 and C3 columns is called a joint index and is essentially a secondary index. This means something different from the statement that indexes columns C2 and C3 separately, with the following differences:

  • Creating a joint index will only create a B+ tree like the one shown above.
  • Indexing the C2 and C3 columns creates two B+ trees sorted by the size of the C2 and C3 columns, respectively.

4. Full-text Index:

This index is implemented in MyISAM engine, InnoDB engine also supports full-text index after 5.6, and Chinese index after 5.7.6. Full-text indexing can only be used on CHAR,VARCHAR, and TEXT fields. The underlying implementation is inverted indexing. Note that for tables with large data volumes, generating full-text indexes can be very time consuming and disk space consuming.

3.4 InnoDB B+ tree index notes

1, the root page position does not move for thousands of years

In the previous introduction, for ease of understanding, the leaf node that stores user records was drawn first, followed by the inner node that stores directory entry records.

But the line formation of a B+ tree actually looks like this:

  • Whenever a B+ tree index is created for a table, a root node page is created for that index. There is no data in the table at first, so there are no user records or directory entries in the root node.
  • When inserting a user record into a table, store the user record on this root node first.
  • When the root node runs out of page space and records are inserted, all records in the root node are copied to a new page (for example, page A), which is then split to create another new page (page B). At this point, newly inserted records are allocated to pages A and B based on the key value size (primary key in the clustered index, value of the index column corresponding to the non-clustered index). The root node page is then upgraded to a page that stores directory entry records, and the directory entry records for pages A and B need to be inserted into the root node.

In addition, when the root node of a B+ tree index is created, its page number does not change. So whenever we create an index for a table, the page number of its root node will be recorded somewhere, and then whenever the InnoDB engine needs to use the index, it will fetch the page number of the root node from that fixed place to access the index.

2. Uniqueness of directory entry records in inner nodes

In general, for non-clustering, in the inner node of the B+ tree index, the contents of the entry record are the index column + page number. But for secondary indexes, it is less rigorous.

For example, if there are four records in a table where c1 is the primary key:

Now index the C2 column (by the size of the c2 column value) :

If you continue to insert a record with columns 9, 1, and ‘c’, you run into a problem:

  • The value of c2 in the new record is also 1. Should the new record be placed on page 4 or page 5?

Therefore, “in order for the newly inserted record to find which page it should go to, it is necessary to ensure that the directory entry record of nodes in the same layer of the B+ tree is unique”.

So, in fact, the directory entry record of the inner node of the secondary index should consist of three parts:

  • The value of the index column
  • The primary key
  • Page number

So the actual index for C2 would look like this:

Now, when new records 9, 1, ‘c’ are inserted:

  • You can start by comparing the value of column C2 of the new record with the value of column C2 of each directory entry on page 3.
  • If the c2 column values are the same, the primary key values are then compared.

Therefore, for secondary indexes, creating this index for C2 column is equivalent to creating a joint index for C2 and C1. Sort by the value of the secondary index first. If the columns of the secondary index have the same value, sort by the primary key.

3. Store at least two records on a page

As mentioned in the previous article, B+ trees can easily store hundreds of millions of records with very few levels and query speed.

This is because a B+ tree is essentially a large multilevel directory. Each directory is filtered for many invalid subdirectories until you finally get to the directory where the real data is stored.

So now imagine: the same amount of data, if a large directory only one subdirectory, what would it look like?

  • There are many directory levels
  • Only one record can be stored in the last directory where the real data is stored

If so, the B+ tree structure makes little sense and does not form a valid index. As a result, innoDB’s designers “required all data pages to hold at least two records in order to avoid growing the B+ tree too high”.

4. Index scheme in MyISAM

4.1 overview,

B tree (B+ tree, no B- thing) index applies to storage engine as shown in table:

Even if multiple storage engines support the same type of index, their implementation principles are different. Innodb and MyISAM default index is Btree index; Memory’s default index is a Hash index.

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

4.2 Principle of MyISAM index

Here is a schematic of the MyISAM index

We know that InnoDB index (data) already contains all the complete user records in the leaves of the B+ tree of clustered indexes, while MyISAM index scheme also uses tree structure, but stores indexes and data separately:

  • Records in a table are stored in a separate file in the order in which they are insertedThe data file. The file is not divided into several data pages, just as many records are crammed into the file. Inserts are not ordered by primary key size, so binary lookup cannot be used on these data, we can quickly access a record by ** line number (data record address)**.
  • useMyISAMThe storage engine’s table will turnIndex informationAnother store is calledIndex fileIn another file.MyISAMIt will be a separate tableA primary keyCreate an index, except that instead of storing the complete user record in the leaf node of the indexPrimary key + Line number (data record address)The combination of. That is, first through the index to find the corresponding row number, and then through the row number to find the corresponding record!

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. Whether the key of an index is a primary key is classified into primary index and secondary index or secondary index. Indexes created using the primary key are called primary indexes, and others are called secondary indexes. Therefore, there can only be one primary index and many secondary indexes. 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 (back table operation).

4.3 Comparison between MyISAM and InnoDB

MyISAM indexes are “non-clustered” (because leaf nodes do not store complete data records), unlike InnoDB which has one clustered index. Summary of index differences between the two engines:

  • In The InnoDB storage engine, we only need to perform a single lookup of the cluster index based on the primary key value to find the corresponding record, but in MyISAM, we need to perform a table back operation, which means that the index created in MyISAM is equivalent to all secondary indexes.
  • InnoDB data files themselves are index files, while MyISAM index files and data files are separated, and the index file only holds the address of the data record.
  • InnoDB’s non-clustered index data field stores the value of the corresponding record primary key, while MyISAM index records the address. In other words, all InnoDB’s non-clustered indexes refer to the primary key as the data field.
  • MyISAM’s back to the table operation is very fast, because it takes the address offset directly to the file, whereas InnoDB takes the primary key and then goes to the clustered index to find the record. It’s not slow, but it’s not as fast as using the address directly to access the data.
  • InnoDB requires tables to have primary keys (MyISAM can’t). If not explicitly specified, the MySQL system automatically selects a non-empty column that uniquely identifies the data record as the primary key. If no such column exists, 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.

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 can make auxiliary index becomes too large (high level, low efficiency). 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.

5. The cost of indexing

As the saying goes, nothing is perfect, and the same can be said of indexes. Before we use indexes, we must understand that indexes can sometimes be a drag: Indexes are a good thing, not to be spoiled, because they consume space and time:

  • The cost in space
    • This one is obvious. For every index you build, you build a tree for itB+Trees, every one of themB+Each node of the tree is a data page, and a page is occupied by default16KBStorage space, a lot ofB+A tree consists of many data pages, which is a lot of storage space.
  • The cost in time
    • Every time you add, delete, or modify data in a table, you need to modify each oneB+Index of the tree. And we talked about,B+The nodes at each level of the tree are sorted in ascending order according to the value of the index column to form a bidirectional linked list. Both the records in the leaf node and the records in the inner node (that is, the user record and the directory entry record) form a one-way linked list in ascending order of the index column values.
    • Add, delete, and modify operations may damage the order of nodes and records, so the storage engine needs extra time to perform some operations such as record shifting, page splitting, and page reclamation to maintain the order of nodes and records. If we build a bunch of indexes, each index corresponds toB+Trees are required to perform maintenance operations, but does this not drag down performance?

So, index is good, but don’t “drink” oh.

The more indexes a table has, the more storage space it takes up, and the worse performance it will have when adding, deleting, and changing records. In order to create good and few indexes, we must learn the conditions under which these indexes work. In what cases can we use an index, and in what cases can we not use an index?

6, MySQL data structure selection rationality (index implementation method)

Index data structures (primary key indexes, unique indexes, etc.) :

  • BTreeIndex: A data structure used to process multidimensional data, which can be spatially indexed to geographic data. However, it is rarely used in actual business scenarios.
  • B+ tree implementation: THE B+ tree is suitable for range queries such as ‘>’ or ‘<‘, and is the most commonly used index implementation in MySQL
  • HashIndex: The Hash table is used to index data. Unlike Btree, which requires multiple queries to locate records, Hash indexes are more efficient than B-tree. However, Hash indexes do not support range search and sorting, and are rarely used.
  • R-TreeThe index.

From mysql’s point of view, we have to consider the practical problem of disk IO. If we can index the data structure to minimize disk IO operations, the less time is consumed. It can be said that the number of I/O operations on a disk is critical to index efficiency.

Generally speaking, the index is very large, especially for relational databases. When the data volume is large, the size of the index may be several GIGABytes or even more. In order to reduce the memory occupation of the index, the database index is stored on the external disk. When we use index query, it is impossible to load the whole index into memory, only one by one, so mysql measures the query efficiency standard is disk I/O times

6.1 Full table traversal

SELECT * FROM user WHERE id = ‘3’; We do a row by row query, which is called a full table scan; Obviously, this approach is extremely inefficient, and database performance can be significantly degraded under frequent operations, so indexes are designed to solve this problem.

6.2. Hash Structure

Hash itself is a function, also known as a Hash function, that can make retrieving data much more efficient.

Hash algorithms convert input to output using deterministic algorithms such as MD5, SHA1, SHA2, and SHA3. The same input can always produce the same output, and given a slight deviation in the input content, there will often be different results in the output.

For example: If you want to verify the two files are the same, so you don’t need to bring two copies of files directly, only need to let the other side to tell you the result of the Hash function to calculate, then the local same Hash function of file operations, finally by comparing the results of the two Hash functions are the same, you can know whether the two files are the same.

There are two common types of data structures that speed up lookups:

  • For trees, such as balanced binary search trees, the average time complexity of query/insert/modify/delete is O(log2N);
  • For hashes, such as HashMap, the average time complexity of query/insert/modify/delete is O(1);

Hash is highly efficient. Data can be found in a single search, whereas B+ trees need to search from the top down and visit nodes for multiple times to find data. In the process, MULTIPLE I/O operations are required.

In the way of hashing, an element K is in h(k), that is, using the hash function h, the slot position is calculated according to the key word k. Function h maps the keyword field to slots in the hash table T[0…m-1].

The hash function h in the figure above has the potential to map two different keywords to the same location. This is called a collision and is usually solved by chaining in databases. In chaining, the elements hashed to the same slot are placed in a linked list, as shown below:

Experiment: See the efficiency difference between arrays and hash lookups

// The algorithm complexity is O(n)
@Test
public void test1(a){
    int[] arr = new int[100000];
    for(int i = 0; i < arr.length; i++){ arr[i] = i +1;
    }
    long start = System.currentTimeMillis();
    for(int j = 1; j<=100000; j++){int temp = j;
        for(int i = 0; i < arr.length; i++){if(temp == arr[i]){
                break; }}}long end = System.currentTimeMillis();
    System.out.println("Time." + (end - start)); / / time: 823
}
Copy the code
// The algorithm complexity is O(1)
@Test
public void test2(a){
    HashSet<Integer> set = new HashSet<>(100000);
    for(int i = 0; i <100000; i++){ set.add(i +1);
    }
    long start = System.currentTimeMillis();
    for(int j = 1; j<=100000; j++) {int temp = j;
        boolean contains = set.contains(temp);
    }
    long end = System.currentTimeMillis();
    System.out.println("Time." + (end - start)); / / time: 5
}
Copy the code

Hash structures are efficient, so why should index structures be trees?

  • Cause 1: The Hash index can only meet the requirements of (=) (<>) and IN. It can quickly locate a record, and the time complexity is O(1). If range query is carried out, the time complexity of hash index will be reduced to O(n); The order characteristic of trees can still maintain O(log2N) high efficiency

  • Cause 2: The Hash index has another defect. The data is stored in an unordered ORDER. In ORDER BY case, the Hash index needs to be reordered.

  • Cause 3: In the case of a joint index, the Hash value is calculated by combining the joint index keys together, and a single key or several index keys cannot be queried.

  • Cause 4: Hash indexes store hash codes (the hash codes corresponding to the keys of each row). Generally, hash indexes are more efficient for equivalent queries. However, if there are many duplicate values in the index columns, the efficiency will be reduced. This is because when Hash conflicts occur, it is time-consuming to traverse the row pointer in the bucket for comparison and find the query key. Therefore, Hash indexes are usually not used on columns with many duplicate values, such as gender, age, and so on.

Hash indexes for storage engines are shown in the following table:

Applicability of Hash indexes:

Hash indexes have many limitations. B+ tree indexes are more widely used in databases, but there are some scenarios where Hash indexes are more efficient. For example, in key-value databases, the core of Redis storage is Hash tables.

The Memory storage engine in MySQL supports Hash storage. If you need to query a temporary table, you can use the Memory storage engine to set a field as a Hash index, such as a string field, which can be shortened to a few bytes after the Hash calculation. Using Hash indexes is a good choice when field duplicates are low and equivalent queries are often required.

In addition, InnoDB does not support Hash indexes, but does provide Adaptive Hash indexes. When should an adaptive Hash index be used? If certain data is frequently accessed, the address of the data page is stored in the Hash table when certain conditions are met. So that the next time you query, you can directly find the location of the page. This gives B+ trees the benefit of a Hash index.

The adaptive Hash index is used to speed up the locating of leaf nodes according to SQL query conditions, especially when the B+ tree is deep. The adaptive Hash index can significantly improve the data retrieval efficiency. We can check whether adaptive Hash is enabled by using the innodb_adaptive_hash_index variable, for example:

mysql> show variables like '%adaptive_hash_index';
Copy the code

Only memory storage engines support hash indexes, which compute the hashCode of that value using the value of the index column and then store the physical location of that value in the corresponding hashCode location. Because hash algorithms are used, access is very fast, but a value can only correspond to one hashCode. And hash distribution, so hash indexes do not support range lookup and sorting functions.

6.3. Binary search tree

If we use a binary tree as an index structure, the number of DISK I/OS is related to the height of the index tree.

1. Characteristics of binary search tree

  • A node can only have two children, that is, a node degree cannot exceed 2
  • Left child node < local node; Right child >= this node, older than me to the right, younger than me to the left
  • The time complexity of binary trees is O(n).

2. Find rules

The Binary Search Tree is a Binary Search Tree in which a node is searched in the same way as a node is inserted, assuming that the value of the Search insert is key:

  1. If the key is larger than the root node, the search is performed in the right subtree.
  2. If the key is smaller than the root node, the search is performed in the left subtree.
  3. If the key is equal to the root node, which means the node is found, return the root node.

For example, the binary search tree we created for the sequence (34,22, 89, 5, 23, 77, 91) is shown below:

But there are special cases where the depth of the binary tree is very large. For example, the order of data given by us is (5, 22, 23, 34, 77,89,91), and the binary search tree created is shown in the figure below:

The second tree above is also a binary search tree, but it has been degraded to a linked list and the search time is O(n). You can see that the depth of the first tree is 3, which means it takes at most three comparisons to find the node, and the depth of the second tree is 7, which takes at most seven comparisons to find the node.

To improve query efficiency, you need to reduce disk I/OS. To reduce the number of DISK I/OS, you need to reduce the tree height as much as possible. You need to change the original “tall and thin” tree structure into “short and fat”. The more branches in each layer of the tree, the better.

6.4, the AVL tree

In order to solve the problem of Binary search Tree degenerated into a linked list, people put forward Balanced Binary search Tree, also called AVL Tree (different from AVL algorithm), which adds constraints on the basis of Binary search Tree and has the following properties:

“It is an empty tree or the absolute value of the difference in height between its left and right subtrees is no more than 1, and both subtrees are a balanced binary tree.”

Here, there are many kinds of common balanced binary trees, including balanced binary search tree, red black tree, number heap, secondary progression tree. Balanced binary search tree is the first self-balanced binary search tree. When we refer to balanced binary search tree, we usually refer to balanced binary search tree. In fact, the first tree is a balanced binary search tree, the search time complexity is O(1og2n).

The time of data query mainly depends on the number of disk I/OS. If we adopt the form of binary tree, even if we improve it by balancing binary search tree, the tree depth is O(log2n). When N is large, the depth is high, as shown in the following figure:

Each node access requires one disk IO operation, and for the tree above, we need five I/ OS. The balanced binary tree is efficient, but the tree depth is also high, which means that the number of DISK I/O operations affects the overall data query efficiency.

And whether ordinary binary search tree, or AVL tree, a node can only store a data here, and a node, in MySQL inside and corresponding to a disk block, so that every time we read a disk blocks, can only obtain a data, especially low efficiency, so we will think of the B tree structure is used to storage.

For the same data, what if we change the binary tree to an m-tree (M>2)? When M=3, the same 31 nodes can be stored by the following trigeminal tree:

You can see that the height of the tree is reduced. For large N and large M, the height of the m-tree is much smaller than the height of the binary tree (M> 2). So, we need to change the tree from tall and thin to chunky.

6.5, the b-tree

B Tree is a Balance Tree. Short for b-tree (note that the bar means the two words are connected, not the minus sign). Its height is much smaller than that of a balanced binary tree. Compared to binary search tree, the height/depth is lower, and the natural query efficiency is higher. It is the most common type of index, and most storage engines support b-tree indexes

The structure of b-tree is shown in the figure below:

[Introduction to initialization]

A b tree, the light blue piece of what we call a disk block, you can see every disk block contains several data items (shown in blue) and pointer (shown in yellow, address information stored in the node), such as disk block 1 contains data item 17 and 35, contains a pointer (P1, P2, P3, P1 said less than 17 disk blocks, P2 indicates the disk block whose value is between 17 and 35. P3 indicates the disk block whose value is greater than 35. Real data exists at leaf nodes, namely 3, 5, 9, 10, 13, 15, 28, 29, 36, 60, 75, 79, 90, 99. Non-leaf nodes do not store real data, but only the data items that guide the search direction, which can be understood as the key of the data item. For example, 17 and 35 do not really exist in the data table.

[Search process]

If we want to find item 29, we will first load disk block 1 from disk to memory. At this time, we will use binary search in memory to determine that 29 is between 17 and 35. The P2 pointer of disk block 1 will be locked. By disk 1 piece of P2 pointer disk address the disk block 3 by disk loaded into memory, in the second IO, 29 between 26 and 30, locking disk blocks of the 3 P2 pointer, pointer loading disk blocks through eight into memory, in the third IO, binary search to find memory do 29 at the same time, the end of the query, a total of three IO.

The reality is that a 3-tier B-tree can represent millions of data. If millions of data lookups take only three IO, the performance improvement is huge. If there is no index and each data item has to take one IO, the total number of IO will be millions, which is obviously very, very expensive.

As a multi-path balanced search tree, each node of the B-tree can contain at most M child nodes, which is called the order of the B-tree. Each disk block contains Pointers to keywords and child nodes. If a disk block contains X keywords, the number of Pointers is x+1. For a 100-rank B-tree, if there are three levels, it can store up to about 1 million index data. For a lot of rope bow | data, adopting the structure of B tree is very suitable for, because the height of the tree is far less than the height of the binary tree.

An m-order B-tree (M>2) has the following properties:

  1. The range of sons of the root node is [2,M].
  2. Each intermediate node contains K-1 keywords and K children. The number of children is equal to the number of keywords +1. The value of k ranges from[ceil(M/2), M].
  3. The leaf node contains k-1 keywords (the leaf node has no children), and the value range of k is[ceil(M/2), M].
  4. Assume that the keyword of the intermediate node is:The Key [1], the Key [2],... , Key[k-1], and the keywords are sorted in ascending order, i.eKey[i]<Key[i+1]. At this point, k-1 keyword is equivalent to dividing K ranges, that is, corresponding to K Pointers, namely, P[1], P[2],… , P[k], where P[1] points to the subtree whose Key is less than Key[1], P[I] points to the subtree whose Key belongs to (Key[i-1], Key[I]), and P[k] points to the subtree whose Key is greater than Key[k-1].
  5. All leaf nodes are in the same layer.

The b-tree represented in the diagram above is a third-order B-tree. If we look at disk block 2, the keyword is (8, 12), it has 3 children (3, 5), (9,10) and (13,15), you can see that (3, 5) is less than 8, (9,10) is between 8 and 12, and (13,15) is greater than 12. It fits exactly what we just gave you.

And then let’s see how we can use B trees to find things. Assuming that the keyword we want to find is 9, the steps can be divided into the following steps:

  1. We compare it with the keyword (17, 35) of the root node. If 9 is less than 17, we get pointer P1.
  2. Find disk block 2 according to pointer P1, keyword is (8, 12), because 9 is between 8 and 12, so we get pointer P2;
  3. Follow pointer P2 to find disk block 6 with keyword (9, 10), and then we find keyword 9.

B tree shortcomings

As you can see, we’re not comparing a lot of times in the search of the B tree, but if we’re reading the data out and comparing it in memory, that’s negligible. Reading the disk block itself requires I/O operations, which consume more time than the time required for comparison in memory, and is an important factor in data lookup time. B trees require less disk I/O operations than balanced binary trees, and are more efficient in data queries than balanced binary trees. So as long as the tree height is low enough, I/O times are low enough, you can improve query performance. When a large amount of data is generated, the B tree is very deep, which increases the number of DISK I/OS and affects the query efficiency.

Summary:

  1. If the tree is unbalanced when nodes are inserted or deleted, the tree is self-balanced by automatically adjusting the position of nodes.
  2. Keyword sets are distributed in the whole tree, that is, both leaf nodes and non-leaf nodes store data. The search may end at a non-leaf node
  3. Its search performance is equivalent to a binary search in the whole set of keywords.

Example 1:

6.6 and B + Tree

B+ tree is also a multi-way search tree, based on the IMPROVEMENT of B tree, the mainstream DBMS all support B+ tree index, such as MySQL. Compared to B-Treey, B+Tree is suitable for file indexing systems.

MySQL > MySQL

B+ tree features:

  1. The number of subtree Pointers and keywords of non-leaf nodes is the same.
  2. The subtree pointer P[I] of non-leaf node points to the subtree whose keyword value belongs to [K[I], K[I +1]) (front closed and then open, b-tree is the open interval);
  3. Add a chain pointer to all leaf nodes.
  4. All keywords appear in leaf nodes (data exists in leaf nodes);

Differences between B+ trees and B trees:

  1. A node with k children has k keywords. So the number of children is equal to the number of key words, and in the CASE of B tree, the number of children is equal to the number of key words plus 1.

  2. Keywords of non-leaf nodes in the B+ tree also exist in leaf nodes and are the maximum (or minimum) of all keywords in the child nodes.

  3. Non-leaf nodes are only used for indexing and do not hold data records. Records-related information is stored in leaf nodes. In a B-tree, non-leaf nodes store both indexes and data records.

  4. All the keywords of B+ tree appear in leaf nodes, which form an ordered linked list, and the leaf nodes themselves are linked in order of the size of the keywords from small to large.

  5. B-tree keywords and records are put together, leaf nodes can be regarded as external nodes, do not contain any information; The non-leaf nodes of the B+ tree have only keywords and indexes pointing to the next node, and the records are only placed in the leaf node.

  6. In b-tree, the record search time is faster the closer to the root node, and the existence of the record can be determined as long as the key word is found. However, the search time of each record in B+ tree is basically the same, and it needs to go from the root node to the leaf node, and then compare keywords in the leaf node. From this perspective, b-trees appear to perform better than B+ trees, but in practice, B+ trees perform better. Since the non-leaf nodes of a B+ tree do not store actual data, each node can contain more elements and the tree height is smaller than that of a B- tree, which reduces the number of disk accesses.

  7. Though the B + tree to find a record number of required more than b-tree more, but a memory disk access time is equal to the hundreds of thousands of times more time, so in the actual performance of B + tree may be better, and B + tree leaf nodes use pointer together, convenient for sequential traversal (for example, to view a directory of all the files, All records in a table, etc.), which is why many databases and file systems use B+ trees.

Both B trees and B+ trees can be used as data structures for indexes. In MySQL, B+ trees are used. However, both B trees and B+ trees have their own application scenarios. It is not true that B+ trees are better than B trees and vice versa.

The query process for a B+ tree is similar to that for a B+ tree, but the fundamental difference is that the middle node of a B+ tree does not store data directly. What are the benefits?

  1. First, B+ tree query efficiency is more stable. Because B + tree each time the only access to the leaf node to find the corresponding data, in the B tree, not a leaf node will store data, this will cause the query efficiency is not stable, sometimes access to the leaf node can find key and end, and sometimes need to access to the leaf node to find the key.
  2. Second, the query efficiency of B+ tree is higher. This is because B+ trees are generally dumber (larger order, lower depth) than B trees and require less disk IO for queries. The B+ tree can store more node keywords for the same disk page size.
  3. The efficiency of B+ tree is higher than that of B tree not only in the query of a single keyword, but also in the query range. This is because all the keywords appear in the leaf nodes of the B+ tree, there are Pointers between the leaf nodes, and the data is incremented, which makes our range lookup possible through pointer joins. In B tree, it is necessary to complete the search of the query range through middle-order traversal, which is much less efficient.

Both B trees and B+ trees can be used as data structures for indexes. In MySQL, B+ trees are used. However, both B trees and B+ trees have their own application scenarios. It is not true that B+ trees are better than B trees and vice versa.

Question to consider: In order to reduce IO, will the index tree be loaded once?

1. The database index is stored on disk. If the data volume is very large, the index size will be very large, more than a few gigabytes. 2, when we use index search, is not all a few G index can be loaded into memory, we can do is: each load each disk page, because the disk page corresponds to the cable arch | node of the tree.

Question: What is the storage capacity of B+ trees? Why does it take only 1 to 3 disk I/OS to find row records

InnoDB storage engine page size is 16KB, the typical table primary key type is INT (4 bytes) or BIGINT (8 bytes), pointer type is also – usually 4 or 8 bytes, This means that a page (a node in B+Tree) stores 16KB/8+8B =1K keys (K = 10^3 for easy calculation). This means that a depth of 3 B+Tree index can maintain 10^3 * 10^3 * 10^3= 1 billion records. (This assumes a data page also stores 10^3 rows of record data.)

In practice, each node may not be fully filled, so in the database, the height of B+Tree is generally between 2 and 4 layers. MySQL’s InnoDB storage engine is designed to have the root node resident in memory, which means that it takes at most one to three disk I/O operations to find rows of a particular key value.

Question: Why are B+ trees better than B- trees for file and database indexes in practical operating systems?

1. The disk read and write cost of B+ tree is lower

The internal nodes of the B+ tree do not have Pointers to specific information about 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 I0 reads and writes are relatively low.

2. The query efficiency of B+ tree is more stable

Because non-endpoints are not the nodes that ultimately point to the contents of the file, they are only the indexes of the keywords in the leaf nodes. 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.

Question: The difference between a Hash index and a B+ tree index

We talked about the structure of the B+ tree index, and the Hash index structure is different from the B+ tree index structure, so there are differences in index usage.

1. Hash indexes cannot be used for range query, whereas B+ trees can. This is because a Hash index | point data is chaotic, and B + tree leaf node is an ordered list.

2. IHash indexes do not support the leftmost principle of a combined index, whereas B+ trees do. For a Hash index, the Hash value is calculated by combining the index keys together. Therefore, the Hash value is not calculated separately for each index. So if use joint index of one or a few index, joint index | can’t be used.

3, a Hash index does not support the ORDER BY sorting, because a Hash index | point data is chaotic, so cannot play a sorting optimization for use, and B + tree index data is ordered, can have the effect of the ORDER of the field BY sorting optimization. Similarly, we can’t use Hash indexes for fuzzy queries, whereas B+ trees that use LIKE for fuzzy queries can be optimized by using LIKE followed by a fuzzy query (e.g. % ending).

4. InnoDB does not support hash indexes

Question: Are Hash indexes and B+ tree indexes manually specified when building an index?

If you are using MySQL, we need to understand the MySQL storage engine support which index structure, as shown in the figure below (reference source dev.mysql.com/doc/refman/…

As you can see, both InnoDB and MyISAM storage engines use B+ tree indexes by default, not Hash indexes. InnoDB provides an adaptive Hash that does not need to be specified manually. Hash indexing is optional for Memory/Heap and NDB storage engines.

6.7, R tree

R-tree is rarely used in MySQL. It supports only the geometry data type. Only myISAM, BDB, InnoDB, NDB, and Archive support this type of storage engine. An example of what R trees can do in the real world: find all restaurants within 20 miles. What would you do if there were no R trees? In general, we will divide the coordinates of the restaurant (x and Y) into two fields and store them in the database. One field records longitude and the other one latitude. So we need to go through all the restaurants to get their location information, and then calculate if they meet the requirements.

If there are 100 restaurants in an area, we need to perform 100 location calculations, which is certainly not feasible when applied to large databases such as Google maps and Baidu Maps. R tree is a good solution to the high dimensional space search problem. It extends the idea of B-tree to multi-dimensional space, adopts the idea of b-tree partition space, and combines and decomposes nodes in addition and deletion operations to ensure the balance of the tree. Therefore, R tree is a balanced tree for storing high dimensional data. Compared with B-tree, R-tree has the advantage of range search.

6.8, summary

Using indexes can help us quickly locate the data we want to search from the massive data. However, indexes also have some disadvantages, such as occupying storage space, reducing the performance of database write operations, and increasing the index selection time if there are multiple indexes. When we use the index, the need to balance index (improve query efficiency) and cons (cost needed for the maintenance line | bow). In practical work, we also need to determine whether to use index based on demand and the distribution of data itself. Although index is not a panacea, it is unimaginable not to use index when there is a large amount of data. After all, the essence of index is to help us improve the efficiency of data retrieval.

6.9 appendix: Time complexity of the algorithm

The same problem can be solved by different algorithms, and the quality of one algorithm will affect the efficiency of the algorithm and even the program. The aim of algorithm analysis is to select suitable algorithm and improve algorithm.

7. Interview questions

In MySQL, indexes belong to storage engine level concept. Different storage engines implement indexes differently, such as MyISAM and InnoDB storage engine.

MyISAM index implementation:

MyISAM storage engine uses B+Tree as the index structure, and the data field of the leaf node stores the address of the data record. MyISAM’s index is also called “non-clustered” to distinguish it from InnoDB’s clustered index.

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.
  • 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. 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 the records in the primary index (back to the table).

In fact, the realization of database index can use red black Tree, B-tree Tree data structure. But why is B+Tree actually used?

This from the computer storage principles and operating system related knowledge. Because the index of the data table is too large to reside in memory, it is stored in disk as a file. Therefore, I/O operations are required when querying data. The goal of efficient queries is fewer I/O counts. An I/O typically reads one page of data (typically 4k) (locality principle). Thus, in the B-tree, every time a new node is requested, the size of the page is requested. That is, one I/ O can read data from one node (containing many keys); In red-black tree structures, nodes that are logically adjacent are not necessarily physically adjacent, that is, multiple I/ OS are required to read the same data. So the b-tree is more efficient.

So why did you pick a B+ tree?

Since the data field is removed from the nodes in the B+ tree, they can have a larger outgo, which means that a node can store more inner nodes and thus have a higher I/O efficiency.

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.

Clustered index and non-clustered index:

  • InnoDB is a clustered index because the leaves of its B+ tree contain complete data records. However, the leaf node of MyISAM B+ tree only stores the address of data, so it is called non-clustered index.

Index usage strategy and optimization

  • The optimization of MySQL is mainly divided into Scheme optimization and Query optimization.

8, clustered index and non-clustered index more official discourse

Clustered index: The order of clustered index table records is consistent with the order of the index (index is data, data is index), so the query efficiency is fast, as long as the first index value record is found, the rest of the continuous records are stored in the same physical continuity. The disadvantage of clustered index correspondence is that it is slow to modify because the data pages are reordered when the records are inserted to ensure that the physical and index order of the records in the table is consistent. That is, it mainly describes physical storage.

Non clustered index: non clustered index to establish the logical sequence of records in the table, but the index of physics and records may not consistent, both indexes using B + tree structure, the leaves of the clustered index layer is not overlapped and actual data page, and USES the leaf layer contains a pointer to records in the table data pages in the way. Non-clustered indexes have many levels and do not cause data rearrangement.

The fundamental difference between a clustered index and a non-clustered index is whether the table records are sorted in the same order as the index.

An index is described by the data structure of a binary tree. We can think of a clustered index as: the leaf nodes of the index are data nodes. A leaf node that is not a clustered index is still an index node but has a pointer to the corresponding data block.