Shulou(Shulou.com)06/01 Report--

For the underlying implementation of MySQL indexing, let's talk a little bit today, less about "how is it" and more about "why it's designed this way".

Question 1. Why does the database design the index?

The library has saved 1000W books, from which to find the "architect's way", one by one, when do you want to check?

So the librarian designed a set of rules:

(1) History on the first floor, literature on the second floor and IT on the third floor.

(2) IT class, which is divided into software class and hardware class.

(3) the software class is sorted according to the phonetic order of the book title.

In order to find a book quickly.

Therefore, there should be an index, which can be used to improve the search speed of the database.

Question 2. Hash is faster than tree, so why should the index structure be designed as a tree?

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

(1) Hash, such as HashMap, the average time complexity of query / insert / modify / delete is O (1)

(2) for trees, such as balanced binary search trees, the average time complexity of query / insert / modify / delete is O (lg (n)).

As you can see, whether it's a read request or a write request, an index of a hash type is faster than a tree index, so why is the index structure designed to be a tree?

Voiceover: 80% of the students couldn't answer the interview.

The index is designed as a tree, related to the requirements of SQL.

The SQL requirements for such a single-line query:

Select * from t where name= "shenjian"

It is true that hash indexing is faster, because only one record is queried at a time.

Voiceover: so, if the business requirements are single-line access, such as passport, you can indeed use a hash index.

However, the SQL requirements for sorting queries are:

Grouping: group by

Sorting: order by

Compare:

...

The hash index, the time complexity will degenerate to O (n), while the tree "ordered" property can still maintain the high efficiency of O (log (n)).

Any design that deviates from the needs is a hooligan.

By the way, InnoDB does not support hash indexes.

Question 3. Why do database indexes use B+ trees?

In order to maintain the integrity of the knowledge system, the following trees are briefly introduced.

The first kind: binary search tree

Binary search tree, as shown above, is the most well-known data structure, so let's not introduce it. Why is it not suitable for database indexing?

(1) when the amount of data is large, the height of the tree will be higher, and when the amount of data is large, the query will be slow.

(2) only one record is stored in each node, which may result in multiple disk IO in a query.

Voiceover: this tree often appears in college textbooks, so it is best known to everyone.

The second kind: B tree

The B-tree, as pictured above, is characterized by:

(1) it is no longer a binary search, but an m-search.

(2) Leaf nodes, non-leaf nodes, all store data

(3) traversal in the middle order, all nodes can be obtained.

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.