Author: Tom Brother wechat official account: Micro technology

Do you think the B+ tree index file will become smaller after deleting half of the data in a table with tens of millions of bytes?

(Answers in the article!!)

Let’s do an experiment to see how the size of the table changes.

Do an experiment and let the data do the talking

1, first of all, inmysqlCreate a user table as follows:

CREATE TABLE `user` ( `id` bigint(20) NOT NULL AUTO_INCREMENT, 'user_name' varchar(128) NOT NULL DEFAULT 'COMMENT ',' age 'int(11) NOT NULL COMMENT' age ', 'address' varchar(128) COMMENT 'address ', PRIMARY KEY (' id')) ENGINE=InnoDB DEFAULT CHARSET= utf8MB4 COMMENT=' user ';Copy the code

2. Create data. Batch insert to user table1000WThe data

@getMapping ("/insert_batch") public Object insertBatch(@requestParam ("batch") int batch) { Insert 1000W data for (int j = 1; j <= batch; j++) { List<User> userList = new ArrayList<>(); for (int i = 1; i <= 100; I++) {User User = User. The builder (). The userName (" Tom elder brother - "+ ((j - 1) * 100 + I)). The age (29). The address (" Shanghai"). The build (); userList.add(user); } userMapper.insertBatch(userList); } return "success"; }Copy the code

Batch insertion, 100 records per batch, 100000 batches, a total of 1000W data

3, check table file size

Index file size is about 595 M, last modified at 02:17

Said * * * * :

  • Before MySQL 8.0, table structures existed in files with the suffix.frm

  • Ibd files are used to store data and indexes. Each table has an. Ibd file

Table data can exist in either a shared table space or as a separate file. Innodb_file_per_table control. After MySQL 5.6.6, the default is ON, so that each InnoDB table data is stored in a file with an.ibd suffix.

4. Delete the appointment500WThe data

@GetMapping("/delete_batch")
public Object deleteBatch(@RequestParam("batch") int batch) {
    for (int j = 1; j <= batch; j++) {
        List<Long> idList = new ArrayList<>();
        for (int i = 1; i <= 100; i += 2) {
            idList.add((long) ((j - 1) * 100 + i));
        }
        userMapper.deleteUser(idList);
    }
    return "success";
}

Copy the code

At the beginning, there were 1000W entries in the user table. After deleting some entries, there are about 550W entries left in the user table

5. After deleting about 500W records, check the table file size again

The index file size is about 595 M. The last modification time was 10:34

Experimental conclusions:

For tens of millions of table data stores, deleting a large number of records does not reduce the table file size. That’s weird. What’s causing that? Don’t worry, here’s a closer look at why

Data table operations include adding, deleting, modifying, and querying data tables. Querying data tables is a read operation and does not modify file contents. File contents are modified by write operations, which are classified into three types: delete, add, and modify.

Next, let’s start analyzing one by one

Delete the data

Data in InnoDB is organized in B+ trees. If you are not sure about the B+ tree storage structure, you can take a look at an article I wrote earlier to consolidate the basics.

Q: How many rows can a B+ tree store in mysql?

If several records have been inserted into the table, the B+ tree structure is constructed as shown below:

Delete the record with id=7. InnoDB only marks the record with id=7 as deleted, but the space is reserved. This space can be reused if there are subsequent inserts with ids in the range (6,19).

In the figure above, a new record with id=16 is inserted.

In addition to records, data pages can also be reused. When the ** entire page is removed from the B+ tree, it can be reused anywhere. 巴哈马解密

For example, after deleting all records on page number=5, the page is marked as reusable. If a new page is needed to insert a record with id=100, the page number=5 can be reused.

If the utilization of two adjacent pages is low, the database merges the data from the two pages into one page, and the other page is marked as reusable.

Of course, what if we delete the entire table as we did above? All data pages are marked as reusable, but space is not freed, so the table file size remains unchanged.

Summary: The delete command only marks the data page or record location as reusable. The table space is not reclaimed. This phenomenon is called “void”.

The new data

If the inserted data is in a random non-primary key order, the data page may be split.

Insert a new page (id=15) with page number=6 to save the data. After page splitting is complete, a reusable void is left at the end of page number=5.

Conversely, if the data is inserted in order of index increment, the index is compact and there is no data page split.

Modify the data

If you change a non-index value, the structure of the B+ tree will not be affected

For example, if you update the values of other fields with id=7, the primary key ID remains the same. The entire B+ tree has not been restructured.

However, if the modification contains an index, the procedure is to delete an old value and then insert a new value. It could create a void.

The analysis found that,Add, modify, deleteIs there any way to compress the table space?

Guest officer, please continue to read

The new table

Alter table A alter table B alter table A alter table B alter table A alter table B alter table A alter table B alter table A alter table B alter table A alter table B alter table A alter table B alter table A alter table B alter table A alter table B alter table A alter table B alter table A alter table B Because table B is new and does not have voids, the data pages are more utilized.

After all data in table A is migrated, replace table A with Table B.

Prior to release 5.5, MySQL provided one-click commands to perform the entire process in a quick manner, such as dumping data, swapping table names, and dropping old tables.

Alter table engine=InnoDBCopy the code

However, this scheme has A fatal shortcoming. During table reconstruction, if new data is written to table A, it will not be migrated, resulting in data loss.

Online DDL

To address these issues, MySQL 5.6 began to introduce Online DDL to optimize the process.

Execution steps:

  • Create a temporary file

  • Scan all data pages of primary key of table A to generate B+ tree and store in temporary file

  • If A write is made to table A during temporary file generation, the operation is logged to A log file

  • When a temporary file is generated, replay the log file to apply the action to the temporary file

  • Replace table A’s data files with temporary files

  • Delete the old table A data file

The biggest difference with the new table, added log file recording and replay function. Table A can be added, deleted, or modified during migration.

About me: I am a former ali architect who has won patents and prizes in competitions. I am a CSDN blog expert who is responsible for e-commerce transactions, community fresh food, marketing, finance and other businesses. I have years of team management experience

Recommended reading

Q: How many rows can a B+ tree store in mysql?

Learn these 10 design principles and be one step closer to being an architect!!

How to design the Redis cache for a hundred million level system??

High concurrency, high performance, high availability system design experience

Everyone is an architect?? No easy talk!!

How to design inventory deduction for e-commerce? Not oversold!