[interview ordinary people vs Expert Series] understanding of B tree and B + tree

Data structure and algorithm problems , Troubled countless little friends .

Many small partners have a misunderstanding about data structure and algorithm , I don't think I use... In my work , Why do interviews ask , Asked can solve practical problems ？

Turing prize winner ： Niklaus Wirth Said ： Program = data structure + Algorithm , In other words, we are dealing with data structures all the time .

Just as Java Development , Due to the high maturity of the technical system , Makes most people think ： The program should be equal to frame + SQL ah ？

Today, let's analyze a topic of data structure ：”B Trees and B+ Trees “.

On this question , Let's take a look at the answers of ordinary people and experts ！

Ordinary people

Um. . I think … Um. … Mysql It seems to use B+ Tree to index ！ then … 

 

master

In order to answer this question more clearly , I intend to answer from three aspects ：

• Learn about binary trees 、AVL Trees 、B The concept of tree

• B Trees and B+ Tree application scenarios

1. B A tree is a multi-path balanced search tree .

   Binary tree , Each node supports a tree structure of two branches , Compared with one-way linked list , One more branch .

   Binary search tree , A rule is added to the binary tree , The value of all nodes in the left subtree is less than its root node , All child nodes of the right subtree are larger than its root node .

   

   Skew tree problem will occur in binary search tree , Resulting in increased time complexity , Therefore, a balanced binary tree is introduced , It has all the characteristics of binary search tree , At the same time, a rule is added ：” The absolute value of the height difference between its left and right subtrees shall not exceed 1“. Balanced binary trees will use left-handed 、 Right handed way to achieve balance .

   

   and B A tree is a multi-path balanced search tree , It satisfies the rules of balanced binary tree , But it can have multiple subtrees , The number of subtrees depends on the number of keywords , For example, the root node in this figure has two keywords 3 and 5, Then the number of sub paths it can have = Key words +1.

   Therefore, from this feature , When the same amount of data is stored , The height of balanced binary tree should be greater than B Trees .

   

   B+ Trees , In fact B Enhancement based on tree , There are two big differences ：

   1. B The data is stored on the tree of each node , and B+ The data in the tree is stored in leaf nodes , And connect the data in the leaf node through a linked list .

   2. B+ The number of sub paths of the tree is equal to the number of key words

   This is B The storage structure of the tree , from B It can be seen from the tree that each node will store data .

   

This is B+ Trees ,B+ All the data of the tree is stored in the leaf node , And the data of leaf nodes is associated with a two-way linked list .

1. B Trees and B+ Trees , It is generally used in file system and database system , Used to reduce disk IO Performance loss .

With Mysql Medium InnoDB For example , When we go through select Statement to query a piece of data ,InnoDB Need to read data from disk , This process involves disks IO And random disk IO.

We know that disks IO The performance of is particularly low , Especially random disks IO.

because , disk IO It works by , First, the system will transfer the logical address of the data to the disk , The disk control circuit translates the logical address into the physical address according to the addressing logic , That is to determine which track the data to be read is on , Which sector? .

In order to read the data of this sector , You need to put the head on top of this sector , To achieve this , The disk will keep spinning , Rotate the target sector under the head , Make the head find the corresponding track , This involves seek events and rotation time .

Obviously , disk IO The performance overhead of this process is very large , Especially when there is a large amount of data to query .

So in InnoDB in , Simply build an index on the data stored on the disk block , Then put the index data and the disk address corresponding to the index column , With B+ Store... In the form of a tree .

As shown in the figure , When we need to query the target data , According to the index from B+ Find the target data in the tree , because B+ There are many branches , So only a few disks are needed IO You can find it .

 

1. Why B Trees or B+ The tree is used as the index structure ？ as a result of AVL Trees are taller than trees B The height of the tree should be high , And height means disk IO The number of . So in order to reduce the number of disks IO The number of times , File system or database will adopt B Trees or B+ Trees .

So that's me right B Trees and B+ Understanding of trees ！

 

summary

Data structure is very common in practical development , For example, array 、 Linked list 、 Double linked list 、 Red and black trees 、 Skip list 、B Trees 、B+ Trees 、 Line up, etc .

in my opinion , Data structure is one of the most important basic skills in programming .

Learned the sequence list and the chain list , We can know that sequential tables should be used in scenarios with more query operations , A linked list should be used in scenarios with many modification operations .

After learning the queue , I knew for FIFO In the scene , Queues should be used .

After learning the structure of trees , You will find the original scene of finding classes , It can also further improve query performance .

Basic skills determine the height you can reach in the technical post .

well , Ordinary people in this issue VS That's the end of the expert interview series , Remember to like your friends .

If you encounter some problems in scene class and scheme design class recently , Welcome to write to me , I'll give you an answer in the following content ！

I am a Mic, A job 14 Year of Java The programmer , Let's see you in the next article .