Why doesn't the database use binary tree, red black tree, B tree and hash table? Instead, a b+ tree is used

---

Binary tree

If you use a binary tree , In the worst case, it will degenerate into a linked list , It's a sequential search , Traverse the entire chain .
When the amount of data is large , The number of layers will increase uncontrollably , It leads to inefficiency .

Red and black trees

Red black tree is a special balanced binary tree , He won't have the worst scenario in a binary tree , He can balance .
But there is also a problem , Because he still belongs to the binary tree , A parent node can only follow 2 Child node . If there are tens of millions of data , Then the red and black trees will be very deep and also need a lot io operation , Such a sentence can not quickly find the data we want .

B Trees

In order to solve the problem of low query efficiency caused by too deep layers of the tree , The space of each node is too small , So increase the node space , Each leaf node stores multiple index elements and corresponding multiple data.
This effectively controls the number of layers , Such a squat tree structure , Less io operation , You only need to find the corresponding leaf node search data that should be entered according to the comparison of non leaf node index elements .

B+ Trees

B There's another problem with trees , Because non leaf nodes are also stored data data , It takes up a lot of space .B+ Non leaf nodes in the tree data Data deletion , Instead, it simply places redundant indexes and corresponding node addresses , In this way, a non leaf node can store more redundant indexes , When looking for , Use binary and half search for the current non leaf node .
And leaf nodes are connected by pointers , Improved interval access performance , Support range lookup .
Each layer is stored in order .

B+ The advantages of trees

1. A single non leaf node can store as many index elements + Address , bring IO Reduced operation .
2. All searches are for the lowest leaf node , Stable performance lookup .
3. And leaf nodes have ordered linked lists , Convenient range search .

Please correct me if there is any mistake