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

In this issue, the editor will bring you about the reason why the index chooses B-tree in MongoDB. The article is rich in content and analyzes and narrates it from a professional point of view. I hope you can get something after reading this article.

I. the difference between B-tree and B + tree

Obviously, if we want to figure out why, we need to know the difference between B-trees and B + trees. In order not to make a long speech. We give their forms directly and summarize their characteristics.

1. B-tree

B-tree is a self-balanced search tree with a simple form:

This is a B-tree. The core features of our problem are as follows:

(1) Multipath, non-binary tree

(2) each node saves both index and data.

(3) search is equivalent to binary search.

Here we assume that we have already understood the structure related to the B-tree.

2. B + tree

B + tree is a variety of B-tree.

The core features are as follows:

(1) Multi-channel non-binary

(2) only leaf nodes save data.

(3) search is equivalent to binary search.

(4) the pointing pointer of the adjacent contact is added.

From the above, we can see that there are two core differences, one is the location of the data, and the other is the direction of the adjacent nodes. It is these two that make the difference between MongoDB and Mysql. Why?

3. The difference between B-tree and B + tree.

The main results are as follows: (1) the time complexity of B+ tree query is fixed, and the best query complexity of logn,B- tree is O (1).

(2) the pointers of the adjacent nodes of the B + tree can greatly increase the accessibility of the interval, and can be used in the range query, etc., while the key and data of each node of the B-tree can not be found in the interval.

(3) B + tree is more suitable for external storage, that is, disk storage. Since there is no data domain in the inner node, each node can index a larger and more accurate range.

(4) it is very important to note that this difference is based on (1) (2) (3). Each node of the B-tree saves both data and index, so the number of disk IO is very small, the B+ tree is saved only by leaf nodes, disk IO is more, but interval access is better.

With the difference between them, it would be much better for us to explain this reason now.

II. Explanation of the reasons

To explain why, we must also understand the basic concepts of MongoDB and Mysql.

1 、 MongoDB

MongoDB is a document-based database, a nosql that saves data in a Json-like format. For example, before our table may have a user table, order table, shopping basket table, etc., but also to establish a foreign key relationship between them. But Json-like is different.

We can see that this form is simpler and easier to understand. So why does MongoDB use B-trees?

MongoDB uses a B-tree, and all nodes have a data field, which can be accessed as long as the specified index is found. There is no doubt that a single query is faster than Mysql on average.

2 、 Mysql

Mysql as a relational database, the relevance of data is very strong, interval access is a common situation. Because the data of B+ tree are all stored in leaf nodes and strung together by pointers, it is easy to traverse intervals or even all of them.

The above is the reason why the editor chooses the B-tree in the index of MongoDB shared by you. If you happen to have similar doubts, you might as well refer to the above analysis to understand. If you want to know more about it, you are welcome to follow the industry information channel.

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.