B-tree, B+ tree
"TLDR: This article explores the application of B-trees and B+ trees in data structures, especially their advantages when processing large amounts of data and conducting efficient queries. First of all, the article points out that although the balanced binary tree is simple, it is not suitable for processing massive data because its height limit leads to an increase in the number of disk IOs. Next, the B-tree improves reading speed by sorting within each node, while the B+ tree reduces the number of disk IOs by storing data in leaf nodes and using linked lists to connect all leaf nodes, while ensuring the stability of query speed. Finally, the article provides reference links for readers who are interested in learning more."
These three trees have been taught several times in data structure classes, operating system classes, and database classes, but I have never heard them once. I don’t learn if I don’t take the exam, and I forget after the exam. Now let’s pay off the debt.
Before learning the B-tree, the data structure that wanted to complete efficient data query was the balanced binary tree. By limiting the height difference of the left and right subtrees to less than 1, the average query time complexity was O(logN).
So why not just use a balanced binary tree? This is because in a database scenario that stores millions of massive data, balanced binary trees are not capable of doing so.
-
First of all, the disk IO problem caused by a large amount of data: Since all data cannot be placed directly in the memory, the data index and the data itself are recorded on the disk, and the disk is a ridiculously slow device. Therefore, the height of the balanced binary tree must not be too high, and must be short enough to reduce the number of disk IOs.
-
In addition, the time of querying data must be stable enough. In a balanced binary tree, if the data is queried at the root of the tree, one disk IO is required; if the data is queried at the bottom of the tree, O(logN) disk IO is required.
-
Finally, there is the issue of range query. The database must support range queries. In a balanced binary tree, if you want to find all the data in the range [a, b], you need to perform an in-order traversal in this range, which will cause a lot of disk IO.
B-Tree
B-tree solves the problem of slow reading speed.
If you want to lower the height of the tree, you can only add more data and indexes to each node, thus forming a multi-fork tree with each node sorted inside.
B+Tree
B+ tree solves the problem of unstable search speed and slow range search speed of B-tree.
In order to stabilize the speed of each query and minimize the number of disk IOs, all data can be stored in the lowest layer, that is, in the leaf nodes. This is an important feature of the B+ tree. Since leaf nodes only store data and indexes, non-leaf nodes only store indexes. Therefore, non-leaf nodes have more space to store more indexes, thereby significantly reducing the height of the tree and reducing the number of disk IOs.
If you want to implement range search, then in the B+ tree, you can connect all leaf nodes through a linked list.