Mysql database article series continues to update, want to follow more welcome to wechat public account: pipi's fantastic ideasCopy the code

The original link

You probably already know that B+ trees are used in Mysql’s underlying implementation of indexing, so why B+ trees? In this article, you will explore the underlying implementation of database indexing.

An example summarizes the characteristics of an index

Adding indexes is a way for database to speed up queries, so why can use indexes to speed up queries?

When it comes to indexes, we often hear the example of a library. There are many books in the library. How can we find a book we want from several books?

According to the library system search, we can find a corresponding book number.

On the premise that books are arranged in accordance with certain rules, we can find the book according to the book number.

For example, suppose book numbers are based on:

Number of shelves – number of boxes on a shelf – number of positions from left to right

And this kind of arrangement of rules,

We can easily get the books we want.

You might notice that there are two messages hidden in this example:

  1. Arrange them according to certain rules

  2. The orderly

According to certain rules, establish certain mapping relations, this reminds you of what?

Yes, it’s a hash table.

Hash table based hash index implementation

In Mysql’s InnoDB engine, adaptive hash indexing is implemented using hash tables.

Hash indexes are created and used by the database itself and cannot be interfered with by the DBA itself, but can be disabled or enabled with parameters.

Obviously, the benefits of implementing indexes with hash tables are very obvious, and finding a single specified data requires only O(1) time complexity.

For example, the following SQL statement:

select id from tablename where id == 1;
Copy the code

But for SQL statements that look up a specified range, hash indexes are useless.

select id from tablename where id BETWEEN 20 AND 23;
Copy the code

Note: Because the hash table itself is unordered, it is not conducive to range queries

Think again

Here we have encountered a problem, that is, although the hash table meets our search efficiency requirements for a single data, but obviously, when we encounter a range query, due to the disorder of the hash table itself, it is not conducive to specify the range search.

In other words, our needs have increased, and we want our data to be organized in a way that is both disciplined and orderly.

Before we introduce this data structure, let’s first look at one type of lookup: binary lookup.

Efficient search: binary search

The core idea of binary search is that given an ordered array, the search is performed by skipping in the search process, that is, the midpoint position of the ordered sequence is taken as the comparison object first. If the element to be searched is smaller than the midpoint element, the search sequence is reduced to the left half, otherwise it is the right half. With each comparison, the search interval is reduced in half until the desired element is found.

Say you want to find the number 4 in the following sequence

,3,4,5,6,7,8 [1]Copy the code

The following search steps are required:

  • Take the element corresponding to the center position, obviously 5 is greater than 4, and search in the left interval [1,3,4]

  • Continue to take the corresponding element 3 at the center, which is obviously greater than 4, and search in the right interval [4]

  • 4 is 4, so we found it.

You can see that the efficiency of binary search is order log n.

Due to the order nature of ordered array, range query can still be implemented by binary search to find the boundary of the interval.

In this case, ordered arrays are a good choice for query efficiency alone.

But obviously ordered arrays are not insertion and deletion friendly, and if we want to insert elements or delete elements, we have to move some elements backwards or forwards, and the worst time complexity is ORDER n.

Is there a data structure that is sequential and easy to insert and delete? In fact, based on the idea of binary lookup, such a data structure was born: binary lookup tree.

Binary search tree based on binary search idea

Binary Search Tree (BST) is a kind of data structure, as shown below:

In the binary search tree:

1). If the left subtree of any node is not empty, then the value of all nodes in the left subtree is not greater than the value of its root node.

2). If the right subtree of any node is not empty, then the value of all nodes in the right subtree is not less than the value of its root node.

3). The left and right subtrees of any node are binary search trees respectively.

This structure is perfect for finding elements with the binary lookup mentality.

For example, we need to find records with a key value of 8:

  1. So let’s start at the root, let’s find 6;
  2. Obviously 8 is greater than 6, so I’m going to find the right subtree of 6, find 7;
  3. Obviously 8 is greater than 7, so I find the right subtree of 7, I find 8, and I’m done.

The search efficiency of such a binary search tree whose subtree height difference is no more than 1 is close to O(log n).

But when the binary tree is constructed like this,

Now when we look for 8, the efficiency of the search is reduced to something close to the efficiency of the sequential traversal search.

Obviously this is not what we want, binary search trees also need balance.

Updated BST tree: AVL tree

We set a limit on the binary search tree, which must satisfy that the maximum difference between the two subtrees of any node is 1, which is also the definition of AVL tree, so that our search efficiency can be guaranteed to some extent.

Of course, maintaining AVL trees requires some overhead, that is, if the tree inserts/updates/deletes new data and breaks the balance of the tree, it needs to maintain the balance of the tree through left and right rotation.

When there is a large amount of data, the binary tree is also too high.

We know that the search efficiency of AVL tree is O(log n), that is to say, when the tree is too high, the search efficiency will decrease.

In addition, since our index file is not small, it is stored on disk.

When the file system needs to read data from the disk, it usually reads data by page. If the data on a page is too small, the operating system needs to read more pages, which involves more random DISK I/O accesses.

Reading data from disk into memory involves random I/O access and is one of the most expensive operations in a database.

As a result, the tree height increases dramatically with the amount of data, and each update requires a balanced binary tree maintained by left-rotation and right-rotation, which is not suitable for index files stored on disk.

B tree more consistent with disk characteristics

As we saw earlier, although AVL trees have the advantages of fast insert and delete operations on linked lists and quick array lookups, they are not the most suitable data structures for disk reads and writes.

In other words, we want to find a data structure that can effectively control the height of the tree, so we turn the binary tree into an M-tree, which is the data structure shown below :B tree.

A B-tree is a data structure that:

1. The root node has at least two children.

2. Each intermediate node contains K-1 elements and k child nodes, where m/2 <= k <= m;

3. Each leaf node contains K-1 elements, where M /2 <= k <= m;

4. All leaf nodes are in the same layer;

5. Keywords in each node are arranged from small to large, and when the child of this node is a non-leaf node, the k-1 element is exactly the partition of the range of the element contained in k child node.

As can be seen, B tree has made the following optimization on the premise of retaining the idea of binary tree pre-partitioning scope to improve query efficiency:

The binary tree becomes an M-tree. The SIZE of the M can be adjusted according to the size of a single page. In this way, more data can be stored on a page, and more data can be read from the disk.

However, as we saw, we can only query the full table through mid-order traversal, and when we do range queries, we may need mid-order backtracking.

Constantly optimizing B trees: B+ trees

Based on the above defects, a new optimized B-tree tree was born :B+ tree

B+ tree on the basis of B tree added the following optimization:

1. Leaf nodes are connected with Pointers, that is, a linked list is formed between leaf nodes;

2. Non-leaf nodes only store the key and no longer store data, but only store data in leaf nodes;

Note: The advantage of bidirectional rather than unidirectional links between leaves is that any node in the list can be found by traversing back and forth to find other nodes specified in the list.

The benefits of this are:

1. In range query, the linked list of leaf nodes can be accessed for orderly traversal, instead of the need for mid-order backtracking to visit nodes.

2. Not a leaf node only keyword key storage, on the one hand, this structure is equivalent to differentiate more range, speed up the query speed, smaller size of a single index values on the other hand, the same page can store more keywords, read a single page can get more keywords, increasing the scope of searchable and relatively reduces the number of IO, speaking, reading and writing.

Some of the summary

What’s the difference between a B+ tree and a B tree?

1. Both non-leaf nodes and leaf nodes of B tree store data, so the time complexity of data query is O(1) at best and O(log n) at worst.

B+ trees only store data in leaf nodes, while non-leaf nodes store keywords, and the keywords of different non-leaf nodes may be repeated. Therefore, the time complexity of data query is fixed at O(log N).

2. The leaf nodes of B+ tree are connected with each other in a linked list, so a traversal operation can be completed only by scanning the linked list of leaf nodes, while the middle-order traversal is only possible for B tree.

Why are B+ trees better than B trees for database indexes?

  1. The B+ tree is more suitable for disk features and reduces the NUMBER of I/O reads and writes. Because the index file is large, the index file is stored on disk. The non-leaf nodes of the B+ tree only store keywords but not data. Therefore, a single page can store more keywords, that is, more keywords need to be searched in memory at a time, and the number of random I/O reads on disk is relatively reduced.

  2. The query efficiency of B+ tree is more stable than that of B tree. Since data only exists on leaf nodes, the search efficiency is fixed at O(log n).

  3. B+ tree leaf nodes are connected by linked list in order, so scanning all data only needs to scan leaf nodes once, which is convenient for library scanning and range query. B tree can only be swept by middle-order traversal because non-leaf nodes also store data. That is, B+ trees are more efficient for range queries and ordered traversal.

The last

1. A boring little popular science, AVL tree is named because AVL tree is made by

G.M.A delson Velsky and E.M.L andis

The two Russian scientists first proposed it in a 1962 paper

2. If you have nothing to do, you can do a balanced binary tree

110. Balanced binary trees

Related supplementary links

What is a B tree

What is a B+ tree

Mysql database interview questions series continue to update, want to follow the wechat public account: pipi’s fantastic ideas

A “like” is also an encouragement