Data Structures Algorithms 简明教程
B+ Trees
B+ 树是 B 树的扩展，旨在使插入、删除和搜索操作更有效率。
The B+ trees are extensions of B trees designed to make the insertion, deletion and searching operations more efficient.
B+ 树的性质与 B 树的性质相似，不同之处在于 B 树可以在所有内部节点和叶子节点中存储键和记录，而 B+ 树则在叶子节点中存储记录，在内部节点中存储键。B+ 树的一个显著特性是，所有叶子节点都以单链表格式彼此连接，并且提供了一个数据指针来指向磁盘文件中存在的数据。这有助于以相等数量的磁盘访问来获取记录。
The properties of B+ trees are similar to the properties of B trees, except that the B trees can store keys and records in all internal nodes and leaf nodes while B+ trees store records in leaf nodes and keys in internal nodes. One profound property of the B+ tree is that all the leaf nodes are connected to each other in a single linked list format and a data pointer is available to point to the data present in disk file. This helps fetch the records in equal numbers of disk access.
由于主内存的大小有限，因此 B+ 树充当了存储在主内存中无法存储的记录的数据存储。为此，内部节点存储在主内存中，而叶子节点存储在辅助内存存储中。
Since the size of main memory is limited, B+ trees act as the data storage for the records that couldn’t be stored in the main memory. For this, the internal nodes are stored in the main memory and the leaf nodes are stored in the secondary memory storage.
Properties of B+ trees
-
Every node in a B+ Tree, except root, will hold a maximum of m children and (m-1) keys, and a minimum of $\mathrm{\left \lceil \frac{m}{2}\right \rceil}$ children and $\mathrm{\left \lceil \frac{m-1}{2}\right \rceil}$ keys, since the order of the tree is m.
-
The root node must have no less than two children and at least one search key.
-
All the paths in a B tree must end at the same level, i.e. the leaf nodes must be at the same level.
-
A B+ tree always maintains sorted data.
Basic Operations of B+ Trees
B+ 树支持的操作是插入、删除和搜索，所有操作的时间复杂度为 O(log n) 。
The operations supported in B+ trees are Insertion, deletion and searching with the time complexity of O(log n) for every operation.
它们与 B 树操作类似，因为将数据存储在此两种数据结构中的基本思想是相同的。然而，两者的不同之处在于，与 B 树不同，数据仅存储在 B+ 树的叶结点中。
They are almost similar to the B tree operations as the base idea to store data in both data structures is same. However, the difference occurs as the data is stored only in the leaf nodes of a B+ trees, unlike B trees.
Insertion operation
B+ 树的插入从叶结点开始。
The insertion to a B+ tree starts at a leaf node.
Step 1 − 计算要添加到 B+ 树结点上的最大和最小键数。
Step 1 − Calculate the maximum and minimum number of keys to be added onto the B+ tree node.
Step 2 − 将元素一个接一个地插入叶结点，直到超过最大键数。
Step 2 − Insert the elements one by one accordingly into a leaf node until it exceeds the maximum key number.
Step 3 − 将结点分成两半，其中左子结点包含最小键数，而剩余键存储在右子结点中。
Step 3 − The node is split into half where the left child consists of minimum number of keys and the remaining keys are stored in the right child.
Step 4 − 但是，如果内部结点也超过了最大键属性，则将结点分成两半，其中左子结点包含最小键，而剩余键存储在右子结点中。但是，将右子结点中最小的数字设为父结点。
Step 4 − But if the internal node also exceeds the maximum key property, the node is split in half where the left child consists of the minimum keys and remaining keys are stored in the right child. However, the smallest number in the right child is made the parent.
Step 5 − 如果叶结点和内部结点都具有最大键，则它们都会以类似的方式分割，并且右子结点中的最小键添加到父结点中。
Step 5 − If both the leaf node and internal node have the maximum keys, both of them are split in the similar manner and the smallest key in the right child is added to the parent node.
