One 、B+ The advantages of trees &B+ Trees and B Tree comparison

1、B+ The tree is convenient to sweep the library

For range lookup , b + The tree only needs to traverse the leaf node list , And no sorting operation is required , Because the leaf node has modified the index The sorting operation . b Trees need to be traversed in the middle order repeatedly , Find all nodes in the range .

2、B+ Tree disk is cheaper to read and write

B+ The middle node of the tree does not save data , So the disk page can hold more node elements , more “ Short and fat ”. B Trees, whether leaf nodes or non leaf nodes spot , Data will be saved , This results in a smaller number of pointers that can be saved in a non leaf node （ Some materials are also called fan outs ） , Few pointers Save a lot of data in the next , Can only increase the height of the tree , Lead to IO More operations , Query performance becomes low ;

3、B+ Tree query efficiency is more stable

b + Tree queries must find leaf nodes , b Just go back to the matching tree . therefore b + Tree search is more stable （ Not slow ） , Must check Find the leaf node ; and B Trees , If the data is at the root node , The fastest , The slowest at the leaf node , Query efficiency is not stable .

Two 、B+ Comparison between red and black trees

Red black tree is a self balanced binary search tree , Also known as " Symmetrical binary B Trees ", It can be O(logn) Use in time O(logn) Space to complete the search 、 Insert 、 Delete operation . The read operation of red black tree is the same as that of ordinary binary search tree , The insertion and deletion operations may break the rules of the red black tree , Recovery operation is required . Restoring the nature of red and black trees requires a small amount of color change （ It's actually very fast ） And no more than three tree rotations （ For the insert operation, it's twice ）, Although insertion and deletion are complex , But the operation time can still be kept as O(logn).

difference ：
The difference between the two kinds of trees
The data of red black tree structure often exists in main memory , It is mainly used to quickly find . The amount of data stored in each node of the tree is relatively small ,cpu Through a small amount of interaction with the main memory, you can get all the data of the tree , And quickly find the required data . and B+ Tree data often exists in SSD Or on disk , Because the depth of the tree is relatively small ( commonly 3~4), Can reduce the cpu Interaction time between disks .

3、 ... and 、B+ Comparison between tree and balanced tree

Four 、 Comparison between red black tree and balanced tree