preface

Do you know what an index looks like?

When the disk space is low, why does adding an index cause disk space to be insufficient?

Why does mysql insert and delete less efficiently with more indexes?

With these questions in mind, we begin today’s topic.

What is an index?

Index is a data structure that helps the database system obtain data efficiently. Database Index is essentially a data structure that improves the efficiency of data retrieval in the database at the cost of additional write operations and storage space for maintaining Index data structure.

To sum up, indexes are data structures! A data structure designed to improve retrieval efficiency.

Common database indexes include hash tables and B+ trees.

So what does the index physically look like? Actually we have a “how the mysql data storage (under) | mysql series (5) say: mysql storage structure is divided into 5 levels: table space, period, cluster, page, line. Creating an index creates two segments: a data segment and an index segment.

Why is the index of InnDB B+ tree?

Binary tree search efficiency is also very high, such as balanced binary tree, we often use the idea of binary tree in data structure and algorithm to solve the problem, we all know mysql is using B+ tree, so why InnDB not binary tree?

Because the balanced binary tree structure in memory search efficiency is relatively fast. but

Indexes exist in index files and on disk. Because indexes are usually too large to load all indexes into memory at once, only one disk page can be read from disk into memory at a time. The disk reads several levels slower than the memory reads.

Because the binary tree serialized to disk, its physical implementation is an array, specific reference

“Solving binary Trees in one Article — From Binary Trees to Greedy Algorithms”

And because nodes that are logically similar in structure may be physically far apart. As a result, much of the data on disk pages is not needed each time they are read. Therefore, many disk reads are made during the lookup process.

What’s wrong with indexing binary trees?

Binary trees are used in the search of disks, so there are several problems:

  • If the data is very large, the tree height is very high, resulting in a high number of DISK I/O scans

  • A node stores only one piece of data, which is far apart in physical memory. Disk scanning requires frequent rotation

  • Data needs to be read from disk to memory frequently. Even if the operating system has preread, most of the data brought out is not needed temporarily, resulting in waste

Let’s review a few points here:

Disk IO time:

  • Disk I/O time = Seek + disk rotation + Data transfer time

Performance difference between continuous read/write and random read/write of a mechanical disk:

  • Sequential access: Memory access is 6-7 times faster than hard disk access (Kafka features, more on that later)

  • Random access: Memory access is up to 100,000 times faster than hard disk access. In real disk storage, sequential storage is rare because of the high maintenance cost.

Locality principle and Disk prefetch:

Due to the characteristics of the storage medium, the disk itself access is much slower than the main memory, coupled with the cost of mechanical movement, the disk access speed is often one hundred percent of the main memory, so in order to improve efficiency, to minimize the disk I/O. To achieve this goal, the disk does not read data strictly on demand. Instead, the disk prereads each time. Even if only one byte is required, the disk reads a certain length of data backward from this position into memory. The theory behind this is the famous principle of locality in computer science: when a piece of data is used, nearby data is usually used immediately. The data required during the running of a program is usually concentrated. Because sequential disk reads are efficient (no seek time required, very little spin time required), preread can improve I/O efficiency for localized programs.

In conclusion, binary trees are not suitable for indexing because of the storage and access characteristics of disks and the physical storage mode of binary trees.

Introduction of B+ trees

In view of the above problems, the following points need to be optimized:

  • Reduces the number of DISK I/O scans.

  • Reduces the DISK I/O rotation frequency.

  • Make good use of operating system prefetch, locality principle.

B tree is a data structure created to take full advantage of disk prefetch, that is, B tree was invented to serve as an index.

B+ tree characteristics

  • B + tree has all the advantages of B tree, and the non-leaf nodes of B + tree do not store data, but only store index, and only store index + data in the leaf node, and the leaf node forms a bidirectional linked list structure through the front and back Pointers, so after locating to the index through the tree structure, The result of the range query can be quickly traversed directly through the linked list pointer of the leaf node, which better takes advantage of the optimization of sequential IO performance over random IO. This is something that b trees don’t have.

  • B + tree is the underlying data structure of InnoDB. It is connected by n-fork tree, node page and leaf node linked list to avoid too much DISK IO scanning and rotation times. Besides, it makes use of the prefetch and locality principle of operating system and supports the function of range query.

The advantages of B+ trees

  • Compared with binary trees such as red-black trees and balanced binary trees, the biggest advantage of B tree /B+ tree is that the tree height is smaller.

  • Each Innodb node uses a page, the size of the page is 16KB, the metadata is only about 128 bytes (including file management header information, page header information, etc.), most of the space is used to store data.

  • For a 3-tier B+ tree, the first tier (root node) has 1 page and can store 1000 records; The second layer has 1000 pages and can store 1000*1000 records; The third layer (leaf node) has 1000*1000 pages, and each page can store 100 records, so it can store 1000*1000*100 records, or 100 million records. For binary trees, storing 100 million records requires about 26 layers.

To summarize

Now we can answer the first few questions.

InnoDB is a B+ tree data structure.

Adding an index creates two files, so adding an index when the server disk space is low can result in insufficient disk space.

With more indexes, multiple files are maintained each time data is added or deleted, making it less efficient.