Shulou(Shulou.com)05/31 Report--

This article mainly explains "what is the underlying principle of index failure". The explanation in this article is simple and clear, easy to learn and understand. Please follow the ideas of Xiaobian and go deep into it slowly to study and learn "what is the underlying principle of index failure" together.

single-valued index B+ tree graph

Single-valued index In the structure of B+ tree, a node stores only one key-value pair.

CODIS

A graph that starts with a joint index of fields a and b of the database.

In essence, a union index is also a B+ tree, unlike a single-valued index, which has more than one key-value pair instead of one.

a, b sort analysis

a Order: 1, 1, 2, 3, 3

b Order: 1, 2, 1, 4, 1, 2

You can see that field a is ordered and field b is unordered (because B+ trees can only select one field to build ordered trees)

If you are not careful, you will find that in the case where a is equal, the b field is ordered.

Think about it. In ordinary programming, we have to sort two fields. Is it necessary to sort according to the first field first? If the first field is equal, we will sort with the second field. This sort is also used in B+ trees.

Analyzing the Principle of Optimal Left Prefix

Let's start with an example of following the best left prefix rule.

select * from testTable where a=1 and b=2

The analysis is as follows:

First of all, the a field is ordered on the B+ tree, so we can locate the position where a=1 by binary search.

Second, in the case of a, b is relatively ordered, and because of order, b=2 can also be found by binary search.

Let's look at an example of not following the best left prefix.

select * from testTable where b=2

The analysis is as follows:

Let us recall the premise that b has order: in the case where a is certain.

Now that your a's are flying, then b must not be determined in order. In an unordered B+ tree, it is impossible to locate the b field with binary search.

At this point, the index is not used. Do you understand?

Range Inquiry Right Failure Principle

example

select * from testTable where a>1 and b=2

The analysis is as follows:

First of all, the a field is ordered on the B+ tree, so you can use the binary search method to locate 1, and then take out all the data greater than 1.

The order of b is based on the premise that a is a definite value, so now the value of a is greater than 1, there may be 10 a greater than 1, or there may be 100 a.

In the part of the B+ tree where a is greater than 1, the b field is unordered (the first graph), so b cannot be queried by binary search in the unordered B+ tree, and b does not use the index.

like index failure principle

where name like "a%" where name like "%a%" where name like "%a"

Let's first understand the use of %

% is placed on the right, representing queries for data starting with "a", such as: abc

Two %%, representing the data containing "a" in the query data, such as cab, cba, abc

% is placed on the left to represent queries ending in "a", such as cba

Why is % on the right? Sometimes you can use an index.

% on the right is called: prefix

%% is called: Infix

% on the left is called: suffix

Yes, it's still the concept of the best left prefix rule.

As you can see, the B+ tree above is composed of strings.

String sort: first sort by the first letter, if the first letter is the same, sort by the second letter. so on

to analyse

1, % sign placed on the right (prefix)

Because the index order of B+ tree is sorted according to the size of the first letter, prefix matching is also matching the first letter. So you can do an ordered search on the B+ tree to find data with the first letter that meets the requirements. So sometimes you can use indexes.

2) % on the left.

Is the data matching the tail of the string, we said above the sorting rules, the tail letters are not in order, so you can not query according to the index order, you do not use the index.

Three or two %%

This is to query letters at any position to meet the conditions, only the first letter is indexed, the letters at other positions are relatively disordered, so finding letters at any position is not indexed.

Thank you for your reading. The above is the content of "What is the underlying principle of index failure?" After studying this article, I believe everyone has a deeper understanding of what is the underlying principle of index failure. The specific use situation still needs to be verified by practice. Here is, Xiaobian will push more articles related to knowledge points for everyone, welcome to pay attention!

Welcome to subscribe "Shulou Technology Information " to get latest news, interesting things and hot topics in the IT industry, and controls the hottest and latest Internet news, technology news and IT industry trends.