Trees ： Including binary tree and multi tree
There is also B Trees and B+ Trees

B Trees

B The characteristics of the tree ：
①B The data storage of the tree is ：key-value The type of
②B How many forks there are in a tree is uncertain , It depends on the specific implementation
③M rank B Trees
There are at most M-1 It's worth , And in ascending order
（5 rank B Trees ： Each node can have at most 4 It's worth ）
The main function of memory is to cpu Provide data
for example , Here is a 5 rank B Count ：

B The tree is based on key Value for sorting
Why can a red black tree be a binary tree with optimal memory , There will be more B The emergence of trees ？
Red and black trees and B The tree is in memory ----> Memory to CPU The time to provide data is equal , Red and black tree B Compare trees , The number of data comparisons is less , So the red black tree is the best binary tree in memory .
And red and black trees and B Tree on disk , Data addressing （ Physical time of head movement + The average disk rotates half a turn ） A waste of time ,B Trees are mostly used for disks , as a result of ： Split out multiple forks , Lower the height of the tree , Time to reduce addressing times

B+ Trees

B+ Trees are MySQL Database specific underlying data structure
B+ The characteristics of the tree ：
① Non leaf nodes only have indexing function , That is, non leaf nodes , Can only store key value , Can't store value value
② B+ All leaf nodes of the tree form a linked list , This can be based on key Value traverses the data
for example ： Here is a B+ Trees

Disk to CPU Save the data , Each time you need to push a page of data （ Every time you need to push to the disk 4kb）
B+ The advantages of trees ：
①B Trees ： Non leaf nodes do not contain data , Index only , In this way, more can be transferred to memory each time key value , Compare data in memory , Query data on disk ;
② Leaf nodes are connected , It is conducive to interval query ：
select * from user where key >= 10 and key <=18;`