Indexed data structure

The middle node of the B+ tree does not store Data, the leaf node stores Data, and the other nodes are used for indexes. Therefore, the disk page of the same size can hold more node elements. However, each index node of the B+ tree has a Data field, so the IO times of the B+ tree are less.

For example, the size of the root node is 16KB, and the size of an index is 4B. If the tree structure has three layers, it can store tens of millions of data, and these tens of millions of data can be retrieved only three times. In addition, all leaf nodes are orderly arranged from left to right. Pointers are used to connect leaf nodes of B+ tree to improve the efficiency of range search.