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

This article introduces the reasons for the use of B-tree index in Mongodb. The content is very detailed. Interested friends can use it for reference. I hope it will be helpful to you.

B tree and B + tree

At the beginning, let's recall the structure and characteristics of B-tree and B + tree.

Each node in the tree stores data

There is no pointer adjacency between leaf nodes.

Notice two obvious features of the B-tree:

The data only appears on the leaf node

All leaf nodes add a chain pointer.

According to the characteristics of the above B + tree and B tree, let's make a summary:

The main results are as follows: (1) the data is stored in the tree of B-tree, so when querying a single piece of data, the query efficiency of B-tree is not fixed, and the best case is O (1). We can think that when doing a single data query, the average performance of using B-tree is better. However, because there is no pointer adjacency between the nodes in the B-tree, the B-tree is not suitable to do some data traversal operations.

(2) the data of B+ tree only appears on the leaf node, so when querying a single piece of data, the query speed is very stable. Therefore, the average performance of single data query is not as good as that of B-tree. However, the leaf nodes of the B+ tree are connected by pointers, so when traversing the data, you only need to traverse the leaf nodes, which makes the B+ tree very suitable for range query.

Therefore, we can make a corollary: maybe there are more data traversal operations in Mysql, so we use B + tree as the index structure. On the other hand, Mongodb does more single query and less data traversal operation, so it uses B-tree as the index structure.

So why does Mysql do so much data traversal? But how little does Mongodb do data traversal?

Because Mysql is a relational database, while Mongodb is non-relational data.

Then why are there so many data traversal operations in relational databases?

Instead of a relational database, do less data traversal operations?

Relational VS non-relational

Suppose we have two logical entities at this time: Student and Class. There is an one-to-many relationship between these two logical entities. After all, there are multiple students in a class, and a student can only belong to one class.

Relational database

In a relational database, we consider using several tables to represent the entity relationship between the two. The most common thing is to use a table in an one-to-one relationship. One-to-many relationship, with two tables. Many-to-many relationship, use three tables.

Then we need to check the class whose cname is Class 1 at this time. What about how many students there are?

Suppose we have an index in the cname column!

Execute SQL, as shown below!

SELECT *

FROM t_student T1, (

SELECT cid

FROM t_class

WHERE cname = 'Class 1'

) T2

WHERE t1.cid = t2.cid

And this involves the data traversal operation!

Because whenever you do this kind of related query, you can't avoid join operation! Since the join operation is involved, it is nothing more than taking a data from one table and matching row by row in another table. If the index structure is a B + tree, there is a pointer on the leaf node, which can greatly improve the matching speed of this row!

Some people may argue that if I do it first:

SELECT cid

FROM t_class

WHERE cname = 'Class 1'

After you get the cid, execute it in a loop:

SELECT *

FROM t_student

WHERE cid =...

Can you avoid join operation?

In this regard, I would like to say. You do avoid join operations, but you still don't avoid data traversal operations. You still need to traverse over and over again on the leaf node of this table in student!

So in the non-relational database, how do we query the class whose cname is Class 1 and how many students there are?

Non-relational database

Execute two queries to get the results! Once go to class collection, get id and then go to student collection.

Indeed, it's okay to design this way. I didn't say no. It just doesn't meet the original intention of the design of non-relational database. In MongoDB, this design is not recommended at all. Although there is a $lookup operation in Mongodb, you can do a join query. But ideally, this $lookup operation should not be used often, and if you need to use it often, then you are using the wrong data store (database): if you have associated data, you should use a relational database (SQL).

Suppose we have an index in the name column!

I only need to execute the statement once:

Db.class.find ({name: 'class 1'})

In this way, you can find out the results you want.

And this is a single data query! After all, you don't need to match line by line, no traversal is involved, and fortunately, it's possible to get the results you want in a single IO.

Therefore, due to the difference in the design of relational database and non-relational data. As a result, traversal operations are more common in relational data, so it is more appropriate to use B + tree as the index. In non-relational databases, a single query is more common, so it is more appropriate to use B-tree as the index.

At present, there are several kinds of interview routines:

Trick one

You wrote mysql on your resume, not mongodb!

Interviewer: "tell me about the mysql index structure?"

Me: "Barabara"

Interviewer: "do you know why you use B + tree instead of B tree?"

At this time, the normal interviewer will be fooled and will spray the shortcomings of the B tree! So the next question is.

Interviewer: "in fact, some non-relational databases, such as mongodb, use B-trees. Do you know why?"

And then you go back and wait for the notice!

Trick two

You wrote mysql and mongodb on your resume!

This situation is more perfect!

Interviewer: "tell me about the mysql index structure?"

Me: "Barabara"

Interviewer: "you have Mongodb on your resume. Do you know his index structure?"

Me: "Barabara"

Interviewer: "Why does Mongodb refer to B-tree and Mysql use B + tree?"

And then you go back and wait for the notice!

Trick three

You don't have mysql on your resume, you don't write mongodb!

Interviewer: "if you were to design a database, what data structure would you use for his index?"

Me: "first of all, do not consider the red and black trees, Barabala … should be able to use B-tree or B + tree."

Interviewer: "if I want to design a non-relational database like Mongodb, what data structure should I use as an index?"

On the reasons for the use of B-tree index in Mongodb is shared here, I hope the above content can be of some help to you, can learn more knowledge. If you think the article is good, you can share it for more people to see.

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.