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

Abstract

During the interview, when exchanging questions about the mysql index, I found that some people can keep talking about the B + tree and the B tree, balancing the difference between the binary tree, but can not tell the difference between the B + tree and the hash index. It is clear at a glance that it is rote learning and does not understand the nature of the index. The purpose of this article is to analyze the principle behind this. You are welcome to leave a comment.

problem

If you are confused or have little understanding of the following questions, please read on. I am sure this article will be helpful to you.

How mysql index implements mysql index structure what is the difference between B + tree and hash. Are there any other implementations of the index of the database applicable to what scenarios? how is the redis jump table implemented and what is the difference between the jump table and the B+ tree, the LSM tree?

Analysis

Why should mysql index and redis jump table be discussed together in the first place, because they both solve the same problem, which is used to solve the problem of finding data sets, that is, quickly finding its location (or corresponding value) according to the specified key

When you think about the problem from this point of view, don't you know the difference between Btree index and hash index?

The problem of finding data sets

Now we have clearly delineated the boundary of the problem domain in order to solve the problem of finding the data set. What issues need to be considered in this area?

Which search methods need to be supported, single key/ multi-key/ range search, insert / delete efficiency search efficiency (i.e. time complexity) storage size (space complexity)

Let's take a look at several commonly used search structures

Hash

Hash is in the form of key,value. Through a hash function, you can quickly find value according to key.

B + tree

B + tree is evolved on the basis of balanced binary tree. Why didn't we learn the structure of B + tree and jump table in algorithm class? Because they all got it from engineering practice, they made a compromise on the basis of theory.

First of all, the B+ tree is an ordered structure. in order not to have a high height of the tree and affect the search efficiency, what is stored on the leaf node is not a single data, but a page of data, which improves the search efficiency. In order to better support range query, B+ tree redundancy non-leaf node data in the leaf node, in order to support page flipping, leaf nodes are connected by pointers.

Skip meter

The jump list is extended on the basis of the linked list in order to implement the sorted set data structure of redis. Level0: it stores the original data and is an ordered linked list. Each node connects the nodes in series through pointers on the chain, which is a subset of the original data. The higher the level level, the less data in series, which can significantly improve the search efficiency.

Summary

Data structure implementation principle key query method search efficiency storage size insert and delete efficiency Hash hash table supports single key close to O (1) small, except data there is no extra storage O (1) B + tree balanced binary tree extends to single key, range, paging O (Log (n) in addition to data, but also more left and right pointers, and leaf node pointer O (Log (n), need to adjust the structure of the tree. The algorithm is more complex jump table ordered linked list extended to a single key, paging O (Log (n) in addition to data, but also more pointers, but the pointer of each node is less than

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.