What’s the difference between a B tree and a B+ tree

For more exciting, visit Coke Coke: Coke Coke home page

A few days ago, I naivedly thought that knowing the B+ tree, which is also the Mysql tree, would be able to pass the customs smoothly. Unexpectedly, I did not expect that, in these two days, I have asked me twice about my vulnerability (another is message queue).

So, what is a B tree? Why is a B+ tree plus? What’s the difference

For those of us who have studied data structures in third grade, there is no doubt that there is a pattern

In the case of large amount of data, the efficiency of tree insertion, deletion and search is more stable than other data structures.

This is why databases, like HashMaps in Java, use trees as their own data structure for storing data.

If you’re familiar with data structures like 2-3 trees, you’ll be at ease, but not if you haven’t

Let’s start with a regular linked list

You’re all familiar with linked lists, and when we use linked lists, when we’re looking for elements, it’s a headache, and we have to go through them.

So we can take a few of them up one level as an index, and we just need to know whether the current node is big or small compared to the target, and then we can choose our own path

So, for example, when we query, we call number 3 first, using something like dichotomy.

The bottom two numbers continue to grow, and our tree becomes more complex

Let’s describe this diagram, and there are a couple of important points that you should pay attention to

  1. Each node has data
  2. Maximum 3 nodes per node group (optional)
  3. To access the lowest level of data, you need to go down the tree level by level
  4. The total I/O count is the number of tree layers

There is a problem, in order to achieve rapid allocation of space, we store every team is the use of a data page (16 KB), if you want to access to the underlying data, need IO for many times, each of these groups can store data is very limited (a group of 16 KB) space, and remove data, get the inner data, then compare.

To improve performance, Mysql has upgraded the B tree, also known as the B+ tree

B+ trees store all the data directly in the bottom layer, the upper layer is indexed (small, efficient use of space), the bottom layer of data because in the first layer, the family has to be neat, using a linked list!

What good is that?

  1. The index section is lighter, so each group can have more indexes, and the number of B+ tree levels will be lower, and the NUMBER of I/OS will be lower
  2. The underlying list is linked together to take advantage of sequential reads and writes

At this point, I don’t know if you have the concept, B+ tree upgrades the way of storage, the number of layers of THE B tree is lower, more efficient use of resources.

Master, I understand, interview is not afraid to woo woo woo

If you do, keep three companies HXD